Sound, Complete and Minimal UCQ-Rewriting for Existential Rules

Tracking #: 652-1862

Authors: 
Melanie Konig
Michel Leclere
Marie-Laure Mugnier
Michaël Thomazo

Responsible editor: 
Guest Editors RR2013 Special Issue

Submission type: 
Full Paper
Abstract: 
We address the issue of Ontology-Based Data Access, with ontologies represented in the framework of existential rules, also known as Datalog. A wellknown approach involves rewriting the query using ontological knowledge. We focus here on the basic rewriting technique which consists of rewriting the initial query into a union of conjunctive queries. First, we study a generic breadth-first rewriting algorithm, which takes any rewriting operator as a parameter, and define properties of rewriting operators that ensure the correctness of the algorithm. Then, we focus on piece-unifiers, which provide a rewriting operator with the desired properties. Finally, we propose an implementation of this framework and report some experiments.
Full PDF Version: 
Tags: 
Reviewed

Decision/Status: 
Accept

Solicited Reviews:
Click to Expand/Collapse
Review #1
By Stijn Heymans submitted on 22/Apr/2014
Suggestion:
Accept
Review Comment:

Thanks a lot for the very detailed comments on the first review round. I carefully checked your rebuttal as well as the changes applied and have no further issues with this paper. A clear accept from my side.

Review #2
Anonymous submitted on 26/Apr/2014
Suggestion:
Accept
Review Comment:

The paper has been improved and can be accepted. Some minor (mostly linguistic) remarks are listed below.

p 2, Example 1: Q = \exists y play (x,y) is rather confusing -- on the one hand, the query has an answer variable (x), which is not listed as an argument of Q; on the other hand, the authors prefer to omit the quantifiers altogether in the rest of the paper. One can suggest to use Q(x) (and respectively, Q'(x)) in Example 1.

p 2, Example 1: font usage for movie, play, actor should be unified

p 3, above Paper contributions: what is the precise reference in [RK13] (i.e., theorem number)?

p 4, after the 3 items: "Moreover, if we delete ... then we obtain"

p 5, Example 5: the use of quantifiers in queries is rather confusing again --- Q has some, but Q_1 does not

p 5, Example 5: "despite Q being not"

p 5, par 5: "When additionally the head of a rule R"

p 5, par 6: "fewer queries"

p 6, par 2: "denote its sets of variables, constants and terms, respectively"

p 6, Def 1: noted -> denoted

p 6, after Def 1: quantifiers are omitted not only in rule, but also in CQs

p 7, Example 3: "and consider the following preorder"

p 8, Example 4: it seems that one rule R_1 is enough to active the effect; perhaps, it is also worth pointing out that R_1 is not fus

p 8, proof of Th 1: the cardinalities of covers, strictly speaking, are not smaller -- they do not exceed cardinalities of the rewriting sets

p 8, footnote 3: "f.i." -> "e.g.," or "for instance,"

p 9: the elements of rew(Q,R) are not just some queries, they are BCQs (also, the terminology should be consistent throughout the section)

p 9, Def 7: just a suggestion to use rew_{\leq k} for W_k --- otherwise, there are too many symbols with similar meanings

p 10, Def 8: sentences should not begin with a formula -- one could use, for example, "A rewriting operator rew is said to be prunable if …"

p 11, proof of Property 5: there is no need to repeat the 4 invariants in the proof

p 12, above Property 6: "owns a finite cover" -> "has a finite cover"

p 12, proof of Property 6: "proved by straightforward induction"

p 13, proof of Property 9: "we are sure that" -> "we obtain"

p 13, proof of Theorem 10: "We conclude with" -> "The claim then follows from"

p 14, Def 11: "satisfying the following three conditions"

p 19, Example 8, last line: remove "so"

p 19, Example 9: it is not clear why there is an "e.g." after "yields"

p 21, Def 15: Given such *a* compatible

p 26, par 2: "if a rule R has an atomic head then every atom in Q..."

p 27, last line of Sec 7.2: "hereafter" -> "below"

pp 29 and 31: Tables 2 and 4 use "Base" for an ontology -- why? set of rules might be better (but it is certainly not a knowledge base)

p 30, line -5: "being less" (no of)

p 31, Table 4: runtime in ms?

p 31, Table 4: 0ms looks a bit strange -- the timing for rapid presumably included JVM startup time, parsing, etc.; and it is hard to believe that that could be done instantaneously for PURE... by the way, is PURE an abbreviation? Is it available to download?

p 32: [CGL12] is a journal version of [CGL09]

pp 32-33: abbreviate names in [CLR03], [OP11], [VSS14] (and check publication titles)

Review #3
By Giorgio Orsi submitted on 08/May/2014
Suggestion:
Minor Revision
Review Comment:

The paper has been improved substantially in this revision and I believe that it can now be accepted.

There are still issues that can be addressed in the camera-ready version of the paper. In particular:

- Page 3, before contributions, on the equivalence of fus and FO-rewritability. The equivalence of fus and fo-rewritability is not proven in RK13. On this point, RK13 states only that: “First-order rewritable sets of TGDs are also called finite unification sets” (that I find incorrect anyway) citing the paper “J.F. Baget, M. Leclère, M.-L. Mugnier, and E. Salvat. On rules with existential variables: Walking the decidability line. Artificial Intelligence, 175(9–10):1620–1654, 2011.” Where also no proof is given. Since these two are different notions, if a proof is available somewhere else, please cite it or rephrase the statements with “It is believed that fus and fo-rewritability are equivalent notions.”

- Page 4: 3rd paragraph. The authors state that removing redundant atoms from the obtained CQs can be performed by a linear number of homomorphism tests. Can you explain this better? It seems to me that all possible subsets of atoms have to be considered in order to minimise the query. Also this would be a good place to reference that this job can be done via, e.g., the Chase&Backchase procedure (and its optimisations).

- Page 7, after Definition 4. I still believe that here is a good place to clarify that this notion of minimality refers only to the cardinality of the set and it is different from the notion of query minimisation under constraints where algorithms like the Chase&Backchase can be used.

Minor / Cosmetics:

- Page 2, line 1: […] for general existential rules. —> Please add a citation here.

- Page 2, end of first paragraph: rephrase the paragraph the last line.

- Page 26, Property 23: […] for all atom […] —> for all atoms

- Page 29 (and other places): Explorated —> Explored