Rewriting Queries for Hyper-Relations

Hyper-relation is a recently proposed formal concept for denormalization of relational databases. Hyper-relations are structures of prejoined relations the schema of which can be represented as a hyper-graph. Instead of entire relations of the tables in the initial normalized schema, hyper-relations prejoin their atomic constituents called base relations, and do that with only those base relations that are really used in the queries being optimized. In this paper, we derive a simple and efficient algorithm for rewriting queries for hyper-relations. The algorithm is based on incremental rewriting procedure that traverses the query expression tree and builds up the transformed query by seamlessly propagating the proposed <tex-math notation="LaTeX">Σ</tex-math> operator, composed of selection and nullification of the tuples in a hyper-relation. The algorithm is applicable to a wide range of multiblock (nested) select-project-(outer) join queries.