Tree queries

Abstract

One can partition the class of relational database schemas into tree schemas and cyclic schemas. (These are called acyclic hypergraphs and cyclic hypergraphs elsewhere in the literature.) This partition has interesting implications in query processing, dependency theory, and graph theory. The tree/cyclic partitioning of database schemas originated with a similar partition of equijoin queries. Given an arbitrary equijoin query one can obtain an equivalent query that calculates the natural join of all relations in (an efficiently) derived database; such a query is called a natural join (NJ) query. If the derived database is a tree schema the original query is said to be a tree query, and otherwise a cyclic query. In this paper we analyze query processing consequences of the tree/cyclic partitioning. We are able to argue, qualitatively, that queries which imply a tree schema are easier to process than those implying a cyclic schema. Our results also extend the study of the semijoin operator.