Complexity of Reasoning in Entity Relationship Models

Alessandro Artale, Diego Calvanese, Roman Kontchakov, Vladislav Ryzhikov, and Michael Zakharyaschev

Technical Report, Faculty of Computer Science, Free University of Bozen-Bolzano. Technical report 2007. Full version of a paper published in the Proc. of the 20th Int. Workshop on Description Logics (DL 2007).

We investigate the complexity of reasoning over various fragments of the Extended Entity-Relationship (EER) language, which include different combinations of the constructors 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 both covering and disjointness for relationships. Surprisingly, when we also drop ISA between relations, reasoning becomes NP-complete. If we further remove the possibility to express covering between entities, reasoning becomes polynomial. Our lower bound results are established by 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.


@techreport{DL-2007-er-full,
   title = "Complexity of Reasoning in Entity Relationship Models",
   year = "2007",
   author = "Alessandro Artale and Diego Calvanese and Roman Kontchakov
and Vladislav Ryzhikov and Michael Zakharyaschev",
   institution = "Faculty of Computer Science, Free University of
Bozen-Bolzano",
   note = "Full version of a paper published in the Proc. of the 20th Int.
Workshop on Description Logics (DL 2007)",
}
pdf