Technical Report CS0368

Title: Hypergraph Covering Algorithms for Relational Query Processing
Authors: A. Lustig and O. Shmueli
Abstract: Tree schemas (acyclic hypergraphs) play a fundamental role in the theory of relational query processing. Consider a query Q which is the join of some relations projected on a prescribed set of attributes. Suppose Q is solved by a finite program P using the operators project, join and semijoin. It is known that P must transform the original set of relations into a new set of relations that contains an "embedded" tree schema which includes the original relations and the desired result relation; such a schema is called a tree projection. This work analyzes two classes of simple cyclic schemas called Arings and Diamonds. Given database schema D1 (which is an Aring or a Diamond) and an arbitrary database schema D2, polynomial time algotithms are presented for deciding whether there exists a tree projection. A tree projection is a tree schema D3 such that each relation schema in D3 is contained in some relation of D2 and each relation in D1 is contained in some relation of D3. These algorithms are not merely of theoretical interest; they may prove useful as part of query processors for both centralized and distributed database systems.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1985
To the main CS technical reports page

Computer science department, Technion