Ontology Based Query Answering with Existential Rules

Thomazo, Michael

Ontology Based Query Answering with Existential Rules

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 3245-3245.

Abstract

The aim of my Ph.D thesis is to identify expressive decidable classes, study the complexity of reasoning for these classes, and design efficient algorithms in the sense that they improve state of the art algorithms.

[Abiteboul et al., 1994] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison Wesley, 1994.
[Baader et al., 2007] Franz Baader, Diego Calvanese, Deb- orah McGuinness, Daniele Nardi, and Peter Patel- Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, second edition, 2007.
[Baader, 2003] F. Baader. Terminological cycles in a de- scription logic with existential restrictions. In IJCAI, pages 325-330, 2003. IJCAI
[Baget et al., 2011a] J.-F. Baget, M.-L. Mugnier, S. Rudolph, and M. Thomazo. Walking the Com- plexity Lines for Generalized Guarded Existential Rules. In IJCAI, pages 712-717, 2011. IJCAI
[Baget et al., 2011b] Jean-Franc ¸ois Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On Rules with Ex- istential Variables: Walking the Decidability Line. Artif. Intell., 175(9-10):1620-1654, 2011.
[Calì et al., 2009] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. A General Datalog-Based Framework for Tractable Query Answering over Ontologies. In PODS, pages 77-86. ACM, 2009.
[Calvanese et al., 2007] Diego Calvanese, Giuseppe De Gi- acomo, Domenico Lembo, Maurizio Lenzerini, and Ric- cardo Rosati. Tractable reasoning and efficient query an- swering in description logics: The dl-lite family. J. Autom. Reasoning, 39(3):385-429, 2007.
[Chortaras et al., 2011] Alexandros Chortaras, Despoina Trivela, and Giorgos B. Stamou. Optimized query rewriting for OWL 2 QL. In CADE, pages 192-206, 2011.
[Fagin et al., 2005] R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answer- ing. Theor. Comput. Sci., 336(1):89-124, 2005.
[Gottlob et al., 2011] Georg Gottlob, Giorgio Orsi, and An- dreas Pieris. Ontological queries: Rewriting and optimiza- tion. In ICDE, pages 2-13, 2011.
[Grau et al., 2012] Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, and Zhe Wang. Acyclicity conditions and their application to query answering in description logics. In KR, 2012.
[Kikot et al., 2011] Stanislav Kikot, Roman Kontchakov, and Michael Zakharyaschev. Polynomial conjunctive query rewriting under unary inclusion dependencies. In RR, pages 124-138, 2011.
[König et al., 2012] Mélanie König, Michel Leclère, Marie- Laure Mugnier, and Michaël Thomazo. A sound and com- plete backward chaining algorithm for existential rules. In RR, pages 122-138, 2012.
[Krötzsch and Rudolph, 2011] M. Krötzsch and S. Rudolph. Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. In IJCAI, pages 963-968, 2011. IJCAI
[Marnette, 2009] Bruno Marnette. Generalized schema- mappings: from termination to tractability. In PODS, pages 13-22, 2009.
[Mugnier, 2011] M.-L. Mugnier. Ontological Query An- swering with Existential Rules. In RR, pages 2-23, 2011.
[Pérez-Urbina et al., 2009] Héctor Pérez-Urbina, Ian Hor- rocks, and Boris Motik. Efficient query answering for OWL 2. In International Semantic Web Conference, pages 489-504, 2009.
[Rosati and Almatelli, 2010] Riccardo Rosati and Alessan- dro Almatelli. Improving query answering over dl-lite on- tologies. In KR, 2010.
[Thomazo et al., 2012] Michaël Thomazo, Jean-Franc ¸ois Baget, Marie-Laure Mugnier, and Sebastian Rudolph. A generic querying algorithm for greedy sets of existential rules. In KR, 2012.
[Thomazo, 2012] Michaël Thomazo. From el to tractable ex- istential rules with complex role inclusions. In Description Logics, 2012.
[Thomazo, 2013] M. Thomazo. Compact rewriting for exis- tential rules. In IJCAI, 2013.
[Venetis et al., 2012] Tassos Venetis, Giorgos Stoilos, and Giorgos B. Stamou. Incremental query rewriting for OWL 2 QL. In Description Logics, 2012.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 Framework and objectives

Ontology-Based Query Answering (OBQA) is currently a problem that receives a lot of attention both from knowledge representation and databases communities. The aim is to answer queries that are at least as expressive as conjunctive queries while taking an ontology into account. This is important in order to improve the quality of query answering and interoperability between different sources of data.

The mainstream formalism to deal with ontologies is description logics (DLs) ([Baader et al., 2007]). While historical DLs are very expressive, most of the OBQA research focus on recently introduced lightweight DLs (EL [Baader, 2003] and DL-Lite [Calvanese et al., 2007]). Real-world ontologies expressed in these DLs already exist, such as the medical ontology SNOMED-CT (based on EL).

from F F, this materialization yields a finite fact entailing all possible consequence of F and R, R is called a finite expansion set (fes). When this fact is not finite, but has a bounded treewidth, R is said a bounded treewidth set (bts) 2 . Both conditions ensures decidability of OBQA, but none are recognizable. Non-materializing algorithms perform query rewriting: the initial query Q is rewritten into a query Q′ , such that Q is entailed by F,R iff Q′ is entailed by F. When Q′ is a finite union of conjunctive queries (UCQs), R is said a finite unification set (fus). Rules translating DL-Lite ontologies are both bts and fus, while rules translating EL are only bts.

During my Ph.D, I am considering an alternative, rulebased formalism. I use existential rules [Baget et al., 2011b] (rules for short, also known as Tuple Generating Dependencies [Abiteboul et al., 1994], Datalog+/- [Cal`ı et al., 2009]), which despite their simple syntactic form are very expressive. Moreover, they allow for a smooth integration to database systems since, in contrast to DLs, they allow for any predicate arity and support variable cycles. Indeed, their form is:

Formula not decoded

where B (resp. H) is an arbitrary conjunction of atoms called the body (resp. the head) of the rule. The OBQA problem is thus formalized as follows: given two facts (existentially closed conjunctions of atoms) F and Q, a set of rules R, does F, R |= Q hold? (where |= denotes logical entailment). However, the ability to create new unknown individuals, via existentially quantified variables, makes reasoning extremely complex: the OBQA problem is undecidable, even with a single rule with a single binary predicate ([Baget et al., 2011b]). A lot of work has been done in the last years in order to define decidable classes of rules, aiming at a good tradeoff between expressivity and complexity. The interested reader can consult [Mugnier, 2011] for a survey of such classes. Some of these class cover the lightweight DLs used for OBQA 1 .

Algorithms for OBQA can be split in two big categories: either they materialize, that is, they use R to infer new data The aim of my Ph.D thesis is to identify expressive decidable classes, study the complexity of reasoning for these classes, and design efficient algorithms in the sense that they improve state of the art algorithms.

1 Constraints and equality rules are also needed, but this is out of the scope of this summary.

2 Contributions

In my Ph.D work, I consider both materialization-based and query rewriting approaches. Natural brute-force algorithms exist for fes and fus, but no such algorithm is known for bts. In a joint work with J.-F. Baget, M.-L. Mugnier and S. Rudolph, we have defined an abstract class, named greedy bounded treewidth set (gbts) and provided a worst-case optimal algorithm for it. This class is a subset of bts that covers most of the known recognizable bts classes of rules. Slight adaptation of this algorithm makes it also optimal for these subclasses. This work has been published in [Baget et al., 2011a; Thomazo et al., 2012; Thomazo, 2012].

Pure query rewriting approaches suffer from the exponential blow-up of the size of rewritings w.r.t. to the query, even with solely class or role hierarchies. UCQs are then too large to be efficiently dealt with by RDMS. In [K¨onig et al., 2012], we show that this is inherent to UCQs by characterizing the smallest rewriting using that shape of formulas. In [Thomazo, 2013], I use semi-conjunctive queries, which are a more general form of positive existential formula. I present an algorithm for computing such rewritings, and experimentally evaluate their quality by checking the efficiency of evaluation of such queries. First results show that this approach is more efficient than using UCQs.

2 See [Baget et al., 2011b] for formal definition of these classes.

3 Related work

Recognizability of set of rules suited for a materializationbased approach relies on two main criteria: guardedness and acyclicity. Guarded rules (where an atom of the body contains all variables of the body) have been generalized in several ways [Cal`ı et al., 2009; Baget et al., 2011b; Kr¨otzsch and Rudolph, 2011].

Weak-acyclicity [Fagin et al., 2005] has been generalized into super-weak acyclicity [Marnette, 2009] and join acyclicity [Kr¨otzsch and Rudolph, 2011]. An incomparable notion relies on the notion of rule dependency [Baget et al., 2011b]. [Grau et al., 2012] proposes a semantic condition of acyclicity that generalizes all these notions.

Last, the combined approach mixes materialization and query rewriting: it both extends the data by applying rules (independently of the query) and rewrite the queries with respect to the rules (independently of the data). This has proven to be useful for both DL-Lite and EL ontologies.

Query rewriting approaches are applicable in particular to linear [Cal`ı et al., 2009; Baget et al., 2011b] and sticky [Gottlob et al., 2011] rules, which are fus. Several algorithms have been implemented for linear rules or DL-Lite ontologies, rewriting either into a union of conjunctive queries ([P´erezUrbina et al., 2009; Gottlob et al., 2011; Venetis et al., 2012; Chortaras et al., 2011]) or into a Datalog program (Presto [Rosati and Almatelli, 2010]). All fus are processed by the algorithm presented in [K¨onig et al., 2012]. The question of finding polynomial cases has also been addressed [Kikot et al., 2011].

Michael Thomazo. 2013. Ontology Based Query Answering with Existential Rules. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 3245–3245. https://ijcai.org/proceedings/2013/509

@inproceedings{ijcai2013p509,
  title     = {Ontology Based Query Answering with Existential Rules},
  author    = {Thomazo, Michael},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {3245--3245},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/509},
}

TY  - CPAPER
TI  - Ontology Based Query Answering with Existential Rules
AU  - Thomazo, Michael
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 3245
EP  - 3245
UR  - https://ijcai.org/proceedings/2013/509
ER  -

[1] [Abiteboul et al., 1994] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison Wesley, 1994.

[2] [Baader et al., 2007] Franz Baader, Diego Calvanese, Deb- orah McGuinness, Daniele Nardi, and Peter Patel- Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, second edition, 2007.

[3] [Baader, 2003] F. Baader. Terminological cycles in a de- scription logic with existential restrictions. In IJCAI, pages 325-330, 2003. IJCAI

[4] [Baget et al., 2011a] J.-F. Baget, M.-L. Mugnier, S. Rudolph, and M. Thomazo. Walking the Com- plexity Lines for Generalized Guarded Existential Rules. In IJCAI, pages 712-717, 2011. IJCAI

[5] [Baget et al., 2011b] Jean-Franc ¸ois Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On Rules with Ex- istential Variables: Walking the Decidability Line. Artif. Intell., 175(9-10):1620-1654, 2011.

[6] [Calì et al., 2009] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. A General Datalog-Based Framework for Tractable Query Answering over Ontologies. In PODS, pages 77-86. ACM, 2009.

[7] [Calvanese et al., 2007] Diego Calvanese, Giuseppe De Gi- acomo, Domenico Lembo, Maurizio Lenzerini, and Ric- cardo Rosati. Tractable reasoning and efficient query an- swering in description logics: The dl-lite family. J. Autom. Reasoning, 39(3):385-429, 2007.

[8] [Chortaras et al., 2011] Alexandros Chortaras, Despoina Trivela, and Giorgos B. Stamou. Optimized query rewriting for OWL 2 QL. In CADE, pages 192-206, 2011.

[9] [Fagin et al., 2005] R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answer- ing. Theor. Comput. Sci., 336(1):89-124, 2005.

[10] [Gottlob et al., 2011] Georg Gottlob, Giorgio Orsi, and An- dreas Pieris. Ontological queries: Rewriting and optimiza- tion. In ICDE, pages 2-13, 2011.

[11] [Grau et al., 2012] Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, and Zhe Wang. Acyclicity conditions and their application to query answering in description logics. In KR, 2012.

[12] [Kikot et al., 2011] Stanislav Kikot, Roman Kontchakov, and Michael Zakharyaschev. Polynomial conjunctive query rewriting under unary inclusion dependencies. In RR, pages 124-138, 2011.

[13] [König et al., 2012] Mélanie König, Michel Leclère, Marie- Laure Mugnier, and Michaël Thomazo. A sound and com- plete backward chaining algorithm for existential rules. In RR, pages 122-138, 2012.

[14] [Krötzsch and Rudolph, 2011] M. Krötzsch and S. Rudolph. Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. In IJCAI, pages 963-968, 2011. IJCAI

[15] [Marnette, 2009] Bruno Marnette. Generalized schema- mappings: from termination to tractability. In PODS, pages 13-22, 2009.

[16] [Mugnier, 2011] M.-L. Mugnier. Ontological Query An- swering with Existential Rules. In RR, pages 2-23, 2011.

[17] [Pérez-Urbina et al., 2009] Héctor Pérez-Urbina, Ian Hor- rocks, and Boris Motik. Efficient query answering for OWL 2. In International Semantic Web Conference, pages 489-504, 2009.

[18] [Rosati and Almatelli, 2010] Riccardo Rosati and Alessan- dro Almatelli. Improving query answering over dl-lite on- tologies. In KR, 2010.

[19] [Thomazo et al., 2012] Michaël Thomazo, Jean-Franc ¸ois Baget, Marie-Laure Mugnier, and Sebastian Rudolph. A generic querying algorithm for greedy sets of existential rules. In KR, 2012.

[20] [Thomazo, 2012] Michaël Thomazo. From el to tractable ex- istential rules with complex role inclusions. In Description Logics, 2012.

[21] [Thomazo, 2013] M. Thomazo. Compact rewriting for exis- tential rules. In IJCAI, 2013.

[22] [Venetis et al., 2012] Tassos Venetis, Giorgos Stoilos, and Giorgos B. Stamou. Incremental query rewriting for OWL 2 QL. In Description Logics, 2012.