Ontologies are a fundamental component of the Semantic Web since they provide a formal and machine manipulable model of a domain. Description Logics (DLs) are often the languages of choice for modeling ontologies. Great e ort has been spent in identifying decidable or even tractable fragments of DLs. Conversely, for knowledge representation and reasoning, integration with rules and rule-based reasoning is crucial in the so-called Semantic Web stack vision. Datalog is an extension of Datalog which can be used for representing lightweight ontologies, and is able to express the DL-Lite family of ontology languages, with tractable query answering under certain language restrictions. In this work, we show that Abductive Logic Programming (ALP) is also a suitable framework for representing Datalog ontologies, supporting query answering through an abductive proof procedure, and smoothly achieving the integration of ontologies and rulebased reasoning. In particular, we consider an Abductive Logic Programming framework named SCIFF and derived from the IFF abductive framework, able to deal with existentially (and universally) quanti ed variables in rule heads, and Constraint Logic Programming constraints. Forward and backward reasoning is naturally supported in the ALP framework. We show that the SCIFF language smoothly supports the integration of rules, expressed in a Logic Programming language, with Datalog ontologies, mapped into SCIFF (forward) integrity constraints.
The main idea of the Semantic Web is making information available in a form that
is understandable and automatically manageable by machines
In order to realize this vision, the W3C has supported the development of a family of knowledge representation formalisms of increasing complexity for de ning ontologies, called Web Ontology Language (OWL). In particular, OWL 1 de nes the sublanguages OWL-Lite, OWL-DL (based on Description Logics) and OWLFull. Therefore, ontologies are a fundamental component of the Semantic Web and Description Logics (DLs) are often the languages of choice for modeling them.
Extensive work has focused on developing tractable DLs, identifying the DL-Lite
family
In a related research direction, Cal et al. (2009b) proposed Datalog , an
extension of Datalog with existential rules for de ning ontologies. Datalog can be used
for representing lightweight ontologies, and encompasses the DL-Lite family
In this work, we consider the Datalog language and show how ontologies
expressed in this language can be also modeled in an Abductive Logic Programming
(ALP, for short) framework
Here we concentrate on Datalog ontologies, and show how an ALP language enriched with quanti ed variables (existential to our purposes) can be a useful knowledge representation and reasoning framework for them. We do not focus here on complexity results of the overall system, which is, however, not tractable.
Forward and backward reasoning is naturally supported by the ALP proof
procedure, and the considered SCIFF language smoothly supports the integration of
rules, expressed in a Logic Programming language, with ontologies expressed in
Datalog . In fact, In fact, SCIFF allows us to map Datalog ontologies into the
forward integrity constraints on which it is based. Other ALP languages could be
used
In the following, Section 2 introduces Datalog . Section 3 introduces Abductive Logic Programming, and the SCIFF language. Section 4 shows how the considered Datalog language can be mapped into SCIFF. Section 5 concludes the paper, and outlines future work.
Datalog extends Datalog by allowing existential quanti ers, the equality predicate
and the truth constant false in rule heads. Datalog can be used for representing
lightweight ontologies and is able to express the DL-Lite family of ontology
languages
In order to describe Datalog , let us assume (i) an in nite set of data constants , (ii) an in nite set of labeled nulls N (used as \fresh" Skolem terms), and (iii) an in nite set of variables V . Di erent constants represent di erent values (unique name assumption), while di erent nulls may represent the same value. We assume a lexicographic order on [ N , with every symbol in N following all symbols in . We denote by X vectors of variables X1; : : : ; Xk with k 0. A relational schema R is a nite set of relation names (or predicates). A term t is a constant, null or variable. An atomic formula (or atom) has the form p(t1; : : : ; tn ), where p is an nary predicate, and t1; : : : ; tn are terms. A database D for R is a possibly in nite set of atoms with predicates from R and arguments from [ N . A conjunctive query (CQ) over R has the form q (X) = 9Y (X; Y), where (X; Y) is a conjunction of atoms having as arguments variables X and Y and constants (but no nulls). A Boolean CQ (BCQ) over R is a CQ having head predicate q of arity 0 (i.e., no variables in X).
We often write a BCQ as the set of all its atoms, having constants and variables as arguments, and omitting the quanti ers. Answers to CQs and BCQs are de ned via homomorphisms, which are mappings : [ N [ V ! [ N [ V such that (i) c 2 implies (c) = c, (ii) c 2 N implies (c) 2 [ N , and (iii) is naturally extended to term vectors, atoms, sets of atoms, and conjunctions of atoms. The set of all answers to a CQ q (X) = 9Y (X; Y) over a database D , denoted q (D ), is the set of all tuples t over for which there exists a homomorphism : X [ Y ! [ N such that ( (X; Y)) D and (X) = t. The answer to a BCQ q = 9Y (Y) over a database D , denoted q (D ), is Yes, denoted D j= q , i there exists a homomorphism : Y ! [ N such that ( (Y)) D , i.e., if q (D ) 6= ;.
Datalog syntax includes three types of implication rules. Given a relational schema R, a tuple-generating dependency (or TGD) F is a rst-order formula of the form 8X8Y (X; Y) ! 9Z (X; Z), where (X; Y) and (X; Z) are conjunctions of atoms over R, called the body and the head of F , respectively. Such F is satis ed in a database D for R i , whenever there exists a homomorphism h such that h( (X; Y)) D , there exists an extension h0 of h such that h0( (X; Z)) D . We usually omit the universal quanti ers in TGDs.
Query answering under TGDs is de ned as follows. For a set of TGDs T on R, and a database D for R, the set of models of D given T , denoted mods(D ; T ), is the set of all (possibly in nite) databases B such that D B and every F 2 T is satis ed in B . The set of answers to a CQ q on D given T , denoted ans(q ; D ; T ), is the set of all tuples t such that t 2 q (B ) for all B 2 mods(D ; T ). The answer to a BCQ q over D given T is Yes, denoted D [T j= q , i B j= q for all B 2 mods(D ; T ).
The second component of a Datalog theory is represented by negative constraints (NC): rst-order formulas of the form 8X (X) ! false, where (X) is a conjunction of atoms. The universal quanti ers are usually left implicit.
Equality-generating dependencies (EGDs) are the third component of a Datalog theory. An EGD F is a rst-order formula of the form 8X (X) ! Xi = Xj , where (X), called the body of F , is a conjunction of atoms, and Xi and Xj are variables from X. We call Xi = Xj the head of F . Such F is satis ed in a database D for R i , whenever there exists a homomorphism h such that h( (X)) D , it holds that h(Xi ) = h(Xj ). We usually omit the universal quanti ers in EGDs.
2.1 The Chase The chase is a bottom-up procedure for deriving atoms entailed by a database and a Datalog theory. The chase works on a database through the so-called TGD and EGD chase rules.
The TGD chase rule is de ned as follows. Given a relational database D for a schema R, and a TGD F on R of the form 8X8Y (X; Y) ! 9Z (X; Z), F is applicable to D if there is a homomorphism h that maps the atoms of (X; Y) to atoms of D . Let F be applicable and h1 be a homomorphism that extends h as follows: for each Xi 2 X, h1(Xi ) = h(Xi ); for each Zj 2 Z, h1(Zj ) = zj , where zj is a \fresh" null, i.e., zj 2 N ; zj 62 D , and zj lexicographically follows all other labeled nulls already introduced. The result of the application of the TGD chase rule for F is the addition to D of all the atomic formulas in h1( (X; Z)) that are not already in D .
The EGD chase rule is de ned as follows. An EGD F on R of the form (X) ! Xi = Xj is applicable to a database D for R i there exists a homomorphism h : (X) ! D such that h(Xi ) and h(Xj ) are di erent and not both constants. If h(Xi ) and h(Xj ) are di erent constants in , then there is a hard violation of F . Otherwise, the result of the application of F to D is the database h(D ) obtained from D by replacing every occurrence of a non-constant element e 2 fh(Xi ); h(Xj )g in D by the other element e0 (if e and e0 are both nulls, then e precedes e0 in the lexicographic order).
The chase algorithm consists of an exhaustive application of the TGD and EGD
chase rules that may lead to an in nite result. The chase rules are applied iteratively:
in each iteration (1) a single TGD is applied once and then (2) the EGDs are applied
until a x point is reached. EGDs are assumed to be separable
The two problems of CQ and BCQ evaluation under TGDs and EGDs are
logspace-equivalent
Consider the following ontology for a real estate information extraction system:
F1 = ann(X ; label ); ann(X ; price); visible(X ) ! priceElem(X ) If X is annotated as a label, as a price and is visible, then it is a price element.
F2 = ann(X ; label ); ann(X ; priceRange); visible(X ) ! priceElem(X ) If X is annotated as a label, as a price range, and is visible, then it is a price element.
F3 = priceElem(E ); group(E ; X ) ! forSale(X ) If E is a price element and is grouped with X , then X is for sale.
F4 = forSale(X ) ! 9P price(X ; P ) If X is for sale, then there exists a price for X .
F5 = hasCode(X ; C ); codeLoc(C ; L) ! loc(X ; L) If X has postal code C , and C 's location is L, then X 's location is L.
F6 = hasCode(X ; C ) ! 9L codeLoc(C ; L); loc(X ; L) If X has postal code C , then there exists L s.t. C has location L and so does X .
F7 = loc(X ; L1); loc(X ; L2) ! L1 = L2 If X has the locations L1 and L2, then L1 and L2 are the same.
F8 = loc(X ; L) ! advertised (X ) If X has a location L then X is advertised.
Suppose we are given the database codeLoc(ox 1; central ); codeLoc(ox 1; south); codeLoc(ox 2; summertown) hasCode(prop1; ox 2); ann(e1; price); ann(e1; label ); visible(e1); group(e1; prop1) The atomic BCQs priceElem(e1), forSale(prop1) and advertised (prop1) evaluate to true, while the CQ loc(prop1; L) has answers q (L) = fsummertowng. In fact, even if loc(prop1; z1) with z1 2 N is entailed by formula F6, formula F7 imposes that summertown = z1. If F7 were absent then q (L) = fsummertown; z1g. Answering BCQs q over databases and ontologies containing NCs can be performed by rst checking whether the BCQ (X) evaluates to false for each NC of the form 8X (X) ! false. If one of these checks fails, then the answer to the original BCQ q is positive, otherwise the negative constraints can be simply ignored when answering the original BCQ q .
3 ALP and the SCIFF language Abductive Logic Programming (ALP, for short) is a family of programming languages that integrate abductive reasoning into logic programming. An ALP program consists of a set of clauses, that can contain in the body some distinguished predicates, belonging to a set A and called abducibles. The aim is nding a set of abducibles EXP, built from symbols in A that, together with the knowledge base, is an explanation for a given known e ect (called goal G) and satis es a set of logic formulae, called Integrity Constraints (IC ):
KB [ EXP j= G
KB [ EXP j= IC
SCIFF
A SCIFF Program is a pair hKB ; ICi where KB is a set of clauses (an extended logic program) and IC is a set of forward rules called Integrity Constraints (ICs, for short in the following).
SCIFF considers a (possibly dynamically growing) set of facts (called history ) HAP, that contains ground atoms H(Event [; Time]). This set can grow dynamically, during the computation, thus implementing a dynamic acquisition of events. Some distinguished abducibles are called expectations. A positive expectation, written E(Event [; Time]) means that a corresponding event H(Event [; Time]) is expected to happen, while EN(Event [; Time]) is a negative expectation, and requires events H(Event [; Time]) not to happen. To simplify the notation, we will omit the Time argument from events and expectations.
Variables occurring only in positive expectations are existentially quanti ed
(expressing the idea that a single event is enough to support them), while those in
negative expectations are universally quanti ed, so that any event matching with a
negative expectation leads to inconsistency with the current hypothesis. CLP
IC plus speci c conditions to support the con rmation of expectations.
Positive/negative expectations are con rmed (not violated) if
KB [ HAP [ EXP KB [ HAP [ EXP j= j=
E(X ) ! H(X )
EN(X ) ^ H(X ) ! false
The declarative semantics of SCIFF also requires that the same event cannot be expected both to happen and not to happen
KB [ HAP [ EXP j= E(X ) ^ EN(X ) ! false
Given a SCIFF program hKB ; ICi and a history HAP, a goal G is a SCIFF answer if there is a set EXP such that equations (1)-(5) are satis ed. In this case, we write hKB ; ICi j=HAP G
The SCIFF proof-procedure is a rewriting system that de nes a proof tree, whose nodes represent states of the computation. A set of transitions rewrite a node into one or more children nodes.
The main transitions, inherited from the IFF are:
Unfolding replaces a (non abducible) atom with its de nitions;
Propagation if an abduced atom a(X ) occurs in the condition of an IC (e.g.,
a(Y ) ! p), the atom is removed from the condition (generating X = Y ! p);
Case Analysis given an implication containing an equality in the condition (e.g.,
X = Y ! p), generates two children in logical or (in the example, either X = Y
and p, or X 6= Y );
Equality rewriting rewrites equalities as in the Clark's equality theory;
Logical simpli cations other simpli cations like (true ! A) , A, etc.
SCIFF includes also the transitions of CLP
A complete description is in
In this paper we consider the generative version of SCIFF, called g-SCIFF
Given a SCIFF program hKB ; ICi and a history HAP, we say that a goal G is a g-SCIFF answer if there exist a set EXP and a set HAP0 HAP such that equations (1)-(5) are satis ed1. In this case, we write g hKB ; ICi j=HAP G
In this section, we show that a Datalog program can be represented as a set of SCIFF integrity constraints and a history. SCIFF abductive declarative semantics provides the model-theoretic counterpart to Datalog semantics. Operationally, query answering is achieved bottom-up via the chase in Datalog , while in the ALP framework it is supported by the SCIFF proof procedure. SCIFF is able to integrate a knowledge base KB , expressed in terms of Logic Programming clauses, possibly with abducibles in their body, and to deal with integrity constraints.
To our purposes, we consider only SCIFF programs with an empty KB , IC s with only conjunctions of positive expectations and CLP constraints in their heads. We show that this subset of the language su ces to represent Datalog ontologies2.
We map the nite set of relation names of a Datalog relational schema R into the set of predicates of the corresponding SCIFF program.
The mapping is recursively de ned as follows, where A is an atom, M can be either H or E, and F1, F2, . . . are Datalog formulae: (Body ! Head )
H(A)
E(A) M(F1 ^ F2)
M(Yi = Yj )
E(9X A) = H(Body ) ! = H(A) = E(A) = M(F1) ^ M(F2) = false = Yi = Yj = E(A)
A Datalog database D for R corresponds to the (possibly in nite) SCIFF history HAP, since there is a one-to-one correspondence between each tuple in D and each (ground) fact in HAP. This mapping is denoted as HAP = H(D ).
A Datalog TGD F of the kind body ! head is mapped into the SCIFF integrity constraint IC = (F ), where the body is mapped into conjunctions of SCIFF atoms, and head into conjunctions of SCIFF abducible atoms. Existential quanti cations of variables occurring in the head of the TGD are maintained in the head of the SCIFF IC , but they are left implicit in the SCIFF syntax, while the rest of the variables are universally quanti ed with scope the entire IC . 1 In the equations (1)-(5) the set HAP should be substituted with HAP0. 2 As should be clear soon, the only CLP constraint used in the mapping is the equality constraint
Given a set of TGDs T , let us denote the mapping of T into the corresponding set IC of SCIFF integrity constraints, as IC = (T ).
Recall that for a set of TGDs T on R, and a database D for R, the set of models of D given T , denoted mods(D ; T ), is the set of all (possibly in nite) databases B such that D B and every F 2 T is satis ed in B . For any such database B , we can prove that there exists an abductive explanation EXP = E(B ), HAP0 = H(B ) such that:
HAP0 [ EXP j= IC where HAP0 HAP = H(D ), and IC = (T ).
Finally, Datalog negative constraints NC are mapped into SCIFF ICs with head false, and equality-generating dependencies EGDs into SCIFF ICs, each one with an equality CLP constraint in its head.
Therefore, informally speaking, the set of models of D given T , mods(D ; T ), corresponds to the set of all the abductive explanations EXP satisfying the set of SCIFF integrity constraints IC = (T ).
A Datalog CQ q (X) = 9Y (X; Y) over R is mapped into a SCIFF goal G = E( (X; Y)), where E( (X; Y)) is a conjunction of SCIFF atoms. Notice that in the SCIFF framework we have therefore a goal with existential variables only, and among them, we are interested in computed answer substitutions for the original (tuple of) variables X (and therefore Y variables can be made anonymous).
A Datalog BCQ q = (Y) is mapped similarly: G = E( (Y)).
Recall that in Datalog the set of answers to a CQ q on D given T , denoted ans(q ; D ; T ), is the set of all tuples t such that t 2 q (B ) for all B 2 mods(D ; T ). With abuse of notation, we will write q (t) to mean answer t for q on D given T .
We can hence state the following theorems for (model-theoretic) completeness of query answering.
For each answer q (t) of a CQ q (X) = 9Y (X; Y) on D given T , in the corresponding SCIFF program h;; A; (T )i there exists an answer substitution and an abductive explanation EXP [ HAP0 for goal G = E( (X; )) such that: g h;; ICi j=HAP G where HAP =
H(D ), IC = (T ), and G = E( (t; )).
If the answer to a BCQ q = 9Y (Y) over D given T is Yes, denoted D [ T j= q , then in the corresponding SCIFF program there exists an abductive explanation EXP [ HAP0 such that: where HAP = g h;; ICi j=HAP G
H(D ), IC = (T ), and G = E( ( )).
The SCIFF proof procedure was proved sound and complete w.r.t. SCIFF
declarative semantics in
The TGDs F1-F8 from the Datalog ontology of Example 1 are one-to-one mapped into the following SCIFF ICs:3
IC7 : H(loc(X ; L1)); H(loc(X ; L2)) ! L1 = L2 IC8 : H(loc(X ; L)) ! E(advertised (X ))
The database is then simply mapped into the following history HAP: fH(codeLoc(ox 1; central )); H(codeLoc(ox 1; south));
The SCIFF proof procedure applies ICs in a forward manner, and it infers the following set of abducibles from the program above:
EXP = fE(priceElem(e1)); E(forSale(prop1)); 9P E(price(prop1; P ));
plus the corresponding H atoms, that are not reported for the sake of brevity.
Each of the (ground) atomic queries of Example 1 is entailed in the SCIFF program above, since there exist sets EXP and HAP0 such that:
HAP0 [ EXP j= E(priceElem(e1)); E(forSale(prop1)); E(advertised (prop1)) The query 9L E(loc(prop1; L)) is entailed as well (with uni cation L = summertown) since:
HAP0 [ EXP j= E(loc(prop1; summertown))
Also in this case, if we remove IC7 we obtain the previous answer, and a further one, similar to the one obtained by Datalog , where the set HAP0 contains two loc events:
and the answer includes a further CLP constraint L 6= summertown (being, instead, L and summertown uni ed in the previous answer). 3 We show for clarity the quanti cation of existentially quanti ed variables, although in the SCIFF syntax the quanti cation is implicit.
In this paper, we addressed representation and reasoning for Datalog ontologies in
an Abductive Logic Programming framework, with existential (and universal)
variables, and Constraint Logic Programming constraints in rule heads. The underlying
proof procedure, named SCIFF and inspired by the IFF proof procedure, was
implemented in Constraint Handling Rules
Here we have shown how the SCIFF language can be a useful knowledge representation and reasoning framework for Datalog ontologies. In fact, the underlying abductive proof procedure can be directly exploited as an ontological reasoner for query answering and consistency check, also supporting inline incrementality of the extensional part of the knowledge base (namely, the ABox), represented in SCIFF as a (possibly incremental) set of events. To the best of our knowledge, this is the rst application of ALP to model and reason upon ontologies.
Many issues have not been addressed in this paper, and they will be subject of future work. First of all, we have not focused here on complexity results. Future work will be devoted to identify syntactic conditions guaranteeing tractable ontologies in SCIFF, in the style of what has been done for Datalog .
A second issue for future work concerns experimentation and comparison with other approaches, even not Logic Programming based, on real-size ontologies.
Finally, SCIFF language is richer than the subset here used to represent Datalog ontologies. In fact, the SCIFF integrity constraints can have the disjunction in the head, and negative expectations in rule heads, with universally quanti ed variables too, which basically represent the fact that something ought not to happen, and the proof procedure can identify violations to them. Moreover, the SCIFF language smoothly supports the integration of rules, expressed in a Logic Programming language, with ontologies expressed in Datalog , since a Logic Programming program can be added to the set of ICs, giving the opportunity to consider deductive rules besides the forward ICs themselves. SCIFF also allows for CLP constraints beside the equality one, which can be used also in the ICs as well. Finally, this rich language could be used to add further expressivity to query languages.
ESAW 2005 Post-proceedings, O. Dikenelli, M.-P. Gleizes, and A. Ricci, Eds. Number 3963 in LNAI. Springer-Verlag, Kusadasi, Aydin, Turkey, 106{124.