Tractable Query Answering over Conceptual Schemata

Andrea Calì, Georg Gottlob, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We address the problem of answering conjunctive queries over extended Entity-Relationship schemata, which we call EER (Extended ER) schemata, with is-a among entities and relationships, and cardinality constraints. This is a common setting in conceptual data modelling, where reasoning over incomplete data with respect to a knowledge base is required. We adopt a semantics for EER schemata based on their relational representation. We identify a wide class of EER schemata for which query answering is tractable in data complexity; the crucial condition for tractability is the separability between maximum-cardinality constraints (represented as key constraints in relational form) and the other constraints. We provide, by means of a graph-based representation, a syntactic condition for separability: we show that our conditions is not only sufficient, but also necessary, thus precisely identifying the class of separable schemata. We present an algorithm, based on query rewriting, that is capable of dealing with such EER schemata, while achieving tractability. We show that further negative constraints can be added to the EER formalism, while still keeping query answering tractable. We show that our formalism is general enough to properly generalise the most widely adopted knowledge representation languages.
Original languageEnglish
Title of host publicationConceptual Modeling - ER 2009, 28th International Conference on Conceptual Modeling, Gramado, Brazil, November 9-12, 2009. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-642-04840-1
ISBN (Print)978-3-642-04839-5
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science (LNCS)
Publisher Springer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Tractable Query Answering over Conceptual Schemata'. Together they form a unique fingerprint.

Cite this