Decomposition of Declarative Knowledge Bases with External Functions
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 752-757.
© 2009 International Joint Conferences on Artificial Intelligence
Abstract
We present a method to decompose a declarative knowledge base, given by a logic program under Answer Set Semantics with access to external sources. It overcomes the ineffectiveness of current methods due to a lack of structural information about these sources, viewed as black boxes, by exploiting independency information in accesses to them. To this end, we develop a generic notion of domain independence that allows to restrict the evaluation domain and, as a consequence, to prune unnecessary dependency assumptions between atoms. This leads to increased decomposability, which we demonstrate by an evaluation method for HEX-programs based on program rewriting. Experiments show that this may yield large performance gains. While developed for a particular formalism, the notions and ideas of this paper might be adapted to related formalisms as well.Thomas Eiter, Michael Fink, Thomas Krennwallner
- [Abiteboul et al., 1995] S. Abiteboul, R. Hull, and V. Vianu. Foun- dations of Databases. Addison-Wesley, 1995.
- [Cohen and Jeavons, 2003] D. Cohen and P. Jeavons. Constraint Processing, R. Dechter (ed.), chapter Tractable Constraint Lan- guages. Morgan Kaufmann, 2003.
- [Costantini, 2006] S. Costantini. On the existence of stable models of non-stratified logic programs. Theory Pract. Log. Program., 6(1-2):169-212, 2006.
- [Eiter et al., 2006a] T. Eiter, G. Ianni, R. Schindlauer, and H. Tom- pits. Effective Integration of Declarative Rules with external Evaluations for Semantic Web Reasoning. In ESWC'06, pp. 273- 287. Springer, 2006.
- [Eiter et al., 2006b] T. Eiter, G. Ianni, R. Schindlauer, and H. Tom- pits. Towards efficient evaluation of HEX programs. In NMR'06, pp. 40-46. 2006.
- [Eiter et al., 2008] T. Eiter, G. Ianni, T. Lukasiewicz, R. Schind- lauer, and H. Tompits. Combining answer set programming with description logics for the semantic web. Artif. Intell., 172(12- 13):1495-1539, 2008.
- [Faber et al., 2004] W. Faber, N. Leone, and G. Pfeifer. Recursive aggregates in disjunctive logic programs: semantics and com- plexity. In JELIA'04, pp. 200-212. Springer, 2004.
- [Gelfond and Lifschitz, 1991] M. Gelfond and V. Lifschitz. Clas- sical negation in logic programs and disjunctive databases. New Gener. Comput., 9:365-385, 1991.
- [Lifschitz and Turner, 1994] V. Lifschitz and H. Turner. Splitting a logic program. In ICLP'94, pp. 23-37. MIT Press, 1994.
- [Subrahmanian et al., 2000] V.S. Subrahmanian, P. Bonatti, J. Dix, T. Eiter, S. Kraus, F. Ozcan, and R. Ross. Heterogeneous Agent Systems: Theory and Implementation. MIT Press, 2000.
- [Wang et al., 2004] K. Wang, D. Billington, J. Blee, and G. Anto- niou. Combining description logic and defeasible logic for the Semantic Web. In RuleML'04, pp. 170-181. Springer, 2004.
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 Introduction
In the last years, there has been a steady increase of the desire to integrate different information sources and software into applications, in order to provide enhanced usability. To address this need, some declarative knowledge representation formalisms have been extended with the capability to access external sources. Often, this is realized via an interface in the style of an API; examples of rule based such formalisms are various extensions of ASP solvers like DLV, XSB, 1 Agent Programs [Subrahmanian et al., 2000], dl-programs [Eiter et al., 2008], defeasible description logic [Wang et al., 2004], Prolog engines with an interface for external functions, etc.
However, the enhanced capabilities of such formalisms come at a performance price. Indeed, structural dependency information, which is usually exploited for efficient evaluation, is blurred or completely lost by access through external sources. This is an inevitable consequence of treating these sources as black boxes, which causes one to cautiously assume that numerous dependencies exists, even if this not true in reality. This may in particular be detrimental in case of mutual dependency between the information in the knowledge base and the external source, which can lead to almost universal dependency assumptions. As a result, decomposing the knowledge base into smaller, local parts for evaluation (like strongly connected components or splitting sets [Lifschitz and Turner, 1994]) is hindered, and large parts have to be evaluated in an uninformed generate and test manner.
∗This work has been supported by the Austrian Science Fund (FWF) projects P20840 and P20841.
1 See www.dlvsystem.com, xsb.sourceforge.net

We illustrate this on the canonical Nixon Diamond, couched in HEX-programs [Eiter et al., 2006a], which extend Answer Set Programming (ASP) with access to external sources via external atoms, in a setting where default rules should be imposed on top of an external ontology.
Example 1 (Nixon Diamond) Suppose T = {r(n), q(n), ∀x. np(x)≡¬p(x) } contains the facts that Nixon was a republican (r(n)) and a quaker (q(n)); we further know that (i) quakers are normally pacifists, while (ii) republicans are normally not pacifists. In spirit of dl-programs [Eiter et al., 2008], the HEX-program PN below encodes (i) and (ii) in the rules (2) and (3), resp.; there, a(p,X) and a(np,X) encode the (reified) assumptions that X is a pacifist resp. is not a pacifist. The program accesses T via external atoms of form &Tχ[a](X), which evaluate to true if, after adding all facts π(c) to T such that a(π, c) is in the model of the program, the atom χ(X) is true in T (d(X) is a simple domain predicate):
Without explaining the semantics here in detail, PN has two models, {d(n), a(p, n)} and {d(n), a(np, n)}, corresponding to the views that Nixon is a pacifist resp. is not a pacifist.
Possible dependencies between atoms are shown in the dependency graph of PN in Figure 1, where an arc from α to
β stands for a (possible) dependency of α from β, and "n" means dependency through negation ("not"). All atoms except d(X) mutually depend on each other, and form one component, C2, for evaluation, which depends on the (singleton) component C1. Now suppose we have m clones of Nixon and d(n1), . . . , d(nm) instead of d(n) in (1). Then the respective program P m N instantiates to m copies, and we have 2m models that contain d(n1), . . . , d(nm) and one of a(p, ni), a(np, ni), for each i = 1, . . . ,m. However, the dependency graph of P m N 's grounding, which traditionally is the basis for efficient evaluation, is not the union of k copies of the dependency graph of PN's grounding, as intuitively expected: there is, e.g., an arc &Tp[a](n1) → a(p, n2), reflecting that a(p, n2) could impact the query p(n1) to T with update a. In fact, according to the dependency graph of P m N 's grounding, all atoms except the d(ni) are on negative cycles, in particular all external atoms; a standard evaluation method thus has to consider all these atoms at once, along with (exponentially many) different guesses for possible input a to them. This results in long execution times. ✷
Due to the black box view, a traditional evaluation of P m N is unaware that each external atom actually depends only on two facts, e.g., &Tp[a](ni) on a(p, ni), a(np, ni), and that (as by intuition) indeed a splitting of the P m N into k disjoint copies is feasible which can be evaluated independently.
This calls for refined methods to decompose a declarative knowledge base with access to external sources. In this paper, we address this issue and make the following contributions.
- We consider domain independence information as a basis for more effective decomposition of programs with access to external sources. Domain independence means that the evaluation of an external atom depends, for a given set of arguments, only on a subset of the domain, and that other elements in the domain can be safely ignored. Building on this, the idea is to split the domain in different parts such that external atoms can be evaluated independently in different parts. This is formalized as greatest local split of a set of ground atoms, which is algebraically defined in Section 3.
- Using greatest local splits, we refine the traditional method of evaluating programs using the ground dependency graph, by pruning unnecessary dependency assumptions of atoms caused by external functions (Section 4).
- We develop a decomposition method for HEX-programs that uses program rewriting on the non-ground level, based on independency information (Section 4). The evaluation of programs resorts then to standard technology, such that the method can be realized with rather little effort (Section 5).
Some experiments with an implementation, in particular on the program in Example 1 above, show that the rewriting may lead to large performance gains and scalability.
2 Preliminaries
Partial orders and partitions. Recall that a poset (S, ⪯) has a binary relation ⪯ on a set S that is reflexive, anti-symmetric, and transitive. For any X ⊆ S, an element u ∈ S is an upper bound of X, if b ⪯ u for all b ∈ X, and is the least upper bound of X, if u ⪯ u′ for all upper bounds u′ of X.
A partition π on a set S is collection of nonempty disjoint subsets of S such that S = ⋃ π.
Syntax of HEX-Programs. Let C, X , and G be mutually disjoint sets whose elements are called constant names, variable names, and external predicate names, respectively. Unless explicitly specified, elements from X (resp., C) are denoted with first letter in upper case (resp., lower case), while elements from G are prefixed with the "&" symbol. We note that constant names serve both as individual and predicate names.
Elements from C ∪ X are called terms. A higher-order atom (or atom) is a tuple (Y0, Y1, . . . , Yn), where Y0, . . . , Yn are terms; n ≥ 0 is the arity of the atom. Intuitively, Y0 is the predicate name; we thus use the more familiar notation Y0(Y1, . . . , Yn). The atom is ordinary, if Y0 is a constant.
An external atom is of the form
where Y1, . . . , Yn and X1, . . . ,Xm are two lists of terms (called input and output lists, respectively), and &g ∈ G is an external predicate name. We assume that &g has fixed lengths in(&g)=n and out(&g)=m for input and output lists, respectively. Intuitively, an external atom provides a way for deciding the truth value of an output tuple depending on the extension of a set of input predicates. For any set of atoms A, we denote by &A the set of external atoms in A.
A rule r is of the form
where m, k ≥ 0, each αi is an atom, and each βj is an atom or an external atom. We let H(r) = {α1, . . . , αk} and B(r) = B+(r) ∪ B-(r), where B+(r) = {β1, . . . , βm} and B-(r) = {βm+1, . . . , βn}. Rule r is a constraint, if H(r)=∅ and B(r) ̸=∅, and a fact, if B(r)=∅ and H(r) ̸=∅.
A HEX-program (or program) is a finite set P of rules; it is ordinary, if all its rules are ordinary, i.e., it contains only ordinary atoms.
Example 2 The program PN for the Nixon Diamond above consists of one fact and two rules that use negation "not", and they have external atoms &Tr [a](X), &Tnp[a](X), etc. ✷
Semantics of HEX-Programs. The Herbrand base HBP of a HEX-program P is the set of all possible ground instances of atoms and external atoms in P using constants from C. The grounding of a rule r, grnd(r), is analogous, and the grounding of P is given by grnd(P) = ⋃r∈P grnd(r). By default, C, X , and G are implicitly given by P .
An interpretation of P is any subset I ⊆ HBP that contains only ordinary atoms; we say that I is a model of
- a ground external atom α=&g[c2](c1) (denoted I |=α), if f&g(I, c2, c1)=1, where f&g is a (fixed) (n+m+1)-ary Boolean function for &g , where n = in(&g ), m = out (&g ), I ⊆ HBP, and c2 ∈C n , c1 ∈Cm.
- a ground rule r (I |= r), if I |=H(r) or I ̸|=B(r), where (i) I |= H(r), if I |= α for some α ∈ H(r) and (ii) I |=B(r), if I |=α for all α ∈ B+(r) and I ̸|=α for all α ∈ B-(r). - a program P (I |= P), iff I |=r for all r ∈ grnd(P).
The FLP-reduct [Faber et al., 2004] of a program P wrt. an interpretation I is fP I = {r ∈ grnd(P) | I |= B(r)}; then I is an answer set of P, if I is a ⊆-minimal model of fP I . For ordinary P, this amounts to answer sets as in [Gelfond and Lifschitz, 1991]. We denote by AS(P) the collection of all answer sets of P .
Example 3 In the Nixon example, the semantics of external atoms may be formally given as f&Tχ (I, c′ , c)=1 iff T ∪ {d(d′ ) | c′ (d, d′ ) ∈ I} |= χ(n), for all c, c′ ∈ C = {n, p, np, a}. Then, I = {d(n), a(p, n)} is an answer set of PN: clearly, I |= fPNI , and fPNI includes (1) and the instance of (2) for X=n; hence, each model J ⊆I of fPNI fulfills J ⊇I.
In the rest of this paper, we assume w.l.o.g. that all input terms in external atoms are viewed as predicate symbols.
We next recall the notions of dependency graph and global splitting sets of a program [Eiter et al., 2006a], which provides a basis for efficient HEX-program evaluation.
For a program P and atoms α, β occurring in P , we say
- (a) α depends positively on β (α→p β), if either
- (i) some rule r∈P has α∈H(r) and β ∈B+(r);
- (ii) there are rules r1, r2 ∈ P such that α ∈ B(r1) and β ∈ H(r2) and there exists a partial substitution θ of variables in α such that either αθ = β or α = βθ; or
- (iii) some rule r ∈ P has α, β ∈ H(r).
- (b) α depends externally on β (α→e β), if α is is of form &g[X1, . . . ,Xn](Y), β is of form p(Z), and Xi = p for some i ∈ {1, . . . , n}.
- (c) α depends negatively on β (α→n β), if there is some rule r ∈ P such that either α ∈ H(r) and β ∈ B-(r) or β is a nonmonotonic external atom (i.e., I ⊆ I ′ and I |= β does not entail I ′ |= β).
We say that α depends on β, if α→β, where → is the union of →p , →e , and →n .
The dependency graph GP =(VP ,EP ) of P has as vertices VP all atoms occurring in P and as edges EP all dependency relations →p , →e , and →n for P
A global splitting set for a HEX-program P is a set of atoms A occurring in P such that α∈A, β occurs in P , and α → β implies β ∈A. The bottom of P wrt. a set of atoms A is the set of rules bA(P) = {r ∈ P | H(r) ∩ A ̸= ∅}.
Example 4 Figure 1 shows the dependency graph of PN; note that all external atoms are monotonic, and C1 ∪ C2 (all atoms) and C1 are global splitting sets. ✷
3 Domain Independence
In this section, we develop our notion of domain independence. The idea is to partition the elements of the domain into disjoint sets, such that the evaluation of an external atom only depends on the elements that are in the sets associated with the arguments of the atom. We call a suitable such partitioning a basis. For program decomposition, we need to take the structure of the rules into account, respecting syntactic dependency of atoms and arguments according to the dependency graph, assuming that elements in the same partition are mutually dependent. This leads us to a refinement of the basis (i.e., sets are further partitioned) to a unique greatest local split of a set of atoms. The latter is defined algebraically.
Notation. We start with fixing some notation. In what follows, let D = C (for domain).
Let (D,⪯) be the poset of the lattice of partitions of D, where for any two partitions π1, π2 ∈ D, π1 ⪯ π2 iff ∀x ∈ π1 ∃y ∈ π2 : x ⊆ y (i.e., ⪯ is the usual refinement order).
For any set S ⊆ D and m-ary predicate symbol p, we let p[S] = {p(c) | c ∈ Sm}, and for a list p = p1, . . . , pk of predicate symbols, we let p[S] = p1[S] ∪ · · · ∪ pk[S].
We now define the notion of a basis for an external atom.
Definition 1 (Basis) Let B ⊆ D, let α = &g[p](c) be a ground instance of an external atom over D with Boolean function f&g. We call B a basis for α, if for all interpretations I and B′ ⊇ B, f&g(I ∩ p[B], p, c) = f&g(I ∩ p[B′ ], p, c). 2
Example 5 Let D be a domain, I = {p(a), p(b), q(a)} be an interpretation, and p = p, q. Let B1 = {a} and B2 = {b, c} be two subsets of D. Then, I ∩ p[B1] = {p(a), q(a)} and I ∩p[B2] = {p(b)}. Now suppose α = &g[p](a) is such that for all interpretations I, f&g(I, p, a) = 1 iff p(a) ∈ I. Then, B1 is a basis for α, and f&g(I, p, a) = f&g(I ∩ p[B1], p, a).
Given an external atom α, define for any a, b ∈ D that a ∼α b iff a, b ∈ B for basis B for α, and c ∼α c for every c ∈ D. Then ∼α is an equivalence relation, whose quotient set D/∼α forms a partition of D.
The notion of greatest local split is now defined as follows.
Definition 2 (Greatest Local Split) For any set of ground atoms A, the greatest local split of A, denoted gls(A), is the partition π ∈ D which is the least upper bound of B = {D/∼α | α ∈ &A } in (D, ⪯) (recall &A from above).
Obviously, gls(A) is unique and always exists.
Example 6 Let ∼α = {(a, a), (b, b), (c, c), (d, d)} and ∼β = {(a, a), (a, b), (b, a), (b, b), (c, c), (d, d)} be equivalence relations over D = {a, b, c, d} for α and β, respectively. Then, D/∼α = {{a}, {b}, {c}, {d}} and D/∼β = {{a, b}, {c}, {d}}. Now let A be a set of ground atoms such that α, β ∈ A. We obtain gls(A) = D/∼β = {{a, b}, {c}, {d}}, whenever all possible ∼ of external atoms in A are equal to ∼α or to ∼β. ✷
The following result then, whose proof is not difficult, forms the basis for exploiting joint dependency information.
Proposition 1 Let &g[p](c) be an external atom, let A be a set of atoms such that &g[p](c) ∈ grnd(A), and let I be an interpretation. Then, for every partition π such that gls(A) ⪯ π, there exists some B′ ∈ π such that
By this proposition, we can partition the domain, at different levels of granularity, in a way such that we can evaluate the atoms in A in different sets of the partition.
Note that computing the greatest local split is inexpensive.
Proposition 2 Given a set of atoms A and B as in Def. 2, we can compute gls(A) in linear time in the size of A and B.
Indeed, we can compute gls(A), e.g., as connected components of a graph that we construct from B in linear time.
4 Rewriting with Domain Independence
In this section, we apply the results obtained in the previous section in order to improve the evaluation of HEX-programs by taking dependency information of external atoms into account. The idea is to first prune unnecessary ground dependencies from the dependency graph GP of a given program P, like for &Tp[a](n1) → a(p, n2) in the grounding of P m N with m Nixon clones. In a second step, we rewrite the program into an equivalent program, such that the evaluation of strongly connected components is restricted to relevant subdomains whenever possible. Intuitively, this step accounts for unnecessary dependencies between non-ground atoms.
2 As f&g only depends on p, f&g(I ∩p[B], p, c) = f&g(I, p, c).
In this section, we assume that the domain D is finite; note that even for a basically infinite set C, P may be equivalent to its grounding over a finite subset of C; e.g., domain-expansion safe programs [Eiter et al., 2006a] have this property.
Step 1: Dependency Graph Pruning. We assume that we are given a HEX-program without higher order atoms-note that w.l.o.g. higher order atoms can be removed by partial grounding-and that every ground external atom α in the program has an associated basis Bα in D. Furthermore, for a proper treatment of the dependency between input and output of a ground external atom, we assume bases Bα, such that all elements of the output c of α are in Bα.
We first reduce the dependency graph GP to a graph G′P as follows. For any graph G, let SCC(G) be the set of strongly connected components in G. Consider any component C ∈SCC(GP ) and gls(grnd(C)) (which is uniquely determined by the bases of external atoms in grnd(C)). We remove every arc &g[p](c1)→p(c2) from C, such that c1 and c2 are variable-free and there is an element in c2 which does not belong to the partition of c1 in gls(grnd(C)). Let G′P denote the resulting graph. Then we can evaluate P using G′P instead of GP . More formally, this is detailed as follows.
Let Comp = {C1, . . . , Cn} be a partitioning of the atoms occurring in P such that all grnd(Ci) are pairwise disjoint, and let PCi contain all rules r ∈ grnd(P) such that H(r) ∩ grnd(Ci) ̸= ∅, i = 1, . . . , n. A partial ordering E(P) = (Comp,⊑) is then an evaluation ordering for P, if H(r) ⊆ grnd(Ci), for each r ∈ PCi , i = 1, . . . , n, and the following property (6) holds. Let PCi ↓ = ⋃Cj⊑Ci PCj ; then
where {Ci1 , . . . ,Cini } = {Cj ⊏ Ci | ∀Cj ′ : Cj ⊑ Cj ′ ⊏ Ci ⇒ Cj = Cj ′} are the maximal sets Cj smaller than Ci. That is, the answer sets of the rules associated with Ci and all Cj below are obtained as the answer sets of the rules associated with Ci to which the answer sets of the rules associated with Cj and all C′j below are added.
Then, given that Ci1 , . . . , Cil are the maximal elements of E(P) and Pcon are all constraints in P, it holds that
It is well-known that SCC(GP ) is an evaluation ordering for P, cf. [Eiter et al., 2006a]. We similarly have:
Proposition 3 SCC(G′P ) is an evaluation ordering for P .
Intuitively, the strongly connected components of G′P refine those of GP by removing unnecessary input dependencies of external atoms. We note that coarser evaluation orderings can be obtained e.g. by collapsing suitable components in SCC(GP ) resp. SCC(G′P ). As for us the precise evaluation ordering is immaterial, we work in the sequel with a generic given evaluation ordering E(P ).
Step 2: Program Rewriting. We proceed by introducing a rewriting of P wrt. E(P) in order to further improve the evaluation of non-ground programs. The idea is to restrict the applicability of rules with external atoms to relevant ground instances given respective domain independence information. To avoid inhibiting the application of relevant ground instances, and to keep the rewriting general and simple, we consider here the maximal number k = k(P ) of distinct variables in a rule r ∈ P as a bound for potential dependencies. 3
In the following, we let for every p ∈ C be ps a fresh symbol with arity of p. For a set of atoms A, let
The i-restricting substitution in A is the partial substitution
which maps predicates p of every ordinary atom p(t) in A to pi . An i-restriction of A in P, short P iA, is the set of rules {H(r)σiA ←B(r)σiA, domi (X1), . . . , domi (Xr) | r ∈ bA(P)}, where domi is a unary predicate symbol and X1, . . . ,Xr are all output variables which occur in some external atoms in B(r). Furthermore, let
be the k-fold union of a partition π augmented with const (A).
Definition 3 (Decomposition dC(P)) Let C ∈ E(P) and gls(grnd(C))k∪(C) = {D1, . . . ,Dℓ} for k = k(P). The decomposition of P wrt. C, denoted dC(P), is defined as
Example 7 Reconsider the cloned version P m N of Example 1 and an evaluation order with the components C1,C2 in Figure 1, where C1 ⊏ C2. Note that this is the evaluation order given by the strongly connected components of GP (which is not affected by the pruning step). Given that &Tχ[a](ni) only depends on a(p, ni), a(np, ni), for 1 ≤ i ≤ m, we obtain that gls(grnd(C2))1∪(C2) = {{ni, p, np} | 1 ≤ i ≤ m}.
Thus, the decomposition of P m N wrt. C2 contains m rewritings of rule (2), e.g., for i = 1 given by
a1 (p, X) ← d(X), &T r [a1 ](X), not &T np [a1 ](X), dom1 (X), where dom1 ranges over D1 = {n1, p, np}. Similarly for rule (3). This reduces the applicability of the two rules to the corresponding domain Di of the respectively rewritten rules, which intuitively amounts to removing any dependencies to ordinary ground atoms (inputs) in other subdomains. ✷
We denote by r and ri ground rules from grnd(bC(P)) and grnd(dC(P)), resp., such that there is a rule r′ ∈ bC(P) and a ground substitution θ yielding r = r′ θ and ri = H(r′ )σiC θ ← B(r′ )σiC θ, domi (X1)θ, . . . , domi (Xr)θ. Moreover, ri is called Di-applicable iff c ∈ Di for every domi (c) ∈ B(ri ). Given C ∈ E(P), with gls(grnd(C))k∪(C) = {D1, . . . , Dℓ} for k = k(P), and a set N ⊆ HBP of ground ordinary atoms, let M(N) be the set
3 This is a cautious overestimate, and often k may be smaller.
Furthermore, for any set M of ground ordinary atoms, M|C = {p(c) ∈ M | p ∈ C}. Obviously, if M is of the formM(N), then N =M|C.
Informally, given a set N of ground ordinary atoms, in addition to the original atoms and a respective domain closure (i.e., domi [Di] atoms) M(N) contains a rewritten atom pi (c) for some p(c) ∈ N: If p(c) is an atom that is modified by the rewriting and appears in a potentially applicable rule in P iC (Condition ϕb), or if p(c) is an input atom, i.e., one that is not modified by the rewriting, such that the predicate p is subject to rewriting, however (Condition ϕa). The latter guarantees that it is taken into account as (potential) input for rewritten external atoms (as it is for the respective unmodified external atoms). Towards correctness of the rewriting technique, we first establish the following lemma.
Lemma 4 Let C ∈ E(P), let r ∈ grnd(bC(P)), and let ri ∈ grnd(dC(P)) such that ri is Di-applicable. Suppose N ⊆ HBP consists of ordinary ground atoms such that, for every &g[p](c) ∈ B(r) ∩ grnd(C) and ground atom α, it holds that α ∈ N ∩ p[Di] iff ασiC ∈ M(N) ∩ pσiC [Di]. Then, N |= B(r) iffM(N) |= B(ri ).
Note that the condition on α could be weakened exploiting information on external atoms in bC(P), e.g., monotonicity.
For the simple rewriting to be applicable, we require the following condition. Given bC(P) and a set of ground ordinary (input) atoms I, such that I ∩ grnd(C) = ∅, we call dC(P) a unique split wrt. I, iff for every ordinary atom p(c) ∈ grnd(C) the following holds: If pi (c) ∈ H(ri ) ∪ B(ri ) for some Di-applicable rule ri ∈ dC(P), and I |= B(ri )\(grnd(C)σiC ∪&B(r i )∪domi [Di]), then (i) pj (c) ∈ H(rj )∪B(rj ) for some Dj-applicable rule rj ∈ dC(P), and I |= B(rj ) \ (grnd(C)σiC ∪ &B(r j ) ∪ domj [Dj]) implies i = j, and (ii) p(c) ∈ p[Dj] implies i = j. In this condition, (i) warrants that there is a unique index i of rewritten rules that can potentially infer a rewritten atom pi (c), and (ii) ensures that such atoms can constitute relevant input for external atoms in P iC only. This could be weakened by more advanced rewriting techniques, taking into account (i) dependencies introduced by the rules in bC(P) rather than the projective rules α ← αi , and (ii) further (monotonicity) information concerning the external atoms in bC(P).
For the setting studied in this paper a 1-to-1 correspondence between the answer sets of bC(P) and the answer sets of its decomposition wrt. C, dC(P), holds for unique splits. More precisely, the correctness of the rewriting in this regard is expressed formally as follows.
Proposition 5 Let C∈E(P), and let I be any set of ground ordinary atoms such that I ∩ grnd(C) = ∅. If dC(P) is a unique split wrt. I, then M ∈ AS(dC(P) ∪M(I)) implies that M|C ∈ AS(bC(P ) ∪ I) and M = M(M|C).
On the other hand, the rewriting technique is complete for unique splits, i.e., given an answer set of N of AS(bC(P) ∪ I), if dC(P) is a unique split wrt. I, thenM(N) is an answer set of dC(P) ∪M(I).
Proposition 6 Let C ∈ E(P), and let I be any set of ground ordinary atoms such that I ∩ grnd(C) = ∅. If dC(P) is a unique split wrt. I, then N ∈ AS(bC(P) ∪ I) implies M(N) ∈ AS(dC(P ) ∪ M(I)).
Applying the global splitting theorem of [Eiter et al., 2006a] and the previous results, we can compute answer sets of P iteratively. Given an evaluation ordering E(P) = (Comp,⊑), let E1, . . . ,Ed be pairwise disjoint sets of components, such that ⋃di=1 Ei = Comp and for every C ∈ Ei, C′ ∈ Ej, and i < j, it holds that C′ ̸⊏ C. For an iterative evaluation, we recursively define sets I of sets of ground ordinary atoms as follows: I0 = {∅}, and Ij+1 = ⋃I∈Ij {N | N = ⋃C∈Ej+1 NC(I)}, where NC(I) = M|C if M ∈ AS(dC(P) ∪M(I)) and dC(P) is a unique split wrt. I, and NC(I) = M for some M ∈ AS(bC(P ) ∪ I), otherwise. We eventually obtain the following correspondence.
Theorem 7 Let P be a HEX-program. Then N ∈ AS(P) if and only if N ∈ Id and N |= {r ∈ P | H(r) = ∅}.
This result establishes the correct application of the rewriting technique for the evaluation of a program.
Example 8 Reconsider the cloned version P m N of Example 1 with the evaluation order C1 ⊏ C2. For C1, which is a set of facts, we obtain a single answer set of dC1 (P m N ) ∪ ∅: NC1 (∅) = {d(ni) | 1 ≤ i ≤ m}. Since dC2 (P m N ) is a unique split wrt. NC1 (∅), the we can compute the answer sets of P m N as the sets M|C, where M ∈ AS(dC2 (P m N ) ∪ M(NC1 (∅))). ✷
Observe that for ground programs P, k(P) = 0, i.e., rule application cannot be further constrained by domain restrictions. This is reflected in the rewriting, which decomposes P into a single copy for every component without any dom predicates in the body. However, for ground programs, the pruning of dependencies as described in Step 1 is most effective, and captures the cases otherwise handled by the rewriting.
On the other hand, for non-ground programs, the evaluation may be improved by partial grounding, which reduces k(P) (thus the number of domain partitions to be joined in a k-fold union). We leave a more fine-grained analysis of the program in order to reduce k(P ) as further work for optimization.
5 Realization and Experimentation
The standard algorithm to evaluate a given HEX-program P was shown in [Eiter et al., 2006b]. Its principal idea is to break up the computation into smaller tasks, and, in spirit of [Lifschitz and Turner, 1994], to perform a bottom-up evaluation of the using the strongly connected components of GP . The procedure uses a subroutine eval(P,C, I), which helps creating the models wrt. a component C and an interpretation I: eval keeps track of cycles in C and chooses the appropriate solving strategy for it, and generates models compliant

(a) Schematic view of dP m
N for m= ℓ

(b) oP m
Figure 2: Nixon decomposition and experiment
Algorithm 1: decomp-eval(P, C, S, I): Compute the answer sets of a component C and greatest local split S in P wrt. I
with the external atoms in C (see [Eiter et al., 2006b] for the details).
We realize the evaluation of our decomposition method by adapting the standard evaluation algorithm. For that, we introduce the refined component evaluation subroutine decomp-eval(P,C, S, I) shown in Algorithm 1. The major changes for the overall refined HEX-program evaluation are:
- after creating the dependency graph GP , we create from SCC(GP ) = {C1, . . . , Cn} the greatest local splits Si = gls(grnd(Ci)), i = 1, . . . , n.
- we generate the pruned dependency graph G′P and perform the bottom-up evaluation wrt. SCC (G′P );
- then, while evaluating the components, we check for each Ci whether dCi (P) is a unique split wrt. I and call then
- (i) decomp-eval(P,Ci, Si, I) instead of eval in order to evaluate a component Ci with greatest local split Si in a HEX-programP wrt. an interpretation I, and take, transparently to the evaluation procedure, dependency information into account; otherwise,
- (ii) if dCi (P) is not a unique split wrt. I, we just call eval(P, Ci, I).
Regarding (2), we prune GP to G′P by stripping ground dependencies in Ci wrt. Si as described in Section 4. The resulting dependency graph G′P then consists of components Comp ′ . The further evaluation of P, which is kept as is, will be performed with Comp ′ .
After preprocessing the components of P outlined as above, the refined components will be evaluated in the usual way. To this end, we may call decomp-eval(P,Ci, Si, I) as described in (3i), provided that dCi (P ) is a unique split wrt. I (see step (3)). Alternatively, we fall back to the standard HEXprogram evaluation procedure eval(P, C, I), as done in (3ii).
Let C∈SCC(G′P ), S=gls(grnd(C)), and I be an interpretation. In decomp-eval(P,C, S, I) from above, we first generate the k-fold union of S in step (a), create dC(P) in step (b), and then evaluate the decomposed program in step (c). The result is stored in N. The following states the correctness.
Proposition 8 Given a HEX-program P, component C, greatest local split S = gls(grnd(C)), and interpretation I, we have N ∈ AS(bC(P) ∪ I) iff M(N) ∈ N, where N is the output of Algorithm 1.
For experimental evaluation, we adapted the development version of the dlvhex prototype system, 4 which is an open source reasoner for HEX-programs.
We have realized our running example, the Nixon diamond, using external atoms that query a description logic knowledge base (DL-KB) in spirit of dl-atoms in description logic programs [Eiter et al., 2008]. To this end, we encoded T as DL-KB. The external atoms &Tχ[a](c) are then realized as instance retrieval queries over T using a DL-reasoner (RacerPro 1.9.2beta). 5 All tests have been conducted on a P4 3GHz Linux system with 1GB of main memory. For a program P , we write short oP for the standard HEX-program evaluation strategy, whereas dP denotes our new decomposition evaluation strategy using decomp-eval.
We fixed a ∼α a for all individuals a and all ground external atoms α for P m N 's. In the decomposed program evaluation of P m N we have m+2 components (see Figure 2a for a schematic view). We computed all 2m answer sets of the test programs, and the experimental results are displayed in Figure 2b. They show the effectiveness of the method; we
4 www.kr.tuwien.ac.at/research/systems/dlvhex/
5 www.racer-systems.com/
N vs. dP m
N (all answer sets)
| m | 1 | 2 | 3 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|---|---|
| oP m N dP m | 0.21 | 1.63 | 14.5 | - | - | - | - | - |
| N | 0.22 | 0.43 | 0.65 | 0.91 | 2.33 | 28.12 | - | - |
| oP m nra dP m nra | 0.21 0.23 | 1.53 0.41 | 14.2 0.61 | - 0.85 | - 2.12 | - 5.81 | - 16.27 | - 49.83 |
gain an exponential speed-up with our decomposed evaluation strategy dP m N .
We have created another example by slightly adapting Example 1. If we add to P m N the additional rule
we obtain a program P m nra that disables the applicability of rule (3) and forces all Nixons to be pacifists. As above, we have fixed a ∼α a for all individuals and all ground external atoms α for P m nra 's. The evaluation with our decomposed programs then consists again of m+2 components. We computed the single answer set of each of these test programs.
The detailed outcome of both Nixon test series is listed in Table 1, where "-" means timeout (1 min). The results show that both oP m N and oP m nra evaluation have an early breakdown (m=4) while all runs of the dP m N evaluation up tom=16, and dP m up to m=64, finished in time.
nra The check for uniqueness of the split dC(P) was fast (a few msecs) on our examples by employing a non-recursive datalog program.
Due to space limitations, we only report here the Nixon example. We have looked at similar encodings, like the Tweety example, and the experiments show a similar picture.
To get a better understanding of the improvements of the evaluation, notice that implementations that feature external functions usually adopt a guess and check strategy when an external atom α = &g[y](x) appears in a (negative) cycle in the dependency graph. A guess represents a model of the cyclic program component and this model has to comply with the function f&g for α, which may be expensive to evaluate. The guesses must be made wrt. a domain of individuals (in the worst case, all constants). Using our theory of domain independence, we can rewrite the program such that components range over smaller domains. This not only effects that fewer guesses are made for the external atoms, but also that the number of (costly) compliance checks decreases.
6 Discussion and Conclusion
We have presented a method to decompose declarative knowledge bases with access to external sources, formalized as HEX-programs, by using domain independence information. The method may lead to a large (exponential) improvement in performance, as evidenced by examples. While our method has been developed for HEX-programs, the underlying ideas and principles are generic and may be adapted for other similar KR formalisms (cf. Introduction).
To the best of our knowledge, program optimization based on domain independence about external sources, with possible non-monotonic negation, has not been addressed before. Note that domain independence is well-known in databases [Abiteboul et al., 1995]. It is related to active domain semantics and usually enforced by safety of queries and rules.
Domain decomposition techniques are also used in constraint processing [Cohen and Jeavons, 2003], but in a different setting.
Several issues remain for further investigation. One issue is a more involved analysis of dependencies, to make the set of atoms for which greatest local splits are computed smaller, e.g., by respecting unifiability over transitive arcs or respecting syntactic conditions (cf. [Costantini, 2006]). Also the notions of greatest local split and k-fold union may be refined. An orthogonal direction is predicate splitting, where input predicates p are removed from external atoms &g[. . . , p, . . . ](X) whose values are independent of p wrt. relevant interpretations; this may be applied as a post processing after domain splitting.
Another issue is how to obtain dependency information. Clearly, this depends on the nature of the external sources, and there is no general recipe apart from (expensive) verification of the definitions. However, often the knowledge engineer has insight in dependency information that she can supply, like in the Nixon diamond example. To some extent, (in)dependency information may also be obtained by (semi)automated analysis of external sources. For logic knowledge bases, notions of relevance for reasoning might be exploited, and for others (e.g., wordnet ontologies, URL lists) specific methods developed.
@inproceedings{ijcai2009p130,
title = {Decomposition of Declarative Knowledge Bases with External Functions},
author = {Eiter, Thomas and Fink, Michael and Krennwallner, Thomas},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Craig Boutilier},
pages = {752--757},
year = {2009},
url = {https://ijcai.org/proceedings/2009/130},
}
TY - CPAPER TI - Decomposition of Declarative Knowledge Bases with External Functions AU - Eiter, Thomas AU - Fink, Michael AU - Krennwallner, Thomas T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 752 EP - 757 UR - https://ijcai.org/proceedings/2009/130 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: