On the satisfiability of dependency constraints in entity-relationship schemata

摘要

The satisfiability problem for a specific class of integrity constraints in data bases, namely the dependency constraints, is studied. An entity-relationship model is used for expressing data schemata. In this model suitable types of dependency constraints, called cardinality ratio constraints, allow one to impose restrictions on the mappings between entities and relationships. We show that, as far as such a class of constraints is concerned, the usual notion of satisfiability is not sufficiently meaningful. For this reason we introduce the notion of strong satisfiability, ensuring that no entity or relationship is compelled to be empty in all of the legal instances of the schema. We propose to model the cardinality ratio constraints of a schema by means of a suitable linear inequality system and we show that a schema is strongly satisfiable if and only if the associated system admits positive solutions. Furthermore, we describe a method for discovering which are the sets of constraints that prevent a schema from being strongly satisfiable.