## On the Interaction between ISA and Cardinality Constraints

**Diego Calvanese and Maurizio Lenzerini**
*Proc. of the 10th IEEE Int. Conf. on Data Engineering (ICDE
1994).* 1994.

ISA and cardinality constraints are among the most interesting
types of constraints in data models. ISA constraints are used to
establish several forms of containment among classes, and are
receiving great attention in moving to object-oriented data models,
where classes are organized in hierarchies based on a
generalization/specialization principle. Cardinality constraints
impose restrictions on the number of links of a certain type
involving every instance of a given class, and can be used for
representing several forms of dependencies beteewn classes,
including functional and existence dependencies. While the formal
properties of each type of constraints are now well understood,
little is known of their interaction. The goal of this paper is to
present an effective method for reasoning about a set of ISA and
cardinality constraints in the context of a simple data model based
on the notions of classes and relationships. In particular, the
method allows one both to verify the satisfiability of a schema and
to check whether a schema implies a given constraint of any of the
two kinds. We prove that the method is sound and complete, thus
showing that the reasoning problem for ISA and cardinality
constraints is decidable.

@inproceedings{ICDE-1994,
title = "On the Interaction between ISA and Cardinality Constraints",
year = "1994",
author = "Diego Calvanese and Maurizio Lenzerini",
booktitle = "Proc. of the 10th IEEE Int. Conf. on Data Engineering
(ICDE 1994)",
pages = "204--213",
publisher = "IEEE Computer Society Press",
doi = "10.1109/ICDE.1994.283032",
}

ps.gz
pdf