nucleation

THEORY-389: For conjunctive queries and views without comparison predicates, a stored view can be used in an equivalent rewriting of a query exactly when the view's body maps homomorphically into the query's, a minimal rewriting needs no more literals than the query, and deciding whether a rewriting shorter than the query or one using only the views exists is NP-complete in the size of the query and view definitions; with comparisons in both, deciding whether any rewriting uses the views is Π2p-complete

4 min read

Properties5
StatusActive
Tagsdatabases, logic
SourceLIT-1100 — Answering Queries Using Views, LIT-1111 — Optimal Implementation of Conjunctive Queries in Relational Data Bases
Bears onQUESTION-114 — Is sorting a collection amortized search, and does physical database design, where a table is stored in one order and every further index is paid for in space and upkeep, give the joint cost model that the question on amortized retrieval lacks?
SupportsCLAIM-303 — Filing an argument moves work across time: it is paid for now, in filing, indexing, tracking dependencies and checking it is still current, against reconstruction later, so it is worth its cost only when expected reuse covers it, and recurrence is evidence of reuse, not the criterion, CLAIM-314 — Reusing a filed argument has a recognition cost that a fixed per-use price leaves out: certifying that stored answers cover a new question is NP-complete even for conjunctive queries, grows with the number and size of the stored definitions rather than being a constant per item, and is undefined for an item filed without a statement of what it answers, so each filing raises the cost of later reuse and per-item break-even decisions are not independent

Graph View

Source

Levy, Mendelzon, Sagiv and Srivastava (1995), LIT-1100, “Answering queries using views (extended abstract)”, PODS 1995, pp. 95–104, read in full in NOTE-909 from the authors’ camera-ready on Mendelzon’s Toronto page. It rests on Chandra and Merlin 1977 (LIT-1111, THEORY-371).

What was actually shown

The problems. A rewriting of Q using views V is a conjunctive query equivalent to Q on every database that uses at least one view literal; a complete rewriting uses only view literals and built-ins. The questions: does some rewriting use V; is there one with fewer than k literals, or fewer than k database literals; is there a complete one.

Usability is containment (Proposition 3.1). There is a rewriting of Q using V iff the boolean projection of Q is contained in that of V, “If V is empty for a given database, then so is Q”, that is, iff V’s body maps into Q’s body. Every use of a view is found among these mappings.

The size bound (Lemma 3.5, Lemma 3.3). Without comparisons, a locally minimal complete rewriting has at most as many literals as Q, uses a subset of Q’s database literals and needs no new variables. The bound fails with functional dependencies, and with comparisons a rewriting may need unions or be exponentially long.

Complexity. Without comparisons, the shorter-rewriting problems and the complete-rewriting problem are NP-complete (Theorem 3.7 (1)–(3)), also for unions of conjunctive queries (Theorem 3.9). With comparisons in Q only, existence of a rewriting using V is NP-complete; with comparisons in both, Π2p-complete (Proposition 3.2); the shorter-rewriting problem is then in Σ3p. Theorem 3.10: complete rewriting stays NP-complete when no rule repeats a predicate, so each view maps into the query in at most one way; the hardness then comes from combining views (exact cover by 3-sets). The paper calls these “two independent sources” of complexity: “The first source is the exponential number of possible containment mappings from the views to the query”; the second is deciding which query literals become redundant.

A tractable step (Theorem 4.4). Given one mapping, the needed literals are computable in polynomial time; if the mapping is one-to-one on view literals and Q is minimal, their complement is the unique maximal set of redundant literals.

What could have come out otherwise. A usable view with no containment mapping into the query would refute Proposition 3.1; a minimal complete rewriting longer than the query, without comparisons or dependencies, would refute Lemma 3.5.

What this does not say

  • That recognizing reuse is expensive in practice. Hardness is worst case, in the size of the query and view definitions; the stored data never enters. The authors expect the polynomial step to handle “many practical cases”.
  • Anything about contained or partial answers. Only equivalent rewritings are studied. Whether stored answers cover some cases of a question (maximally-contained rewritings) is LIT-1116’s subject (THEORY-374), with different complexity.
  • Which rewriting to use. Minimality is counted in literals; choosing between rewritings by evaluation cost is, in the paper’s words, “not addressed”.
  • Anything about stored items without definitions or in prose. Every result assumes each view carries a conjunctive definition over the query’s schema. For a filed argument, there is no such definition, and coverage is not shown decidable.

Connections

  • QUESTION-114: the stored-answer readings (THEORY on Harinarayan et al., LIT-1094) take answerability from a view as given by the lattice. This prices that step in general: NP-complete for conjunctive queries, so the joint cost model the question asks for has a recognition term besides storage, upkeep and saving.
  • CLAIM-303’s c_a has a recognition term that varies with the question and with the set of filed items; CLAIM-308 and THEORY-348 assume a fixed per-use price. This narrows where the 2-competitive rule applies; it does not refute it.
  • THEORY-371 is the containment theory underneath; THEORY-374 places this result among contained rewritings and certain answers.

Backlinks