Equivalences among Relational Expressions
From MaRDI portal
Publication:4199525
DOI10.1137/0208017zbMath0412.68041OpenAlexW1975714036MaRDI QIDQ4199525
A. V. Aho, Jeffrey D. Ullman, Yehoshua Sagiv
Publication date: 1979
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/3f3d33e498578fe721f90c213f46b326c972f669
relation algebrarelational data baseNp-completeeffective computabilityequivalence problem of relational expressionsformulate queries
Other algebras related to logic (03G25) Data structures (68P05) Information storage and retrieval of data (68P20) Other classical set theory (including functions, relations, and set algebra) (03E20) Theory of computing (68Q99)
Related Items
Some results on the containment and minimization of (in)equality queries ⋮ Non-finite specifiability of projections of functional dependency families ⋮ Testing satisfiability of a class of object-oriented conjunctive queries ⋮ Relational lattices: from databases to universal algebra ⋮ Optimization of a subclass of conjunctive queries ⋮ Insertion anomalies and the justification for 4NF in relational databases ⋮ One-sided recursions ⋮ Efficient and optimal query answering on independent schemes ⋮ The Verso algebra or how to answer queries with fewer joins ⋮ A natural semantics for modal logic over databases ⋮ Testing unboundedness of database schemes and functional dependencies ⋮ Parameterized complexity of completeness reasoning for conjunctive queries ⋮ Data independent recursion in deductive databases ⋮ Classification of annotation semirings over containment of conjunctive queries ⋮ Symmetries of knowledge bases ⋮ A corrected 5NF definition for relational database design ⋮ Query containment for data integration systems ⋮ A theoretical framework for knowledge-based entity resolution ⋮ Computable queries for relational data bases ⋮ The optimum execution order of queries in linear storage ⋮ Algebraic dependencies ⋮ Automated reformulation of specifications by safe delay of constraints ⋮ Connection-trap-free database schemes ⋮ Conjunctive query containment with respect to views and constraints ⋮ Argument reduction by factoring ⋮ Logically automorphically equivalent knowledge bases models ⋮ On characterizing boundedness of database schemes with bounded dependencies ⋮ Minimizing restricted-fanout queries ⋮ Isotypeness of models and knowledge bases equivalence ⋮ Normal forms for connectedness in categories ⋮ Implication problems for functional constraints on databases supporting complex objects ⋮ Decidable containment of recursive queries ⋮ On the complexity of entailment in existential conjunctive first-order logic with atomic negation ⋮ A time bound on the materialization of some recursively defined views ⋮ Equivalence of views by query capacity ⋮ Cylindric structures and dependencies in relational databases ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ Recursive query processing: The power of logic ⋮ A characterization of finite fd-acyclicity ⋮ A fast algorithm for query optimization in universal-relation databases ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Verification of knowledge bases based on containment checking ⋮ The relational model of data and cylindric algebras ⋮ Connections in acyclic hypergraphs ⋮ On the expressive power of data dependencies ⋮ Automatic generation of test data for relational queries ⋮ Conjunctive query containment revisited ⋮ Structure and complexity of relational queries ⋮ Strong equivalence of relational expressions under dependencies ⋮ Testing containment of conjunctive queries under functional and inclusion dependencies ⋮ Elimination of redundant operations in relational queries with general selection operators ⋮ Acyclic join dependency and data base projections ⋮ The tree projection theorem and relational query processing ⋮ GYO reductions, canonical connections, tree and cyclic schemas, and tree projections ⋮ Order dependency in the relational model ⋮ Characterizations for functional dependency and Boyce-Codd normal form families ⋮ Formal systems for join dependencies ⋮ The implication and finite implication problems for typed template dependencies
