The Return of the Entity-Relationship Model: Ontological Query Answering

Andrea Calì, Georg Gottlob, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract / Description of output

The Entity-Relationship (ER) model is a fundamental tool for database design, recently extended and employed in knowledge representation and reasoning due to its expressiveness and comprehensibility. We present an extension of the ER model, called ER +, which is particularly suitable for ontology modeling, as well as being flexible and comprehensible. Our model comprises is-a constraints among entities and relationships, plus functional and mandatory participation constraints. In particular, it allows for arbitrary permutations of the roles in is-a among relationships. We argue that ER-based languages can be profitably used in ontology-enhanced database systems, where queries are evaluated against the union of a database instance and an ontology, which constitute a logical theory. In such systems, the instance has usually large size, therefore ensuring tractable complexity of query answering w.r.t. the instance size is crucial. A key notion that ensures tractability in ER +schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs. We provide a precise syntactic characterization of separable ER +schemata by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under separable ER +schemata, and also under several sublanguages of ER +. We show that the addition of so-called negative constraintsdoes not increase the complexity of query answering. With such constraints, our model properly generalizes the most widely-adopted tractable ontology languages, including those in the well-known DL-Litefamily.
Original languageEnglish
Title of host publicationSemantic Search over the Web
PublisherSpringer Berlin Heidelberg
Number of pages27
ISBN (Electronic)978-3-642-25008-8
ISBN (Print)978-3-642-25007-1
Publication statusPublished - 2012

Publication series

NameData-Centric Systems and Applications
PublisherSpringer Berlin Heidelberg
ISSN (Print)2197-9723


Dive into the research topics of 'The Return of the Entity-Relationship Model: Ontological Query Answering'. Together they form a unique fingerprint.

Cite this