Reasoning over Extended ER Models

Proc. of the 26th Int. Conf. on Conceptual Modeling (ER 2007). Volume 4801 of Lecture Notes in Computer Science. 2007.

We investigate the complexity of reasoning over various fragments of the Extended Entity Relationship (EER) language, which include different combinations of the constructs for ISA between concepts and relationships, disjointness, covering, cardinality constraints, and their refinement. Specifically, we show that reasoning over EER diagrams with ISA between relationships is ExpTime-complete, even when we drop relationship covering. Surprisingly, when we also drop ISA between relations, reasoning becomes NP-complete. If we further remove the Boolean constructors, reasoning becomes polynomial. Our lower bound results are established by means of direct reductions, while the upper bounds follow from correspondences with expressive variants of the description logic DL-Lite. The established correspondence shows also the usefulness of DL-Lite as a language for reasoning over conceptual models and ontologies.

@inproceedings{ER-2007,
   title = "Reasoning over Extended ER Models",
   year = "2007",
   author = "Alessandro Artale and Diego Calvanese and Roman Kontchakov
and Vladislav Ryzhikov and Michael Zakharyaschev",
   booktitle = "Proc. of the 26th Int. Conf. on Conceptual Modeling
(ER 2007)",
   pages = "277--292",
   volume = "4801",
   publisher = "Springer",
   series = "Lecture Notes in Computer Science",
   doi = "10.1007/978-3-540-75563-0_20",
}