TY - GEN
T1 - Query Answering under Expressive Entity-Relationship Schemata
AU - Calì, Andrea
AU - Gottlob, Georg
AU - Pieris, Andreas
PY - 2010
Y1 - 2010
N2 - 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 ER + model, comprises is-a constraints among entities and relationships, plus functional and mandatory participation constraints. In particular, it allows arbitrary permutations of the roles in is-a among relationships. A key notion that ensures high tractability in ER + schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs of ER + .We provide a precise syntactic characterization of separable ER + schemata, called ER± schemata, by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under ER± schemata. 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.
AB - 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 ER + model, comprises is-a constraints among entities and relationships, plus functional and mandatory participation constraints. In particular, it allows arbitrary permutations of the roles in is-a among relationships. A key notion that ensures high tractability in ER + schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs of ER + .We provide a precise syntactic characterization of separable ER + schemata, called ER± schemata, by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under ER± schemata. 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.
U2 - 10.1007/978-3-642-16373-9_25
DO - 10.1007/978-3-642-16373-9_25
M3 - Conference contribution
SN - 978-3-642-16372-2
T3 - Lecture Notes in Computer Science (LNCS)
SP - 347
EP - 361
BT - Conceptual Modeling - ER 2010, 29th International Conference on Conceptual Modeling, Vancouver, BC, Canada, November 1-4, 2010. Proceedings
PB - Springer Berlin Heidelberg
ER -