Strong equivalence of relational expressions under dependencies (Q788498)

\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.