About

I am a researcher, employed by Inria, at the Boreal joint project-team (LIRMM, Inria, University of Montpellier, CNRS) in Montpellier, France.
My research focuses on the theory of database query optimization.

Contact.
nofar.carmeli at inria.fr
(!) I no longer have access to my old email address at cs.technion.ac.il.

Research

My research interests revolve around the theory of data management, often using fine-grained complexity and enumeration complexity. My main line of research aspires to determine, for any given query that the user wants to compute over a database, what is an algorithm that runs with optimal guarantees. So far, I focused mostly on identifying the query structures that can be answered with near-optimal time guarantees. For a full list of publications, see Google Scholar or dblp.

• Direct Access to Query Answers

  An array holding the sorted list of query answers can be useful in many scenarios, even when we do not need all answers (e.g., for finding the median or creating a boxplot), but such an array can be very big, and creating it may take a lot of time. Can we simulate such an array more efficiently than materializing it? We call the task of simulating such an array "direct access".

  Dichotomies for conjunctive queries. When can we simulate an array containing the answers with only linear preprocessing and logarithmic overhead? We looked into conjunctive queries, when the answers are required to be sorted lexicographically or by sum of weights. Published as "Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries".⁽¹⁾

  Arxiv PODS 21 TODS 23 Talk

  Optimal preprocessing for join queries. How much preprocessing is required to achieve logarithmic overhead? We looked into full conjunctive queries, when the answers are required to be sorted lexicographically. Published as "Tight Fine-Grained Bounds for Direct Access on Join Queries".⁽¹⁾

  Arxiv PODS 22 TODS 24 Talk

  Quantile Queries. Simulating the sorted array of answers can only be done efficiently for queries of some structures. However, sometimes we only need to read a small number of answers from this array. We propose an efficient algorithm for a single access to the answers array, and when this is provably not possible - an approximation algorithm. We looked into full conjunctive queries, when the answers are required to be sorted lexicographically, by sum of weights, or by the minimum of attributes. Published as "Efficient Computation of Quantiles over Joins".

  Arxiv PODS 23

  Conjunctive queries with aggregation. We looked into conjunctive queries with grouping and aggregation, when the answers are required to be sorted lexicographically. When can we simulate an array containing the answers with only linear preprocessing and logarithmic overhead? Published as "Direct Access for Answers to Conjunctive Queries with Aggregation".⁽¹⁾

  Arxiv ICDT 24 Talk

  (1) Invited for a special issue of the journal on selected publications from the conference.

• Enumerating Query Answers

  Suppose we want to efficiently list all query answers. If the queries we consider are Conjunctive Queries (CQs) without self joins over general databases, we know exactly for which queries this can be done with ideal time guarantees (linear preprocessing and constant delay). We look into how this classification extends to more general settings.

  Answering queries with self joins. Known hardness results apply only for queries without self joins. We study how self joins affect the complexity of listing all query answers and identify several cases where they turn queries with an intractable structure into tractable queries. Published as "Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis".

  Arxiv PODS 23 Talk

  Answering queries in random order. We would like to efficiently list all query answers in uniformly random order, so every prefix of the answers is statistically meaningful. When can this be achieved with only linear preprocessing and polylogarithmic delay? We propose an algorithm that uses direct access to the query answers, and we inspect when conjunctive queries and unions of conjunctive queries admit efficient algorithms for these two tasks. Published as "Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration".

  Arxiv PODS 20 TODS 22 Slides

  Answering unions of conjunctive queries. When can we list the answers to unions of conjunctive queries with optimal time guarantees (linear preprocessing and constant delay)? Among our results, we show that the tractable cases are not limited to unions of tractable CQs, and in fact, some unions consisting of only intractable CQs are tractable too. Published as "Enumeration Complexity of Unions of Conjunctive Queries".⁽¹⁾⁽²⁾

  Arxiv PODS 19 TODS 21 Talk

  We show that unbalanced triangle detection is a closely related problem, and assuming its hardness, the previous work captures all tractable unions of 2 self-join-free CQs.

  Arxiv

  Answering CQs with functional dependencies. Very often databases contain dependencies among attributes, and some queries classified as hard over general databases become tractable if we are allowed to exploit these dependencies. We inspect in which cases the dependencies are enough to make conjunctive queries solvable with optimal time guarantees (linear preprocessing and constant delay). Published as "Enumeration Complexity of Conjunctive Queries with Functional Dependencies".⁽¹⁾

  Arxiv ICDT 18 TOCS 20 Corrigendum Slides

  (1) Invited for a special issue of the journal on selected publications from the conference.
  (2) PODS 2019 Best Student Paper.

• Handling Complicated Data

  While the previous sections treated cases where things can be done very efficiently, things are not always that simple. This section proposes solutions for when databases contain uncertainty (in the form of noise that needs to be cleaned or probabilistic databases), when data does not appear in a neat structured form, or when the queries we want to answer cannot be quickly tweaked into a tractable acyclic form.

  Repairing databases using soft functional dependencies. Assume we have a database that contains noise in the form of redundant facts, and we have constraints in the form of Functional Dependencies (FDs) that are interpreted as soft: they do not necessarily always hold. Instead, every violation and every removal of a fact from the database are penalized. When can we efficiently find an optimal subset of the database? Published as "Database Repairing with Soft Functional Dependencies".⁽¹⁾

  Arxiv ICDT 21 TODS 24 Talk

  Representing infinite probabilistic databases. Infinite Probabilistic Databases (PDBs) model uncertainty when the possible values are not restricted to a finite domain. In the finite case, tuple-independent representations have many advantages, but in the infinite, they cannot always be used. When can they represent the desired infinite PDB? Published as "Tuple-Independent Representations of Infinite Probabilistic Databases".⁽¹⁾

  Arxiv PODS 21 Talk

  Summarizing reviews with structural explanations. Given a large number of reviews expressing opinions regarding a product, we want to automatically build a graph describing the (deduplicated) opinions expressed in the reviews, together with the explanation relationship (e.g. "walking distance to the beach" explains "great location"). Published as "ExtremeReader: An interactive explorer for customizable and explainable review summarization" and "Constructing Explainable Opinion Graphs from Reviews".

  Arxiv WWW 20 WWW 21 Project Page

  Finding tree decompositions. Tree decompositions can be used to optimize join queries, but finding the best decomposition is known to be hard. We propose an algorithm that enumerates all the proper tree decompositions (or minimal triangulations) of a graph in incremental polynomial time. This can be used as an anytime algorithm to improve on any method for finding a single tree decomposition (or triangulation). Published as "Efficiently Enumerating Minimal Triangulations".

  Arxiv PODS 17 DAM 20 Code Talk

  (1) Invited for a special issue of ACM Transaction on Database Systems (TODS) on selected publications from the conference.

• Ph.D. Thesis

  The Power of Implicit Acyclicity in the Enumeration Complexity of Database Queries

  The complexity of enumerating (i.e., listing) query answers over a database depends on the query structure (acyclic is easy). However, a query with a naturally difficult structure can sometimes be adjusted into an easy form by using commonly available additional information (hence the acyclicity is implicit). My work aims at identifying how fast we can solve any given query. This is done either by providing an efficient algorithm for answering the query or by proving that an algorithm with a given complexity cannot be achieved.

  Thesis Talk

Recorded Talks

Professional Background