PaperlayerView exact revision on arXiv

Source-linked AI summary

Answering Conjunctive Queries under Updates

Christoph Berkholz, Jens Keppeler, Nicole Schweikardt

arXiv:1702.06370v1cs.DBcs.DScs.LO

TL;DR

The paper studies how to answer conjunctive queries as relational databases change through tuple insertions and deletions. It classifies queries using q-hierarchical structure, giving efficient maintenance algorithms and conditional lower bounds for harder cases.

  • Problem

    The paper asks how to enumerate, count, or answer conjunctive queries over relational databases that may change through tuple insertions and deletions.

    Source: §1 · p. 1

  • Method

    It uses q-hierarchical structure to classify queries and build dynamic evaluation data structures, with a q-tree characterization supporting the algorithm.

    Source: §3 · p. 7

  • Results

    Q-hierarchical queries admit efficient maintenance, while conditional lower bounds distinguish harder cases; for non-q-hierarchical self-join free queries, O(n^1−ε) delay and update time are impossible unless OMv fails.

    Source: §3 · p. 8, §7 · pp. 25–26

  • Takeaways & Limitations

    The results connect a query-structure property from database theory with the combinatorial hardness captured by the OMv-conjecture.

    Source: §7 · p. 26

    The lower bounds are conditional: they rely on OMv, and the counting lower bound additionally relies on OV.

    Source: §1.1 · p. 2, §5.1 · p. 11

Abstract

from arXiv · show

We consider the task of enumerating and counting answers to $k$-ary conjunctive queries against relational databases that may be updated by inserting or deleting tuples. We exhibit a new notion of q-hierarchical conjunctive queries and show that these can be maintained efficiently in the following sense. During a linear time preprocessing phase, we can build a data structure that enables constant delay enumeration of the query results; and when the database is updated, we can update the data structure and restart the enumeration phase within constant time. For the special case of self-join free conjunctive queries we obtain a dichotomy: if a query is not q-hierarchical, then query enumeration with sublinear$^\ast$ delay and sublinear update time (and arbitrary preprocessing time) is impossible. For answering Boolean conjunctive queries and for the more general problem of counting the number of solutions of k-ary queries we obtain complete dichotomies: if the query's homomorphic core is q-hierarchical, then size of the the query result can be computed in linear time and maintained with constant update time. Otherwise, the size of the query result cannot be maintained with sublinear update time. All our lower bounds rely on the OMv-conjecture, a conjecture on the hardness of online matrix-vector multiplication that has recently emerged in the field of fine-grained complexity to characterise the hardness of dynamic problems. The lower bound for the counting problem additionally relies on the orthogonal vectors conjecture, which in turn is implied by the strong exponential time hypothesis. $^\ast)$ By sublinear we mean $O(n^{1-\varepsilon})$ for some $\varepsilon>0$, where $n$ is the size of the active domain of the current database.

1 Introduction

The paper classifies conjunctive queries by whether their answers can be maintained efficiently as relational databases change. It gives efficient algorithms for q-hierarchical queries and conditional lower bounds that distinguish them from harder cases.

1.1 Our Contribution

  • Q-hierarchical queries admit linear-time preprocessing, constant-time updates, and constant-delay enumeration; Boolean answers and non-Boolean result sizes can also be maintained in constant time.The enumeration result applies after every update, and the result-size and Boolean-answer routines have constant update time.Source: §1.1 · p. 2
  • For self-join free queries that are not q-hierarchical, O(n^1−ε) delay and update time are impossible with arbitrary preprocessing unless the OMv-conjecture fails.Here n is the active-domain size.Source: §1.1 · p. 2
  • A Boolean query is maintainable with linear preprocessing and constant updates when its homomorphic core is q-hierarchical; otherwise, sublinear updates are ruled out unless OMv fails.The lower bound allows arbitrary preprocessing.Source: §1.1 · p. 2
  • For result-size counting, q-hierarchical queries allow linear preprocessing and constant updates; otherwise, sublinear updates are ruled out assuming both OMv and OV.The counting lower bound additionally relies on the orthogonal vectors conjecture, which is implied by the strong exponential time hypothesis.Source: §1.1 · p. 2

1 Introduction

  • The paper addresses a gap in query evaluation research: little was known about its computational complexity under updates.Source: §1.2 · p. 3

1.2 Related Work

  • Q-hierarchical queries form a proper subclass of free-connex queries, so static enumerability does not ensure efficient maintenance under updates.Free-connex queries can be enumerated with constant delay after linear preprocessing.Source: §1.2 · p. 4

2 Preliminaries

This section formalizes databases, conjunctive-query results, and the dynamic evaluation model. It defines preprocessing and update routines alongside the output measures for enumeration, counting, and Boolean answering.

2 Preliminaries

  • A database may be changed by inserting or deleting tuples, and either operation can change its active domain.Source: §2 · p. 4
  • A dynamic algorithm preprocesses the initial database into a data structure, then updates that structure when tuples are inserted or deleted.Preprocessing and update times measure the respective routines.Source: §2 · p. 5
  • Enumeration reports result tuples without repetition, with delay measured before the first output, between outputs, and before termination.Source: §2 · p. 6
  • Counting outputs the result cardinality, while Boolean answering outputs yes or no; the corresponding routines have separate time measures.Source: §2 · p. 6
  • The analysis uses data complexity: query-dependent factors are suppressed, so linear preprocessing scales with database size and constant update time may depend on the fixed query.Source: §2 · p. 6

3 Main Results

The section introduces q-hierarchical CQs as the tractable class for dynamic query answering, then gives efficient maintenance results and conjecture-conditioned lower bounds for queries outside it.

3 Main Results

  • Q-hierarchical queries require a hierarchical quantifier-free part and quantifiers that respect the query’s hierarchical form.The notion extends hierarchical-query conditions to conjunctive queries with quantified variables.Source: §3 · p. 7
  • After preprocessing linear in the initial database up to a query-dependent factor, q-hierarchical CQs admit a dynamic data structure with query-dependent polynomial update time.The structure represents the query result on the current database.Source: §3 · p. 7
  • Q-trees characterize q-hierarchical CQs and provide the tree-like basis for the dynamic data structure; not every f-representation is efficiently maintainable under updates.Every q-tree is an f-tree, but some f-trees are not q-trees.Source: §3 · p. 7
  • For self-join free CQs that are not q-hierarchical, O(n^1−ε) update time and delay are impossible with arbitrary preprocessing unless the OMv-conjecture fails.Here n is the active-domain size, and ε is any fixed positive number.Source: §3 · p. 8
  • For Boolean CQs whose homomorphic core is not q-hierarchical, O(n^1−ε) update time is impossible unless the OMv-conjecture fails.The lower bound allows arbitrary preprocessing and requires answer time O(n^2−ε).Source: §3 · p. 8
  • For CQs whose homomorphic core is not q-hierarchical, sublinear update and counting time are impossible assuming both the OMv- and OV-conjectures.The counting lower bound applies with arbitrary preprocessing and O(n^1−ε) update and counting times.Source: §3 · p. 8

4 The tree-like structure of q-hierarchical queries

The section characterizes q-hierarchical queries through q-trees: each connected component has a q-tree exactly when it is q-hierarchical. This characterization also gives a polynomial-time test and construction algorithm.

4 The tree-like structure of q-hierarchical queries

  • In a q-tree, every atom’s variables form a root-starting directed path, while free variables form a connected subtree containing the root.Source: §4 · p. 9
  • A conjunctive query is q-hierarchical exactly when each connected component has a q-tree, and this characterization yields a polynomial-time decision and construction algorithm.Every query can be decomposed into connected components, and q-hierarchical status holds exactly when all components are q-hierarchical.Source: §4 · p. 9
  • Every connected q-hierarchical query has a variable in every atom; when free variables exist, such a variable can be chosen free.Source: §4 · p. 9
  • The construction chooses a common variable as root, removes it from the atoms, recursively builds trees for the resulting connected components, then attaches them beneath the root.Source: §4 · p. 10

5 Lower Bounds

This section develops conditional lower bounds for dynamic conjunctive-query answering, enumeration, and counting via reductions from OMv/OuMv and Orthogonal Vectors, including representative and non-q-hierarchical queries and distinctions among the assumptions needed for each problem.

5.1 The OMv-conjecture

  • The OMv conjecture rules out truly subcubic online matrix-vector multiplication, and OuMv is at least as difficult; the conjecture is a conditional barrier, not a fully established assumption.OuMv requires each vector-pair answer before the next pair arrives. The authors note that overcoming OMv-based dynamic-query lower bounds could entail major algorithmic breakthroughs.Source: §5.1 · pp. 10–11

5.2 The OV-conjecture

  • The OV conjecture rules out O(n^(2−ε)) time for dimension ⌈log2 n⌉, and is implied by SETH but is not known to imply or follow from OMv.OV asks whether two sets of Boolean vectors contain an orthogonal pair; the paper uses this assumption for a counting lower bound.Source: §5.2 · p. 11

5.3 Proof Ideas

  • For active-domain-size-n databases with arbitrary preprocessing, update time n^(1−ε) and answer time n^(2−ε) for ϕ′ S-E-T imply OuMv in O(n^(3−ε)); update time and delay n^(1−ε) for enumerating ϕE-T imply OMv in O(n^(3−ε)).Source: §5.3 · pp. 11–12

5.4 Proofs of the Main Theorems

  • For Boolean queries violating hierarchy, the proof encodes a matrix and two vectors in a database so the query answer detects whether u^T M v = 1.For a core query, the reduction uses at most 2n updates per vector pair, and a homomorphism exists exactly when the Boolean product is 1; faster dynamic answering would contradict OMv.Source: §5.4 · pp. 13–14
  • Counting lower bounds require separate reductions: Boolean-query hardness does not suffice, and hierarchical queries with incorrectly nested free variables require OV rather than OuMv.The authors explain that a Boolean query’s core may be q-hierarchical even when the non-Boolean query is a non-q-hierarchical core, so the two counting cases need distinct treatment.Source: §5.4 · pp. 14, 16
  • An O(1)-time counter with O(n^{1−ε}) update time would solve Orthogonal Vectors in O(n^{2−ε/2}) time, contradicting the OV-conjecture.The reduction counts vectors in U non-orthogonal to each vector in V; it builds each database using O(nd) updates and checks whether the count is less than n.Source: §5.4 · p. 16
  • For a self-join-free query failing condition (i), sublinear-delay enumeration would answer its non-q-hierarchical Boolean version with the same delay, contradicting Theorem 3.4.The Boolean query is its own core, and its answer is determined by whether enumeration produces a tuple or the end-of-enumeration message.Source: §5.4 · p. 17
  • For a self-join-free query ϕ, if dynamic enumeration has O(n^(1−ε)) delay and update time, the encoding solves OMv in O(n^(3−ε)) time.Each arriving vector requires at most n insertions or deletions of tuples, and its product Mv is computed in O(n^(2−ε)) time.Source: §5.4 · p. 17

6 Upper Bound

This section presents a q-tree-based data structure for q-hierarchical queries that supports constant-delay enumeration and efficient counting, with updates maintained through per-item counts and weights and stored projected-output counts for constant-time count requests.

6 Upper Bound

  • For disconnected q-hierarchical queries, the structure handles each connected component separately, counts by multiplying component counts, and enumerates through nested loops.Source: §6 · p. 17

6.2 The data structure

  • Each database fact induces only a constant number of items, so the structure is linear-sized; updates affect only constantly many fit statuses, enabling constant-time list changes with constant-time access.Source: §6.2 · pp. 18–19
  • Stored item weights and list sums support immediate counting for quantifier-free queries and Boolean answer testing via Cstart.Source: §6.2 · p. 19

6.3 Enumeration

  • The q-tree enumeration routine outputs every free-variable assignment exactly once, with O(k) delay between consecutive tuples.Source: §6.3 · p. 21

6.4 Preprocessing and update

  • Preprocessing constructs the q-tree, initializes the empty-database structure, and applies the initial database’s updates, yielding linear preprocessing when updates take constant time.Source: §6.4 · p. 23
  • For each item, atom-expansion counts identify whether condition (a) holds, allowing items to be created or removed in constant time as updates change those counts.An update changes only a constant number of atom-expansion counts; the affected weights and sums are recomputed bottom-up in time poly(ϕ).Source: §6.4 · p. 24

6.5 Counting in the presence of quantifiers

  • For quantified non-Boolean queries, the maintained projected count eCstart equals |ϕ(D)| and answers count requests in O(1).The update procedure also recomputes projected counts for free-variable items and adjusts their parent sums using Lemma 6.4.Source: §6.5 · p. 25

7 Discussion

The paper classifies efficient dynamic evaluation for several conjunctive-query tasks and identifies an open classification problem for enumeration with self-joins. Its discussion connects query structure to hardness in dynamic algorithms.

7 Discussion

  • Q-hierarchical queries characterize efficient maintenance, and the paper gives corresponding lower bounds and a complete picture for Boolean queries and result-size computation.The q-hierarchical property also precisely characterizes efficient enumeration under updates for self-join-free conjunctive queries.Source: §7 · pp. 25–26
  • The classification of enumeration for conjunctive queries with self-joins remains an open problem.The discussion notes that even the static setting lacks a complexity classification for join queries with self-joins.Source: §7 · p. 26
  • For self-join enumeration, non-q-hierarchical queries can differ: ϕ1 has an OMv-conditioned lower bound, while ϕ2 admits constant-delay enumeration with constant updates.The latter handles loop outputs first, then preprocesses ϕ1 on the database with that loop deleted.Source: §7 · p. 26
  • The paper initiates systematic study of query evaluation under updates and links non-hierarchical query structure to combinatorial hardness captured by the OMv-conjecture.The authors identify conjunctive queries with negation and unions of conjunctive queries as further settings under study.Source: §7 · p. 26

APPENDIX

The appendix contains proof details omitted from Section 7.

APPENDIX

  • The appendix supplies proof details that were omitted from Section 7.Source: APPENDIX · p. 30

A Details on the Discussion about Queries with Self-Joins

This discussion establishes an OMv-based lower bound for dynamic enumeration of ϕ1 and describes a constant-delay, constant-update enumeration algorithm for ϕ2. The lower-bound proof encodes online matrix-vector multiplication in database edges and loops; the ϕ2 algorithm uses output time to perform static preprocessing.

A Details on the Discussion about Queries with Self-Joins

  • Sublinear update time and delay for enumerating ϕ1 would imply an O(n^{3−ε}) OuMv algorithm, contradicting the OMv-conjecture.The argument allows arbitrary preprocessing time and uses n as the active-domain size.Source: A Details on the Discussion about… · p. 30
  • Matrix entries are encoded as E-tuples and vector bits as loops, so enumeration checks simulate each OuMv product in O(n^{3−ε}) total time.The reduction initializes from the empty database and inserts matrix tuples using the assumed update bound.Source: A Details on the Discussion about… · p. 30
  • In the static setting, ϕ1 can be enumerated with constant delay after O(||D||) preprocessing because it is free-connex acyclic..Source: A Details on the Discussion about… · p. 30
  • The ϕ2 algorithm stores E-tuples in a doubly linked list alongside an adjacency matrix, supporting constant-time insertion and deletion.The list is implemented with arrays for next and previous links and first/last tuple pointers.Source: A Details on the Discussion about… · pp. 30–31
  • For ϕ2, outputting (c0, c0) × ED provides enough time to preprocess ϕ1 on the database with (c0, c0) deleted, then enumerate the remaining results.This enumeration has constant delay after linear-time preprocessing and constant-time updates.Source: A Details on the Discussion about… · pp. 30–31
Loading 1702.06370v1…