                                ABSTRACT


==================================================

Title:          Reasoning about Uniqueness Constraints in 
                Object Relational Databases 


Authors:       Vitaliy L. Khizder and Grant E. Weddell 
Emails:        vlkhizde@uwaterloo.ca and gweddell@uwaterloo.ca 
===================================================


Uniqueness constraints such as keys and functional dependencies in the 
relational model are a core concept in information systems technology. 
In this technical report, we identify a boundary between efficient and 
intractable kinds of uniqueness constraints suitable for object relational 
data models. The efficient subclass of the constraints is a strict 
generalization of both keys and relational functional dependencies. We 
present a complete and efficient procedure that solves the membership 
problem for this subclass. To motivate our results, we review some 
applications of our procedure in query optimization and schema evaluation.

In addition, we formulate the problem in terms of a description logic (DL). 
DLs are a family of languages for knowledge representation that have many 
applications in information systems technology. Thus, in addition to 
enhancing earlier work on uniqueness constraints, we integrate the results 
in the larger body of work on DLs.

