Authors: Andrea Calì, Andreas Pieris, Georg Gottlob
Tags: 2012, conceptual modeling
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 address the problem of answering conjunctive queries under constraints representing schemata expressed in an extended version of the Entity–Relationship model. This extended model, called , 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. A key notion that ensures high tractability in schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs of . We provide a precise syntactic characterization of separable schemata by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under separable schemata, and also under several sublanguages of . We show that the addition of so-called negative constraints does 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 DL-Lite family.Read the full paper here: https://www.journals.elsevier.com/information-systems
