Adding inclusion dependencies to an object-oriented data model with uniqueness constraints

We study an object-oriented data model that allows to express both uniqueness constraints and inclusion dependencies as semantic constraints. The data model is based on a subset of F-logic. Uniqueness constraints comprise path functional dependencies which generalise functional dependencies and reflect the navigational power of object-oriented query languages. As inclusion dependencies, we consider explicit class inclusion constraints, besides inclusions required by class hierarchies, and onto constraints that enforce reachability of objects. For these classes of semantic constraints we present an axiomatisation and prove its inference rules to be correct and complete with respect to general logical implication, leaving the decision problem open. The completeness proof combines the known construction for path functional dependencies alone with a possibly infinite model generation process to enforce onto constraints. The results prepare the grounds for normal forms in object-oriented data models and subsequently for computer aided object-oriented database design, following the decomposition approach for the relational data model. Beyond the application for schema design, the achievements could also be exploited for related tasks like semantic query optimisation and mediated data integration within a variety of graph based data models. Received: 11 October 2000 / 27 January 2003