Optimizing Conjunctive Queries that Contain Untyped Variables

Abstract

This paper addresses questions of efficiency in relational databases. We present polynomial time algorithms for minimizing and testing equivalence of what we call “fan-out free” queries. The fan-out free queries form a more general and more powerful subclass of the conjunctive queries than those previously studied. In particular, they can be used to express questions about transitive properties of databases, questions that are impossible to express if one operates under the assumption, implicit in previous work, that each variable has an assigned “type,” and hence can only refer to one fixed attribute of a relation. Our algorithms are graph-theoretic in nature, and the equivalence algorithm can be viewed as solving a special case of the graph isomorphism problem (by reducing it to a series of labelled forest isomorphism questions).