Calculating Constraints on Relational Expressions

Abstract

A desirable feature of a database management system is the ability to support many views of the database via several user models. In order to provide this support while allowing the user to believe that his/her view and data model are the only ones, the database system must have a number of facilities. One of the most important of these is a mechanism to tell when view constraints will be satisfied given that the underlying database constraints are satisfied so that the user always sees what is expected. This paper deals with a particular instance of this problem where the constraints are functional dependencies and the views are created through relational algebra expressions. The problem immediately reduces to the problem of calculating all valid functional dependencies (and other constraints) on a relational algebra expression over relations in the base schema. The problem is undecidable in general but we give a sound and complete algorithm when set difference is omitted from relational algebra.