Equivalences Among Relational Expressions with the Union and Difference Operators

DOI10.1145/322217.322221MaRDI QIDQ3906490zbMATH OpenOpenAlexFDO

Authors Yehoshua Sagiv, Mihalis Yannakakis

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

zbMATH Keywords

query optimizationrelational algebrarelational databasetableau query

Mathematics Subject Classification ID

Other classical set theory (including functions, relations, and set algebra) (03E20) Data structures (68P05) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Cited in

(45)

• Elimination of redundant operations in relational queries with general selection operators
• Characterizations for functional dependency and Boyce-Codd normal form families
• Data independent recursion in deductive databases
• Speeding up inferences using relevance reasoning: a formalism and algorithms
• On characterizing boundedness of database schemes with bounded dependencies
• Minimizing restricted-fanout queries
• Verification of knowledge bases based on containment checking
• Some results on the containment and minimization of (in)equality queries
• Optimization of a subclass of conjunctive queries
• Can datalog be approximated?
• Query containment for data integration systems
• Open-world probabilistic databases: semantics, algorithms, complexity
• Regular queries on graph databases
• Automated reformulation of specifications by safe delay of constraints
• One-sided recursions
• Efficient and optimal query answering on independent schemes
• Certain answers over incomplete XML documents: extending tractability boundary
• Relational lattices: from databases to universal algebra
• Semantic acyclicity on graph databases
• Knowledge compilation meets database theory: compiling queries to decision diagrams
• Classifying the computational complexity of problems
• On simplification of schema mappings
• A theoretical framework for knowledge-based entity resolution
• The complexity of equivalence, entailment, and minimization in existential positive logic
• The complexity of higher-order queries
• scientific article; zbMATH DE number 7561474 (Why is no real title available?)
• Additive first-order queries
• About boundedness for some DATALOG and DATALOG\textsuperscript{neg} programs
• scientific article; zbMATH DE number 7104937 (Why is no real title available?)
• Decidable containment of recursive queries
• XML queries and constraints, containment and reformulation
• A time bound on the materialization of some recursively defined views
• A framework for comparing query languages in their ability to express Boolean queries
• Graph Ramsey theory and the polynomial hierarchy
• The notion of abstraction in ontology-based data management
• Reconcilable differences
• Containment of conjunctive queries on annotated relations
• Query containment under bag and bag-set semantics
• Conjunctive query containment with respect to views and constraints
• On the equivalence of recursive and nonrecursive Datalog programs
• Three \(\sum^ P_ 2\)-complete problems in computational learning theory
• How database theory helps teach relational queries in database education (invited talk)
• Towards an algebraic theory of information integration
• The relational model of data and cylindric algebras
• Rewriting queries using views with access patterns under integrity constraints

This page was built for publication: Equivalences Among Relational Expressions with the Union and Difference Operators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3906490)