Datalog±: A Unified Approach to Ontologies and Integrity Constraints
Authors
- Andrea Calì (University of Oxford, United Kingdom)
- Georg Gottlob (University of Oxford, United Kingdom)
- Thomas Lukasiewicz (University of Oxford, United Kingdom)
Abstract
We report on a recently introduced family of expressive extensions of Datalog, called Datalog±, which is a new framework for representing ontological axioms in form of integrity constraints, and for query answering under such constraints. Datalog± is derived from Datalog by allowing existentially quantified variables in rule heads, and by enforcing suitable properties in rule bodies, to ensure decidable and efficient query answering. We first present different languages in the Datalog± family, providing tight complexity bounds for all cases but one (where we have a low complexity AC0 upper bound). We then show that such languages are general enough to capture the most common tractable ontology languages. In particular, we show that the DL-Lite family of description logics and F-Logic Lite are expressible in Datalog±. We finally show how stratified negation can be added to Datalog± while keeping ontology querying tractable in the data complexity. Datalog± is a natural and very general framework that can be successfully employed in different contexts such as data integration and exchange. This survey mainly summarizes two recent papers.
About the Speaker
Georg Gottlob (University of Oxford, United Kingdom)
Georg Gottlob is a Professor of Computing Science at Oxford University and a Fellow of St Anne's College.
His interests include data extraction, data exchange, algorithms for semistructured data and xml processing, database theory, algorithms for games and auctions, graph or hypergraph based algorithms for problem decomposition, knowledge representation and reasoning, complexity in ai and logic programming complexity theory finite model theory, and complexity computational.
His current research deals with database theory, query languages, data exchange, and with graph-theoretic problem decomposition methods that can be used for recognizing large classes of tractable instances of hard problems. The latter methods have applications in query optimization, in constraint satisfaction, and in game theory and electronic commerce (e.g. winner determination in combinatorial auctions). Georg Gottlob is a founding member of the recently established Oxford-Man Institute of Quantitative Finance.