6 citations · 10 across the 10 of their papers we have counts for
16 papers
Lexicographic Direct Access with Functional Dependencies
Florent Capelli, Nofar Carmeli, Stefan Mengel
We study the complexity of lexicographic direct access to join query answers over databases that satisfy functional dependencies (FDs). More precisely, we give fine-grained lower a…
Let's Play Tag: Linear Time Evaluation of Conjunctive Queries under TGD Constraints
Nofar Carmeli, Carsten Lutz, Marcin Przybyłko
We study the limits of linear time evaluation of conjunctive queries under constraints expressed as tuple-generating dependencies (TGDs), across several modes of query evaluation:…
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
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 attribu…
Efficient Computation of Quantiles over Joins
Nikolaos Tziavelis, Nofar Carmeli, Wolfgang Gatterbauer +2
We present efficient algorithms for Quantile Join Queries, abbreviated as %JQ. A %JQ asks for the answer at a specified relative position (e.g., 50% for the median) under some orde…
Direct Access for Answers to Conjunctive Queries with Aggregation
Idan Eldar, Nofar Carmeli, Benny Kimelfeld
We study the fine-grained complexity of conjunctive queries with grouping and aggregation. For common aggregate functions (e.g., min, max, count, sum), such a query can be phrased…
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
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 li…
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Complexity Analysis
Nofar Carmeli, Luc Segoufin
Even though query evaluation is a fundamental task in databases, known classifications of conjunctive queries by their fine-grained complexity only apply to queries without self-jo…
Tight Fine-Grained Bounds for Direct Access on Join Queries
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 c…
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries
Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer +2
We study the question of when we can provide direct access to the k-th answer to a Conjunctive Query (CQ) according to a specified order over the answers in time logarithmic in the…
Database Repairing with Soft Functional Dependencies
Nofar Carmeli, Martin Grohe, Benny Kimelfeld +2
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 computationa…
Tuple-Independent Representations of Infinite Probabilistic Databases
Nofar Carmeli, Martin Grohe, Peter Lindner +1
Probabilistic databases (PDBs) are probability spaces over database instances. They provide a framework for handling uncertainty in databases, as occurs due to data integration, no…
Constructing Explainable Opinion Graphs from Review
Nofar Carmeli, Xiaolan Wang, Yoshihiko Suhara +4
The Web is a major resource of both factual and subjective information. While there are significant efforts to organize factual information into knowledge bases, there is much less…
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
Nofar Carmeli, Shai Zeevi, Christoph Berkholz +2
As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tr…
On the Enumeration Complexity of Unions of Conjunctive Queries
Nofar Carmeli, Markus Kröll
We study the enumeration complexity of Unions of Conjunctive Queries(UCQs). We aim to identify the UCQs that are tractable in the sense that the answer tuples can be enumerated wit…
Enumeration Complexity of Conjunctive Queries with Functional Dependencies
Nofar Carmeli, Markus Kröll
We study the complexity of enumerating the answers of Conjunctive Queries (CQs) in the presence of Functional Dependencies (FDs). Our focus is on the ability to list output tuples…
Efficiently Enumerating Minimal Triangulations
Nofar Carmeli, Batya Kenig, Benny Kimelfeld +1
We present an algorithm that enumerates all the minimal triangulations of a graph in incremental polynomial time. Consequently, we get an algorithm for enumerating all the proper t…