Equivalences among Relational Expressions

DOI10.1137/0208017zbMATH Open0412.68041OpenAlexW1975714036MaRDI QIDQ4199525FDOQ4199525

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

zbMATH Keywords

relation algebraNp-completerelational data baseeffective computabilityequivalence problem of relational expressionsformulate queries

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05) Other algebras related to logic (03G25) Other classical set theory (including functions, relations, and set algebra) (03E20) Theory of computing (68Q99)

Cited In (58)

• Classification of annotation semirings over containment of conjunctive queries
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Symmetries of knowledge bases
• Logically automorphically equivalent knowledge bases models
• Conjunctive query containment with respect to views and constraints
• A theoretical framework for knowledge-based entity resolution
• A corrected 5NF definition for relational database design
• Decidable containment of recursive queries
• Normal forms for connectedness in categories
• Parameterized complexity of completeness reasoning for conjunctive queries
• A natural semantics for modal logic over databases
• The Verso algebra or how to answer queries with fewer joins
• On the expressive power of data dependencies
• A technique for proving decidability of containment and equivalence of linear constraint queries
• Connections in acyclic hypergraphs
• A characterization of finite fd-acyclicity
• Conjunctive query containment revisited
• Testing unboundedness of database schemes and functional dependencies
• The optimum execution order of queries in linear storage
• On characterizing boundedness of database schemes with bounded dependencies
• Implication problems for functional constraints on databases supporting complex objects
• On the complexity of entailment in existential conjunctive first-order logic with atomic negation
• Computable queries for relational data bases
• Automated reformulation of specifications by safe delay of constraints
• A fast algorithm for query optimization in universal-relation databases
• Testing containment of conjunctive queries under functional and inclusion dependencies
• Relational lattices: from databases to universal algebra
• Data independent recursion in deductive databases
• A time bound on the materialization of some recursively defined views
• Equivalence of views by query capacity
• Verification of knowledge bases based on containment checking
• Some results on the containment and minimization of (in)equality queries
• The relational model of data and cylindric algebras
• Order dependency in the relational model
• Cylindric structures and dependencies in relational databases
• The tree projection theorem and relational query processing
• Algebraic dependencies
• Non-finite specifiability of projections of functional dependency families
• Query containment for data integration systems
• Formal systems for join dependencies
• Insertion anomalies and the justification for 4NF in relational databases
• Structure and complexity of relational queries
• Minimizing restricted-fanout queries
• Recursive query processing: The power of logic
• Connection-trap-free database schemes
• Testing satisfiability of a class of object-oriented conjunctive queries
• Isotypeness of models and knowledge bases equivalence
• Strong equivalence of relational expressions under dependencies
• Elimination of redundant operations in relational queries with general selection operators
• Optimization of a subclass of conjunctive queries
• Acyclic join dependency and data base projections
• The implication and finite implication problems for typed template dependencies
• Characterizations for functional dependency and Boyce-Codd normal form families
• Automatic generation of test data for relational queries
• GYO reductions, canonical connections, tree and cyclic schemas, and tree projections
• One-sided recursions
• Efficient and optimal query answering on independent schemes
• Argument reduction by factoring

This page was built for publication: Equivalences among Relational Expressions

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