Summary. We consider a semantic class, weakly-chase-sticky (WChS), and a syntactic subclass, jointly-weakly-sticky (JWS), of Datalog± programs. Both extend that of weakly-sticky (WS) programs, which appear in our applications to data quality. For WChS programs we propose a practical, polynomial-time query answering algorithm (QAA). We establish that the two classes are closed under magic-sets rewritings. As a consequence, QAA can be applied to the optimized programs. QAA takes as inputs the program (including the query) and semantic information about the “finiteness” of predicate positions. For the syntactic subclasses JWS and WS of WChS, this additional information is computable. Datalog± . Datalog, a rule-based language for query and view-definition in relational databases [5], is not expressive enough to logically represent interesting and useful ontologies, at least of the kind needed to specify conceptual data models. Datalog± extends Datalog by allowing existentially quantified variables in rule heads (∃-variables), equality atoms in rule heads, and program constraints [2]. Hence the “+” in Datalog± , while the “−” reflects syntactic restrictions on programs, for better computational properties. A typical Datalog± program, P , is a finite set of rules, Σ ∪ E ∪ N , and an extensional database (finite set of facts), D. The rules in Σ are tuple-generatingdependencies (tgds) of the form ∃x¯P (x¯, x¯′) ← P1(x¯1), . . . , Pn(x¯n), where x¯′ ⊆ S x¯i, and x¯ can be empty. E is a set of equality-generating-dependencies (egds) of the form x = x′ ← P1(x¯1), . . . , Pn(x¯n), with {x, x′} ⊆ S x¯i. Finally, N contains negative constraints of the form ⊥ ← P1(x¯1), . . . , Pn(x¯n), where ⊥ is false. Example 1. The following Datalog± program shows a tgd, an egd, and a negative constraint, in this order: ∃x Assist (y, x) ← Doctor (y); x = x′ ← Assist (y, x), Assist (y, x′); ⊥ ← Specialist (y, x, z), Nurse(y, z).
Below, when we refer to a class of Datalog± programs, we consider only Σ, the
tgds. Due to different syntactic restrictions, Datalog± can be seen as a class
of sublanguages of Datalog∃ , which is the extension of Datalog with tgds with
∃-variables [
The rules of a Datalog± program can be seen as an ontology O on top of
D, which can be incomplete. O plays the role of: (a) a “query layer” for D,
providing ontology-based data access (OBDA) [
The answers to a conjunctive query Q(x¯) from D wrt. Σ is a sequence of
constants a¯, such that Σ ∪D |= Q(a¯) (or yes or no in case Q is boolean). The answers
can be obtained by querying as usual the universal instance chase(Σ, D). The
chase may be infinite, which leads, in some cases, to undecidability of query
answering [
Sticky programs [
For QA, sticky programs enjoy first-order rewritability [
Stickiness of the Chase. In addition to (syntactic) stickiness, there is a
“semantic” property of programs, which is relative to the chase (and the data,
D), and is called “chase-stickiness” (ChS). Stickiness implies semantic stickiness
(but not necessarily the other way around) [
Intuitively, a program has the chase-stickiness property if, due to the
application of a tgd σ: When a value replaces a repeated variable in the body of a
rule, then that value also appears in all the head atoms obtained through the
iterative enforcement of applicable rules that starts with σ. So, that value is
propagated all the way down through all the possible subsequent steps.
a
a
1 A position refers to a predicate attribute, e.g. Nurse[
Weak-Stickiness of the Chase. Weak-stickiness also has a semantic version, called “weak-chase-stickiness” (WChS); which is implied by the former. So as for chase-stickiness, weak-chase-sticky programs have a tractable QA problem, even with a possibly infinite chase. This class is one of the two we introduce and investigate. They appear in double-edged boxes in Figure 2, with dashed edges indicating a semantic class.
By definition, weak-chase-stickiness is obtained by relaxing the condition for ChS: it applies only to values for repeated variables in the body of σ that appear in so-called infinite positions, which are semantically defined. A position is infinite if there is an instance D for which an unlimited number of different values appear in Chase(Σ, D).
Given a program, deciding if a position is infinite is unsolvable, so as
deciding in general if the chase terminates. Consequently, it is also undecidable if
a program is WChS. However, there are syntactic conditions on programs [
Finite Positions and Program Classes. In principle, any set-valued function S that, given a program, returns a subset of the program’s finite positions can be used to define a subclass WChS(S) of WChS. This is done by applying the definition of WChS above with “infinite positions” replaced by “non-S-finite positions”. Every class WChS(S) has a tractable QA problem.
S could be computable on the basis of the program syntax or not. In the former case, it would be a “syntactic class”. Class WChS (S) grows monotonically with S in the sense that if S1 ⊆ S2 (i.e. S1 always returns a subset of the positions returned by S2), then WChS (S1) ⊆ WChS (S2). In general, the more finite positions are (correctly) identified (and the consequently, the less finite positions are treated as infinite), the more general the subclass of WChS that is identified or characterized.
For example, the function S⊥ that always returns an empty set of finite
positions, WChS (S⊥) is the class of sticky programs, because stickiness must hold
no matter what the (in)finite positions are. At the other extreme, for function
S⊤ that returns all the (semantically) finite positions, WChS (S⊤) becomes the
class WChS. (As mentioned above, S⊤ is in general uncomputable.) Now, if
Srank returns the set of finite-rank positions (for a program P, usually denoted
by ΠF (P) [
Joint-Weakly-Stickiness. The joint-weakly-sticky (JWS) programs we
introduce form a syntactic class strictly between WS and WChS. Its definition appeals
to the notions of joint-acyclicity and existential dependency graphs introduced
in [
If Sext denotes the function that specifies finite positions on the basis of the
existential dependency graphs (EDG), implicitly defined in [
The customized algorithm ALS is guaranteed to be sound and complete only when applied to programs in WChS (S): ALS(Σ, D, Q) returns all and only the query answers. (Actually, ALS is still sound for any program in WChS.) ALS runs in polynomial-time in data; and can be applied to both the WS and the JWS syntactic classes. For them the finite-position functions are computable.
ALS is based on the concepts of parsimonious chase (pChase) and freezing
nulls, as used for QA with shy Datalog, a fragment of Datalog∃ [
Query answering with shy programs has a first phase where the pChase runs
until termination (which it does). In a second phase, the pChase iteratively
resumes for a number of times that depends on the number of distinct ∃-variables in
the query. This second phase is required to properly deal with joins in the query.
Our QAA for WChS programs (AL) is similar, it has the same two phases, but a
pChase step is modified: after every application of a pChase step that generates
nulls, the latter that appear in S-finite positions are immediately frozen.
Magic-Sets Rewriting. It turns out that JWS, as opposed to WS, is closed
under the quite general magic-set rewriting method [
non-terminating
chase weakly-stickyjoin (WSJ) joint-weaklysticky (JWS) weakly-sticky (WS) terminating
chase joint-acyclic
(JA) weakly-acyclic (WA) consequence, AL can be applied to both the original JWS program and its magic rewriting. (Actually, this also holds for the superclass WChS.)
It can be proved that (our modification of) the magic-sets rewriting method
in [
Acknowledgments: We are very grateful to Mario Alviano and the DLV team for providing us with information and support in relation to existential Datalog. We also appreciate useful conversations with Andrea Cali and Andreas Pieris on Datalog±, and important comments from Andrea Cali on an earlier version of this paper.