In previous work, we have introduced probabilistic description logic programs (or pdl-programs), which are a combination of description logic programs (or dl-programs) under the answer set and well-founded semantics with Poole's independent choice logic. Such programs are directed towards sophisticated representation and reasoning techniques that allow for probabilistic uncertainty in the Rules, Logic, and Proof layers of the Semantic Web. In this paper, we continue this line of research. We concentrate on the special case of stratified probabilistic description logic programs (or spdl-programs). In particular, we present an algorithm for query processing in such pdl-programs, which is based on a reduction to computing the canonical model of stratified dl-programs.
of ontologies, that is, for rule-based systems that use vocabulary from ontology knowledge bases. Another type of combination is to build ontologies on top of rules, which means that ontological definitions are supplemented by rules or imported from rules. Towards this goal, the works [7,8] have proposed description logic programs (or dlprograms), which are of the form KB = (L, P ), where L is a knowledge base in a description logic and P is a finite set of description logic rules (or dl-rules). Such dl-rules are similar to usual rules in logic programs with negation as failure, but may also contain queries to L in their bodies, which are given by special atoms (on which possibly default negation may apply). Another important feature of dl-rules is that queries to L also allow for specifying an input from P , and thus for a flow of information from P to L, besides the flow of information from L to P , given by any query to L. Hence, description logic programs allow for building rules on top of ontologies, but also (to some extent) building ontologies on top of rules. In this way, additional knowledge (gained in the program) can be supplied to L before querying. The semantics of dl-programs was defined in [7] and [8] as an extension of the answer set semantics by Gelfond and Lifschitz [12] and the well-founded semantics by Van Gelder, Ross, and Schlipf [29], respectively, which are the two most widely used semantics for nonmonotonic logic programs. The description logic knowledge bases in dl-programs are specified in the well-known description logics SHIF (D) and SHOIN (D).
In [22], towards sophisticated representation and reasoning techniques that also allow for modeling probabilistic uncertainty in the Rules, Logic, and Proof layers of the Semantic Web, we have presented probabilistic description logic programs (or pdlprograms), which generalize dl-programs under the answer set and well-founded semantics by probabilistic uncertainty. They have been developed as a combination of dl-programs with Poole’s independent choice logic (ICL) [25].
It is important to point out that Poole’s ICL is a powerful representation and reasoning formalism for single- and also multi-agent systems, which combines logic and probability, and which can represent a number of important uncertainty formalisms, in particular, influence diagrams, Bayesian networks, Markov decision processes, and normal form games [25]. Furthermore, Poole’s ICL also allows for natural notions of causes and explanations as in Pearl’s structural causal models [10].
In this paper, we continue this line of research. We concentrate on the special case of stratified pdl-programs (or spdl-programs). In particular, as a main new contribution, we present an algorithm for query processing in spdl-programs. It is based on a reduction to computing the canonical model of stratified dl-programs, which can be done by a finite sequence of finite fixpoint iterations. This shows especially that query processing in spdl-programs is conceptually easier than query processing in general pdl-programs, which is reducible to computing the set of all answer sets of general dl-programs and solving linear optimization problems. To my knowledge, this paper and [22] are the first works that combine description logic programs with probabilistic uncertainty.
The rest of this paper is organized as follows. In Section 2, we recall the description logics SHIF (D) and SHOIN (D) as well as stratified description logic programs. Section 3 defines stratified probabilistic description logic programs, and Section 4 deals with query processing in such programs. In Section 5, we discuss related work. Section 6 summarizes the main results and gives an outlook on future research.
In this section, we first recall the description logics SHIF (D) and SHOIN (D). We then recall positive and stratified description logic programs (or dl-programs) under their canonical semantics [7], which combine description logics and normal programs. They consist of a knowledge base L in a description logic and a finite set of description logic rules P . Such rules are similar to usual rules in logic programs with negation as failure, but may also contain queries to L, possibly default negated. 2.1
SHIF (D) and SHOIN (D) We first describe SHOIN (D). We assume a set D of elementary datatypes. Each d ∈ D has a set of data values, called the domain of d, denoted dom(d). Let dom(D) = Sd∈D dom(d). A datatype is either an element of D or a subset of dom(D) (called datatype oneOf). Let A, RA, RD, and I be nonempty finite pairwise disjoint sets of − atomic concepts, abstract roles, datatype roles, and individuals, respectively. Let RA denote the set of all inverses R− of abstract roles R ∈ RA.
A role is an element of RA ∪ RA− ∪ RD. Concepts are inductively defined as follows. Every C ∈ A is a concept, and if o1, o2, . . . ∈ I, then {o1, o2, . . .} is a concept (called oneOf). If C and D are concepts and if R ∈ RA ∪ RA−, then (C ⊓ D), (C ⊔ D), and ¬C are concepts (called conjunction, disjunction, and negation, respectively), as well as ∃R.C, ∀R.C, ≥nR, and ≤nR (called exists, value, atleast, and atmost restriction, respectively) for an integer n ≥ 0. If d ∈ D and U ∈ RD, then ∃U.d, ∀U.d, ≥nU , and ≤nU are concepts (called datatype exists, value, atleast, and atmost restriction, respectively) for an integer n ≥ 0. We write ⊤ and ⊥ to abbreviate C ⊔ ¬C and C ⊓ ¬C, respectively, and we eliminate parentheses as usual.
An axiom is of one of the following forms: (
The syntax of SHIF (D) is as the above syntax of SHOIN (D), but without the oneOf constructor and with the atleast and atmost constructors limited to 0 and 1.
For the semantics of SHIF (D) and SHOIN (D), we refer the reader to [16].
Example 2.1. An online store (such as amazon.com) may use a description logic
knowledge base to classify and characterize its products. For example, suppose that (
We assume a function-free first-order vocabulary Φ with nonempty finite sets of
constant and predicate symbols, and a set X of variables. A term is a constant symbol
from Φ or a variable from X . If p is a predicate symbol of arity k ≥ 0 from Φ and
t1, . . ., tk are terms, then p(t1, . . ., tk) is an atom. A negation-as-failure (NAF) literal
is an atom a or a default-negated atom not a. A normal rule r is of the form
a ← b1, . . . , bk, not bk+1, . . . , not bm , m ≥ k ≥ 0 ,
(
The above dl-rules express that (
In the sequel, let KB =(L, P ) be a dl-program. An interpretation I relative to P is any I ⊆ HB P . We say that I is a model of a ∈ HB P under L, denoted I |=L a, iff a ∈ I. We say that I is a model of a ground dl-atom a = DL[S1op1 p1, . . . , Smopmpm; Q](c) under L, denoted I |=L a, iff L ∪ Sm
i=1 Ai(I) |= Q(c), where Ai(I) = {Si(e) | pi(e)∈I}, for opi = ⊎; and Ai(I) = {¬Si(e) | pi(e)∈I}, for opi = ∪−. A ground dl-atom a is monotonic relative to KB = (L, P ) iff I ⊆ I′ ⊆ HB P implies that if I |=L a then I′ |=L a. In this paper, we consider only monotonic ground dl-atoms, but observe that one can also define dl-atoms that are not monotonic; see [7]. We say that I is a model of a ground dl-rule r iff I |=L H(r) whenever I |=L B(r), that is, I |=L a for all a ∈ B+(r) and I 6|=L a for all a ∈ B−(r). We say that I is a model of a dl-program KB = (L, P ), denoted I |= KB , iff I |=L r for every r ∈ ground (P ). We say that KB is satisfiable (resp., unsatisfiable) iff it has some (resp., no) model.
We say that KB =(L, P ) is positive iff no dl-rule in P contains default-negated atoms. Like ordinary positive programs, every positive dl-program KB is satisfiable and has a unique least model, denoted MKB, that canonically characterizes its semantics. 2.4
We next define stratified dl-programs and their canonical semantics. They are intuitively composed of hierarchic layers of positive dl-programs linked via default negation. Like ordinary stratified normal programs, they are always satisfiable and can be assigned a canonical minimal model via a number of iterative least models.
For any dl-program KB = (L, P ), we denote by DLP the set of all ground dl-atoms that occur in ground (P ). An input atom of a ∈ DLP is a ground atom with an input predicate of a and constant symbols in Φ. A (local) stratification of KB = (L, P ) is a mapping λ : HBP ∪ DLP → {0, 1, . . . , k} such that (i) λ(H(r)) ≥ λ(b′) (resp., λ(H(r)) > λ(b′)) for each r ∈ ground (P ) and b′ ∈ B+(r) (resp., b′ ∈ B−(r)), and (ii) λ(a) ≥ λ(b) for each input atom b of each a ∈ DLP , where k ≥ 0 is the length of λ. For i ∈ {0, . . . , k}, let KB i = (L, Pi) = (L, {r ∈ ground (P ) | λ(H(r)) = i}), and let ⋆ HBPi (resp., HBPi ) be the set of all b ∈ HBP such that λ(b) = i (resp., λ(b) ≤ i). A dlprogram KB = (L, P ) is (locally) stratified iff it has a stratification λ of some length k ≥ 0. We define its iterative least models Mi ⊆ HBP with i ∈ {0, . . . , k} as follows: (i) M0 is the least model of KB 0; ⋆ ⋆ (ii) if i > 0, then Mi is the least model of KB i such that Mi|HBPi−1 = Mi−1|HBPi−1 . The canonical model of the stratified dl-program KB , denoted MKB , is then defined as Mk. Observe that MKB is well-defined, since it does not depend on a particular λ. Furthermore, MKB is in fact a minimal model of KB . 3
In this section, we define stratified probabilistic dl-programs as a combination of dlprograms with Poole’s independent choice logic (ICL) [25]. Poole’s ICL is based on ordinary acyclic logic programs under different “atomic choices”, where each atomic choice along with an acyclic logic program produces a first-order model, and one then obtains a probability distribution over the set of first-order models by placing a distribution over the different atomic choices. In stratified probabilistic dl-programs, we here use stratified dl-programs rather than ordinary acyclic logic programs. 3.1
We assume a function-free first-order vocabulary Φ with nonempty finite sets of constant and predicate symbols, and a set of variables X , as in Section 2. We use HB Φ (resp., HU Φ) to denote the Herbrand base (resp., universe) over Φ. In the sequel, we assume that HB Φ is nonempty. We define classical formulas by induction as follows. The propositional constants false and true, denoted ⊥ and ⊤, respectively, and all atoms are classical formulas. If φ and ψ are classical formulas, then also ¬φ and (φ ∧ ψ). A conditional constraint is of the form (ψ|φ)[l, u] with reals l, u ∈ [0, 1] and classical formulas φ and ψ. We define probabilistic formulas inductively as follows. Every conditional constraint is a probabilistic formula. If F and G are probabilistic formulas, then also ¬F and (F ∧ G). We use (F ∨ G), (F ⇐ G), and (F ⇔ G) to abbreviate ¬(¬F ∧ ¬G), ¬(¬F ∧ G), and (¬(¬F ∧ G) ∧ ¬(F ∧ ¬G)), respectively, and adopt the usual conventions to eliminate parentheses. Ground terms, ground formulas, substitutions, and ground instances of probabilistic formulas are defined as usual.
A choice space C is a set of pairwise disjoint and nonempty sets A ⊆ HB Φ. Any member A ∈ C is called an alternative of C and any element a ∈ A an atomic choice of C. A total choice of C is a set B ⊆ HB Φ such that |B ∩ A| = 1 for all A ∈ C. A probability μ on a choice space C is a probability function on the set of all total choices of C. Since C and all its alternatives are finite, μ can be defined by (i) a mapping μ : S C → [0, 1] such that Pa ∈ A μ(a) = 1 for all A ∈ C, and (ii) μ(B) = Πb∈Bμ(b) for all total choices B of C. Intuitively, (i) associates a probability with each atomic choice of C, and (ii) assumes independence between the alternatives of C.
A probabilistic dl-program (or pdl-program) KB = (L, P, C, μ) consists of a dlprogram (L, P ), a choice space C such that (i) S C ⊆ HB P and (ii) no atomic choice in C coincides with the head of any dl-rule in ground (P ), and a probability μ on C. A stratified probabilistic dl-program (or spdl-program) is a pdl-program KB =(L, P, C, μ) where (L, P ) is stratified. A probabilistic query to KB has the form ?F or the form ?(β|α)[L, U ], where F is a probabilistic formula, β, α are classical formulas, and L, U are variables. The correct answer to ?F is the set of all substitutions θ such that F θ is a consequence of KB . The tight answer to ?(β|α)[L, U ] is the set of all substitutions θ such that ?(β|α)[L, U ]θ is a tight consequence of KB . In the following paragraphs, we define the notions of consequence and tight consequence.
Example 3.1. Consider the spdl-program KB 1 = (L1, P1, C1, μ1), where L1 is as in
Example 2.1, and P1 is as in Example 2.2 except that the dl-rules (
Furthermore, let C1 be given by {{avoid pos, avoid neg }, {offer pos, offer neg }, {v buy pos, v buy neg }, {a buy pos, a buy neg }}, and let μ1(avoid pos) = 0.9, μ1(avoid neg ) = 0.1, μ1(offer pos) = 0.9, μ1(offer neg ) = 0.1, μ1(v buy pos) = 0.7, μ1(v buy neg ) = 0.3, μ1(a buy pos) = 0.7, and μ1(a buy neg ) = 0.3.
Here, the new dl-rules (4’) and (5’) express that the dl-rules (
In a probabilistic query, one may ask for the tight probability bounds that a customer c buys a needed product x, if (i) c bought another product y, (ii) every customer that previously had bought y also bought x, (iii) x is not avoided, and (iv) c has been shown product x (the result to this query may, e.g., help to decide whether it is useful to make a customer automatically also view product x when buying y): ?(buy(c, x) | needs(c, x)∧buy(c, y)∧also buy(y, x)∧view (x)∧not avoid (x))[L, U ] . 3.2
A world I is a subset of HBΦ. We use IΦ to denote the set of all worlds over Φ. A variable assignment σ maps each variable X ∈ X to an element of HU Φ. It is extended to all terms by σ(c) = c for all constant symbols c from Φ. The truth of classical formulas φ in I under σ, denoted I |=σ φ (or I |= φ when φ is ground), is inductively defined by: • I |=σ p(t1, . . ., tk) iff p(σ(t1), . . ., σ(tk)) ∈ I ; • I |=σ ¬φ iff not I |=σ φ ; and I |=σ (φ ∧ ψ) iff I |=σ φ and I |=σ ψ.
A probabilistic interpretation Pr is a probability function on IΦ (that is, since IΦ is finite, a mapping Pr : IΦ → [0, 1] such that all Pr (I) with I ∈ IΦ sum up to 1). The probability of a classical formula φ in Pr under a variable assignment σ, denoted Pr σ(φ) (or Pr (φ) when φ is ground), is defined as the sum of all Pr (I) such that I ∈ IΦ and I |=σ φ. For classical formulas φ and ψ with Pr σ(φ) > 0, we use Pr σ(ψ|φ) to abbreviate Pr σ(ψ ∧ φ) / Pr σ(φ). The truth of probabilistic formulas F in Pr under a variable assignment σ, denoted Pr |=σ F , is inductively defined as follows: • Pr |=σ (ψ|φ)[l, u] iff Pr σ(φ) = 0 or Pr σ(ψ|φ) ∈ [l, u] ; • Pr |=σ ¬F iff not Pr |=σ F ; and Pr |=σ (F ∧ G) iff Pr |=σ F and Pr |=σ G.
A probabilistic interpretation Pr is a model of a probabilistic formula F iff Pr |=σ F for every variable assignment σ. We say that Pr is the canonical model of an spdlprogram KB = (L, P, C, μ) iff every world I ∈ IΦ with Pr (I) > 0 is the canonical model of (L, P ∪{p ← | p ∈ B}) for some total choice B of C such that Pr (I) = μ(B). Notice that every KB has a unique canonical model Pr . A probabilistic formula F is a consequence of KB , denoted KB k∼ F , iff every model of KB is also a model of F . A conditional constraint (ψ|φ)[l, u] is a tight consequence of KB , denoted KB k∼ tight (ψ|φ)[l, u], iff l (resp., u) is the infimum (resp., supremum) of Pr σ(ψ|φ) subject to all models Pr of KB and all variable assignments σ with Pr σ(φ) > 0. Here, we assume that l = 1 and u = 0, when Pr σ(φ) = 0 for all models Pr of KB and all σ. 4
The canonical model of an ordinary positive (resp., stratified) normal logic program P has a fixpoint characterization in terms of an immediate consequence operator TP , which generalizes to dl-programs. This can be used for a bottom-up computation of the canonical model of a positive (resp., stratified) dl-program, and thus also for computing the canonical model of an spdl-program and for query processing in spdl-programs. 4.1
For a dl-program KB = (L, P ), define the operator TKB on the subsets of HB P as follows. For every I ⊆ HB P , let
TKB (I) = {H(r) | r ∈ ground (P ), I |=L ℓ for all ℓ ∈ B(r)} .
If KB is positive, then TKB is monotonic. Hence, TKB has a least fixpoint, denoted lfp(TKB ). Furthermore, lfp(TKB ) can be computed by finite fixpoint iteration (given finiteness of P and the number of constant symbols in Φ). For every I ⊆ HB P , we define TKB (I) = I, if i = 0, and TKB (I) = TKB (T Ki−B1(I)), if i > 0.
i i Theorem 4.1. For every positive dl-program KB = (L, P ), it holds that lfp(TKB ) = MKB . Furthermore, lfp(TKB ) = Sn i
i=0 TKB (∅) = TKnB (∅), for some n ≥ 0. 4.2
We next describe a fixpoint iteration for stratified dl-programs. Using Theorem 4.1, we can characterize the canonical model MKB of a stratified dl-program KB = (L, P ) as follows. Let TbKiB (I) = T KiB (I) ∪ I, for all i ≥ 0. ni ≥ 0 such that TbKnBii (Mi−1) = TbKnBi+i1(Mi−1). Then, Mk = MKB .
Theorem 4.2. Suppose KB = (L, P ) has a stratification λ of length k ≥ 0. Define Mi ⊆ HBP , i ∈ {−1, 0, . . . , k}, as follows: M−1 = ∅, and Mi = TbKnBii (Mi−1) for i ≥ 0, where
Query Processing in Stratified Probabilistic Description Logic Programs
Fig. 2 shows Algorithm tight answer, which computes tight answers θ = {L/l, U/u}
for a given query ?(β|α)[L, U ] to a given spdl-program KB . The algorithm first
computes the canonical model of KB in step (
Algorithm tight answer Input: spdl-program KB = (L, P, C, μ) and probabilistic query ?(β|α)[L, U ]. Output: tight answer θ = {L/l, U/u} for ?(β|α)[L, U ] to KB . 1. Pr := canonical model(KB ); 2. l := 1; 3. u := 0; 4. for every ground instance β′|α′ of β|α do begin 5. l := min(l, Pr (β′|α′)); 6. u := max(u, Pr (β′|α′)); 7. end; 8. return θ = {L/l, U/u}. Related approaches can be roughly divided into (a) description logic programs with non-probabilistic uncertainty, (b) probabilistic generalizations of description logics, and (c) probabilistic generalizations of web ontology languages. Note that related work on description logic programs without uncertainty is discussed in [7,8,22].
As for (a), Straccia [28] combines description logic programs with non-probabilistic uncertainty using interval annotations. To my knowledge, the present paper and [22] are the first ones on description logic programs with probabilistic uncertainty.
As for (b), Giugno and Lukasiewicz [13] present a probabilistic generalization of the expressive description logic SHOQ(D) behind DAML+OIL, which is based on lexicographic probabilistic reasoning. In earlier work, Heinsohn [15] and Jaeger [20] present probabilistic extensions to the description logic ALC, which are essentially based on probabilistic reasoning in probabilistic logics. Koller et al. [21] present a probabilistic generalization of the CLASSIC description logic, which uses Bayesian networks as underlying probabilistic reasoning formalism. Note that fuzzy description logics, such as the ones by Straccia [26,27], are less closely related to probabilistic description logics, since fuzzy uncertainty deals with vagueness, rather than ambiguity and imprecision.
As for (c), especially the works by Costa [4], Pool and Aikin [24], and Ding and Peng [6] present probabilistic extensions to OWL. In particular, Costa’s work [4] is semantically based on multi-entity Bayesian networks, while [6] has a semantics in standard Bayesian networks. In closely related work, Fukushige [11] proposes a basic framework for representing probabilistic relationships in RDF. Finally, Nottelmann and Fuhr [23] present pDAML+OIL, which is a probabilistic generalization of the web ontology language DAML+OIL, and a mapping to stratified probabilistic datalog. 6
We have continued the research on probabilistic dl-programs. We have focused on the special case of stratified probabilistic dl-programs. In particular, we have presented an algorithm for query processing in such probabilistic dl-programs, which is based on a reduction to computing the canonical model of stratified dl-programs.
A topic of future research is to further enhance stratified probabilistic dl-programs towards a possible use for Web Services. This may be done by exploiting and generalizing further features of Poole’s ICL for dynamic and multi-agent systems [25]. Acknowledgments. This work has been supported by a Heisenberg Professorship of the German Research Foundation. I thank the reviewers of this paper for their constructive comments, which helped to improve this work.