From the 1 of 6 linked papers with an AI index.
6 papers
Lexicographic Direct Access with Functional Dependencies
Florent Capelli, Nofar Carmeli, Stefan Mengel
The paper investigates how quickly one can retrieve join query results in lexicographic order from databases that satisfy functional dependencies, providing fine‑grained lower and…
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…
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…
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…
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…