NCNofar Carmeli

Nofar Carmeli

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Nofar Carmeli has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Enumeration Theory through the Lens of Database Challenges

    by Florent Capelli, Nofar Carmeli, Alessio Conte, Benny Kimelfeld, Reinhard Pichler, Nikolaos Tziavelis

    Computational tasks that require producing many solutions arise throughout data management systems: database query engines return all qualifying tuples; search engines retrieve all relevant documents, albeit ranked; graph databases are tasked with producing all paths connecting two nodes; query optimizers routinely explore a vast space of candidate plans; and so on. Abstractly, these tasks are formalized as enumeration problems, solved by enumeration algorithms, and studied through the lens of enumeration complexity. This talk reflects on the evolution of enumeration in database research. It will begin with a brief survey of classic complexity-theoretic notions and algorithmic techniques that play a central role in enumeration across many domains. It will then review past results on enumeration problems arising in various areas of database systems. After that, it will delve deeper into the evolution of ideas and results on relational queries, with a special focus on join queries. It will conclude with challenges for future directions.

  • Open Access

    Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum

    by Nofar Carmeli, Nikolaos Tziavelis

    We investigate the fine-grained complexity of direct access to Conjunctive Query (CQ) answers according to their position, ordered by the minimum (or maximum) value between attributes. We further use the tools we develop to explore a wealth of related tasks. We consider the task of ranked enumeration under min/max orders, as well as tasks concerning a CQ with a predicate of the form x ≤ min X , where X is a set of variables and x is a single variable: counting, enumeration, direct access, and predicate elimination (i.e., transforming the pair of query and database to an equivalent pair without min-predicates). For each task, we establish a complete dichotomy for self-join-free CQs, precisely identifying the cases that are solvable in near-ideal time, i.e., (quasi)linear preprocessing time followed by constant or logarithmic time per output.

  • Open Access

    Tuple-Independent Representations of Infinite Probabilistic Databases

    by Nofar Carmeli, Martin Grohe, Peter Lindner, Christoph Standke

    Infinite probabilistic databases (PDBs) are a framework of probability distributions over infinitely many different database instances. We systematically study the representability problem for such PDBs by means of tuple-independence and first-order views. Although first-order views over tuple-independent PDBs are not a complete representation system for infinite PDBs, they form a fairly robust class: Adding first-order constraints does not give them additional expressive power, and they cover many relevant special cases such as block-independent disjoint PDBs, and PDBs of bounded instance size. We identify criteria for representability (or non-representability) in this class and explore their limits. In addition, we study the expressive power of fragments of first-order logic over tuple-independent PDBs. In general, for infinite PDBs, the landscape of relative expressive power for various classes of views over PDBs with independence assumptions is much more complex than in the finite setting.

  • Top Cited Papers
    Open Access

    Direct Access for Conjunctive Queries with Negations

    by Florent Capelli, Nofar Carmeli, Oliver Irwin, Sylvain Salvati

    Given a conjunctive query $Q$ and a database $D$, a direct access to the answers of $Q$ over $D$ is the operation of returning, given an index $k$, the $k$-th answer for some order on its answers. While this problem is $\#\mathcal{P}$-hard in general with respect to combined complexity, many conjunctive queries have an underlying structure that allows for a direct access to their answers for some lexicographical ordering that takes polylogarithmic time in the size of the database after a polynomial time precomputation. Previous work has precisely characterised the tractable classes and given fine-grained lower bounds on the precomputation time needed depending on the structure of the query. In this paper, we generalise these tractability results to the case of signed conjunctive queries, that is, conjunctive queries that may contain negative atoms. Our technique is based on a class of circuits that can represent relational data. We first show that this class supports tractable direct access after a polynomial time preprocessing. We then give bounds on the size of the circuit needed to represent the answer set of signed conjunctive queries depending on their structure. Both results combined together allow us to prove the tractability of direct access for a large class of conjunctive queries. On the one hand, we recover the known tractable classes from the literature in the case of positive conjunctive queries. On the other hand, we generalise and unify known tractability results about negative conjunctive queries -- that is, queries having only negated atoms. In particular, we show that the class of $β$-acyclic negative conjunctive queries and the class of bounded nest set width negative conjunctive queries admit tractable direct access.


  • Open Access

    Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum

    by Nofar Carmeli, Nikolaos Tziavelis

    We investigate the fine-grained complexity of direct access to Conjunctive Query (CQ) answers according to their position, ordered by the minimum (or maximum) value between attributes. We further use the tools we develop to explore a wealth of related tasks. We consider the task of ranked enumeration under min/max orders, as well as tasks concerning CQs with predicates of the form x <= min X , where X is a set of variables and x is a single variable: counting, enumeration, direct access, and predicate elimination (i.e., transforming the pair of query and database to an equivalent pair without min-predicates). For each task, we establish a complete dichotomy for self-join-free CQs, precisely identifying the cases that are solvable in near-ideal time, i.e., (quasi)linear preprocessing time followed by constant or logarithmic time per output.

  • Open Access

    PACMMOD, V3, N2 (PODS), May 2025 Editorial

    by Nofar Carmeli, Floris Geerts, Ahmet Kara, Benny Kimelfeld

    We are excited to announce the third issue dedicated to the Principles of Database Systems (PODS) research track of the Proceedings of the ACM on Management of Data (PACMMOD) journal. In its current form, the journal hosts both a SIGMOD and a PODS research track. The PODS research track aims to provide a solid scientific foundation for methods, techniques, and solutions to the data management challenges that continually arise in our data-driven society. More specifically, articles in the PODS track of PACMMOD present principled contributions to modeling, application, system building, and both theoretical and experimental validation in the context of data management. Such articles may be based, among others, on establishing theoretical results, developing new concepts and frameworks that merit further exploration, providing experimental work that sheds light on the scientific foundations of the discipline, or conducting a rigorous analysis of widely used and/or recently developed industry artifacts.

  • Open Access

    Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries

    by Karl Bringmann, Nofar Carmeli

    We study the enumeration of answers to Unions of Conjunctive Queries (UCQs) with optimal time guarantees. More precisely, we wish to identify the queries that can be solved with linear preprocessing time and constant delay. Despite the basic nature of this problem, it was shown only recently that UCQs can be solved within these time bounds if they admit free-connex union extensions, even if all individual CQs in the union are intractable with respect to the same complexity measure. Our goal is to understand whether there exist additional tractable UCQs, not covered by the currently known algorithms. As a first step, we show that some previously unclassified UCQs are hard using the classic 3SUM hypothesis, via a known reduction from 3SUM to triangle listing in graphs. As a second step, we identify a question about a variant of this graph task that is unavoidable if we want to classify all self-join-free UCQs: is it possible to decide the existence of a triangle in a vertex-unbalanced tripartite graph in linear time? We prove that this task is equivalent in hardness to some family of UCQs. Finally, we show a dichotomy for unions of two self-join-free CQs if we assume the answer to this question is negative. In conclusion, this paper pinpoints a computational barrier in the form of a single decision problem that is key to advancing our understanding of the enumeration complexity of many UCQs. Without a breakthrough for unbalanced triangle detection, we have no hope of finding an efficient algorithm for additional unions of two self-join-free CQs. On the other hand, a sufficiently efficient unbalanced triangle detection algorithm can be turned into an efficient algorithm for a family of UCQs currently not known to be tractable.


  • Open Access

    Tight Fine-Grained Bounds for Direct Access on Join Queries

    by Karl Bringmann, Nofar Carmeli, Stefan Mengel

    We consider the task of lexicographic direct access to query answers. That is, we want to simulate an array containing the answers of a join query sorted in a lexicographic order chosen by the user. A recent dichotomy showed for which queries and orders this task can be done in polylogarithmic access time after quasilinear preprocessing, but this dichotomy does not tell us how much time is required in the cases classified as hard. We determine the preprocessing time needed to achieve polylogarithmic access time for all join queries and all lexicographical orders. To this end, we propose a decomposition-based general algorithm for direct access on join queries. We then explore its optimality by proving lower bounds for the preprocessing time based on the hardness of a certain online Set-Disjointness problem, which shows that our algorithm’s bounds are tight for all lexicographic orders on join queries. Then, we prove the hardness of Set-Disjointness based on the Zero-Clique Conjecture, which is an established conjecture from fine-grained complexity theory. Interestingly, while proving our lower bound, we show that self-joins do not affect the complexity of direct access (up to logarithmic factors). Our algorithm can also be used to solve queries with projections and relaxed order requirements, though in these cases, its running time is not necessarily optimal. We also show that similar techniques to those used in our lower bounds can be used to prove that, for enumerating answers to Loomis-Whitney joins, it is not possible to significantly improve upon trivially computing all answers at preprocessing. This, in turn, gives further evidence (based on the Zero-Clique Conjecture) to the enumeration hardness of self-join-free cyclic joins with respect to linear preprocessing and constant delay.


  • Open Access

    PACMMOD, V2, N5 (PODS), November 2024 Editorial

    by Nofar Carmeli, Floris Geerts, Benny Kimelfeld

    This editorial accompanies the second issue dedicated to the PODS research track of the Proceedings of the ACM on Management of Data (PACMMOD) journal. The journal hosts a SIGMOD and a PODS research track. The PODS research track aims to provide a solid scientific basis for methods, techniques, and solutions for the data management challenges that continually arise in our data-driven society. Articles for the PODS track of PACMMOD present principled contributions to modeling, application, system building, and both theoretical and experimental validation in the context of data management. Such articles might be based, among others, on establishing theoretical results, developing new concepts and frameworks that deserve further exploration, providing experimental work that sheds light on the scientific foundations of the discipline, or conducting a rigorous analysis of industry artifacts that are widely used and/or recently developed. Articles published in this track will be invited for presentation to the ACM Symposium on Principles of Database Systems (PODS), which is held jointly with SIGMOD each year.

  • Open Access

    Database Repairing with Soft Functional Dependencies

    by Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, Muhammad Tibi

    A common interpretation of soft constraints penalizes the database for every violation of every constraint, where the penalty is the cost (weight) of the constraint. A computational challenge is that of finding an optimal subset: a collection of database tuples that minimizes the total penalty when each tuple has a cost of being excluded. When the constraints are strict (i.e., have an infinite cost), this subset is a “cardinality repair” of an inconsistent database; in soft interpretations, this subset corresponds to a “most probable world” of a probabilistic database, a “most likely intention” of a probabilistic unclean database, and so on. Within the class of functional dependencies, the complexity of finding a cardinality repair is thoroughly understood. Yet, very little is known about the complexity of finding an optimal subset for the more general soft semantics. The work described in this manuscript makes significant progress in that direction. In addition to general insights about the hardness and approximability of the problem, we present algorithms for two special cases (and some generalizations thereof): a single functional dependency, and a bipartite matching. The latter is the problem of finding an optimal “almost matching” of a bipartite graph where a penalty is paid for every lost edge and every violation of monogamy. For these special cases, we also investigate the complexity of additional computational tasks that arise when the soft constraints are used as a means to represent a probabilistic database in the case of a probabilistic unclean database.