Equivalences Among Relational Expressions with the Union and Difference Operators
From MaRDI portal
Publication:3906490
DOI10.1145/322217.322221zbMath0456.68123OpenAlexW2056660085MaRDI QIDQ3906490
Mihalis Yannakakis, Yehoshua Sagiv
Publication date: 1980
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322217.322221
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Information storage and retrieval of data (68P20) Other classical set theory (including functions, relations, and set algebra) (03E20)
Related Items
Certain answers over incomplete XML documents: extending tractability boundary ⋮ Some results on the containment and minimization of (in)equality queries ⋮ Relational lattices: from databases to universal algebra ⋮ Optimization of a subclass of conjunctive queries ⋮ One-sided recursions ⋮ Efficient and optimal query answering on independent schemes ⋮ Semantic Acyclicity on Graph Databases ⋮ Knowledge compilation meets database theory: compiling queries to decision diagrams ⋮ Rewriting queries using views with access patterns under integrity constraints ⋮ Regular queries on graph databases ⋮ Can datalog be approximated? ⋮ Unnamed Item ⋮ Data independent recursion in deductive databases ⋮ Speeding up inferences using relevance reasoning: a formalism and algorithms ⋮ On simplification of schema mappings ⋮ About boundedness for some datalog and DATALOGneg programs ⋮ Query containment for data integration systems ⋮ A theoretical framework for knowledge-based entity resolution ⋮ The notion of abstraction in ontology-based data management ⋮ Classifying the computational complexity of problems ⋮ Reconcilable differences ⋮ Containment of conjunctive queries on annotated relations ⋮ Query containment under bag and bag-set semantics ⋮ The complexity of equivalence, entailment, and minimization in existential positive logic ⋮ Automated reformulation of specifications by safe delay of constraints ⋮ The complexity of higher-order queries ⋮ Conjunctive query containment with respect to views and constraints ⋮ Open-world probabilistic databases: semantics, algorithms, complexity ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ Three \(\sum^ P_ 2\)-complete problems in computational learning theory ⋮ On characterizing boundedness of database schemes with bounded dependencies ⋮ Minimizing restricted-fanout queries ⋮ Towards an algebraic theory of information integration ⋮ Decidable containment of recursive queries ⋮ XML queries and constraints, containment and reformulation ⋮ Graph Ramsey theory and the polynomial hierarchy ⋮ A time bound on the materialization of some recursively defined views ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A framework for comparing query languages in their ability to express Boolean queries ⋮ Verification of knowledge bases based on containment checking ⋮ The relational model of data and cylindric algebras ⋮ Elimination of redundant operations in relational queries with general selection operators ⋮ Characterizations for functional dependency and Boyce-Codd normal form families
