Strong equivalence of relational expressions under dependencies

DOI10.1016/0020-0190(82)90087-4MaRDI QIDQ788498zbMATH OpenOpenAlexWikidataFDO

Authors Marc H. Graham, Alberto O. Mendelzon

Publication date 1982

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(82)90087-4

zbMATH Keywords

algorithm for multi-relation query equivalencedata dependencyquery processingrelational database

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)

Review text

\textit{A. V. Aho}, \textit{Y. Sagiv} and \textit{J. D. Ullman} [SIAM J. Comput. 8, 218-246 (1979; Zbl 0412.68041)] first suggested tableaux as a means to test equivalence of relational database queries. A tableau is a tabular representation of a query that much resembles a relation. Aho, et al., showed that equivalence of queries on a single-relation database can be reduced to testing for the existence of certain kinds of functions, containment mappings, between the tableau versions of the queries. They extended this result in two directions: to multi-relation databases and to relations with data dependencies. The multi-relation case involves adding tags indicating certain relations to rows in a tableaux, along with a requirement that containment mappings preserve tags. In the presence of data dependencies, a transformation based on the dependencies, called a chase, can be applied to tableaux to reduce the problem to the no-dependencies case. This paper addresses the combined extensions: multi-relation databases with dependencies. The first problem the authors address is the proper notion of dependency satisfaction for multi-relation databases. They adopt the existence of a weak instance (a universal relation that contains all the facts in the database and obeys the dependencies) as the definition of dependency satisfaction. The main result is that applying the chase to tagged tableaux reduces the multi- relation case with dependencies to the case without dependencies. The existence of containment mappings on tagged tableaux is decidable. Thus, this result gives an algorithm for multi-relation query equivalence for classes of dependencies where the chase transformation is effective, such as functional and join dependencies.

Recommendations

• scientific article; zbMATH DE number 4039353
• scientific article; zbMATH DE number 4058918
• scientific article; zbMATH DE number 4039354
• Formal Systems for Tuple and Equality Generating Dependencies
• A Proof Procedure for Data Dependencies

Cites work

• Equivalences among Relational Expressions
• scientific article; zbMATH DE number 3596227 (Why is no real title available?)
• Preserving Functional Dependencies

Cited in

(9)

• Conditions equivalent to unit representations of ordered relational structures
• Database states and their tableaux
• On the equivalence of an Egd to a set of Fd's
• scientific article; zbMATH DE number 3982574 (Why is no real title available?)
• scientific article; zbMATH DE number 4039353 (Why is no real title available?)
• scientific article; zbMATH DE number 4039354 (Why is no real title available?)
• scientific article; zbMATH DE number 4058918 (Why is no real title available?)
• scientific article; zbMATH DE number 549084 (Why is no real title available?)
• Querying Weak Instances Under Extension Chase Semantics: A Complete Solution

This page was built for publication: Strong equivalence of relational expressions under dependencies

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