We present a simple framework for theta-subsumption testing in Prolog. In its simplest instantiation, it yields an algorithm that takes only a few dozen lines of code. Despite its simplicity, the framework has turned out to work very well on data where a state-of-the-art subsumption engine su ered from excessive run times. The framework can easily be instantiated in di erent ways, precisely because of its simplicity, and can o er an interesting view on how existing methods compare to each other.
2.1
We assume familiarity with standard terminology from logic programming and relational databases, and with Prolog. Theta-subsumption, or brie y subsumption, is de ned as follows: A clause c theta-subsumes another clause d, denoted c d, if and only if there exists a variable substitution such that c d. 2.2
We assume clauses are represented as lists of literals. The following code can then be used to test whether a clause C subsumes a clause D: subsumes(C,D) :- \+ \+ (copy_term(D,D2), numbervars(D2,0,_), subset(C,D2)). subset([], D).
subset([A|B], D) :- member(A, D), subset(B,D).
It makes a copy D2 of D to rename its variables apart from those in C, then skolemizes D2 (i.e., instantiates each variable in it to a di erent constant), and tries to unify C with a subset of D2. Skolemizing D2 avoids that the uni cation procedure applies variable substitutions to both C and D, instead of only to C. The double negation (\+ \+) ensures that the uni cations do not survive the call, so that subsumes(C,D) does not have any side e ects.
This code exploits Prolog's uni cation and backtracking mechanisms. A call to member(A,D) may have multiple solutions, requiring di erent substitutions for the variables in A. Some of these substitutions may make other literals (which share variables with A) un-uni able with any member of D. This may be noticed only later on. Prolog then has to backtrack and try other substitutions for A.
When the rst clause contains variables, the subset predicate de nes a search through the space of all possible variable substitutions. The size of this space is the product of the number of possible instantiations for each variable, and hence exponential in the number of variables occurring in C. 2.3
A simple way to make the search more e cient is to rst partition the clause C
into minimal subsets such that di erent subsets share no variables. The choice of
a substitution for one subset then cannot a ect the existence of a substitution for
another subset. Each subset can then be tested separately using the code listed
above. The complexity of this method is exponential in the largest number of
variables in any one subset (as opposed to the total number of variables).
Example 1. Let C = fp(X); q(X; Y ); r(Z; 2))g and D = fp(
The splitting of clauses into independent parts, each solved separately, is a
crucial element in all e cient theta-subsumption testers.
c: p(a,X,Y), p(b,Y,X), q(Y,Z), r(Y)
d: p(a,1,2), p(a,3,5), p(a,1,0), p(b,1,1), p(b,5,3), p(b,1,0), p(b,2,0), q(5,a), q(3,b), r(
Y 5 In the context of testing C D, let d be the skolemized version of D and c one of the independent subsets of C. A solution is a variable substitution such that c d. A literal l1 matches a literal l2 if and only if a variable substitution exists such that l1 = l2. The instantiation list of a literal l 2 c is the set of all literals l0 2 d that match l. Figure 1 shows an example pair of clauses c and d (a), and for each literal in c the matching literals in d (b).
Using terminology from relational databases, we de ne the instantiation table of a literal l as a table with as attributes the variables in l, and as tuples the value combinations for these variables that occur in the instantiation list. An instantiation table is simply a di erent representation for an instantiation list. Figure 1(c) shows the instantiation tables of the four literals in c.
Note that the instantiation tables serve as constraints on the possible instantiation of tuples of variables. Let T be an instantiation table and X the set of variables corresponding to its attributes. Any solution must instantiate X such that X occurs in T . Therefore: { when tables T and T 0 have the same attribute set, attr(T ) = attr(T 0), they can be replaced by a single table that contains their intersection. { more generally, when attr(T ) attr(T 0), all t0 2 T 0 for which attr(T )(t0) 62 T can be removed from T 0, and after doing this, T can be dropped (it no longer imposes a constraint that is not already imposed by T 0) { even more generally, let A = attr(T ) \ attr(T 0); when A 6= ;, all tuples t0 of T 0 for which A(t0) 62 A(T ) can be removed from T 0, and vice vera, all t 2 T for which A(t) 62 A(T 0) can be removed from T . When the search space can no longer be reduced in the way described, an exhaustive search is needed. The following procedure is then recursively applied: choose a table T ; for each tuple t 2 T : lter the other tables by leaving out all tuples incompatible with t (that is, remove each t0 2 T 0 such that A(t0) 62 A(T ) with A = attr(T ) \ attr(T 0)); call the search procedure recursively on the resulting set of tables. When there are no tables left to choose from, a solution has been found. If at any point, a table becomes empty, the search must backtrack and choose the next t; if no alternatives for t are left, this means no solutions exist.
The selection of T can be done according to a heuristic. Ideally, it maximally reduces the search space. A table with n attribute, each with domain size m, has domain size mn. Of all values in this domain, only the tuples in the table are valid; so, if the table contains l tuples, the search space is reduced by a factor mn=l (compared to exhaustively trying all values). This factor can be used as a heuristic. Another factor to take into account is: in how many other tables lists do the attributes occur, and to what extent will those tables be reduced? Finally, as observed by Santos and Muggleton [5], the instantiation may cause further decomposition of the clause. A heuristic that tries to maximize such decomposition is likely to be advantageous. The above points give rise to a simple algorithm for e cient subsumption testing. A number of auxiliary functions and procedures of the algorithm can be instantiated in di erent manners. The algorithm thus gives rise to a framework that we an easily experiment with.
Our current implementation uses a very simple and rough heuristic: it simply uses 5n=l (that is, it assumes an average domain size of 5). It performs semi-joins until a xpoint is reached. The ltering during the search uses a single step of semi-joining the chosen tuple with the other tables. Decomposition into independent components is done only at the beginning, not after each instantiation. 2.7
Existing subsumption algorithms can be situated within this framework, making it easier to explain and compare them. We focus on Subsumer [5], Resumer [3], Django [4], and the algorithm proposed by Sche er, Herbrich and Wysotzky [6], which we call SHW here. For lack of space, we focus on two main di erences.
All methods mentioned above phrase the problem as a constraint programming problem and use advanced constraint solving methods. An important difference among methods is in how they de ne the variables and domains for the solver. Subsumer and Resumer use as variables the logical variables that occur in the clauses. Django and SHW use as variables the literals in c, and as possible values the (matching) literals in d. From the constraint solving point of view, our method uses tuples of logical variables as the variables to solve for, and tuples of values as their values. The use of single variables is inherently less e cient, as information about which combinations of values occur in clause d is ignored. Using variable tuples as opposed to literals has the advantage that when the same tuple of variables occurs in multiple literals, only one variable is introduced for them in the constraint solver.
Instantiating a variable tuple may cause a connected component to decompose into independent components. Subsumer is the only method to exploit this. Santos and Muggleton showed that this can yield important e ciency gains [5]. The idea can easily be incorporated into our framework. The selection heuristic can be adapted to take the ensuing search space reduction into account. 3
This work was motivated by work on learning language from sentences in a context, where the context is described as a logical interpretation [1, 2]. The incremental learning algorithm proposed there repeatedly computes lggs, which themselves involve multiple subsumption tests, and the straightforward implementation of subsumption testing quickly turned out too slow. Somewhat to our surprise, also Subsumer, the most recently proposed subsumption engine, turned out to be problematically slow on some cases. Repeated attempts to improve our own straightforward subsumption algorithm yielded a simple instantiation of the framework described above.
We compared the runtimes of Subsumer and our algorithm, dubbed Subtle,3 on a dataset of 10000 sentence/context examples. Due to the NP-hardness of the problem, average timings take very long to obtain and are not very informative (they are strongly in uenced by the heavy tails of the runtime distribution). We have therefore followed the following methodology. The incremental learner processes examples one by one. When the processing of a single example takes over a minute (indicating that it gave rise to a \di cult" pair of clauses), the example is commented out and the learner restarted. As more and more such 3 \SUBsumption Testing with Little E ort" \problematic" examples are removed, the learner gets further into the dataset before getting stuck. After removing 10 problematic examples, we stopped.
Subsumer had its 10th problematic example at index 73. Subtle had only 7 problematic examples; the remaining 9993 were processed in 27 minutes.
On one benchmark included in the Subsumer distribution (speci cally, testing 40 hypotheses from the le hyp1 00.pl on the 400 examples in exs 00.pl), we found CPU time ratios for Django, Subsumer and Subtle of roughly 1:5:30. On separate sets of subsumption problems generated from the language learning problem, we found the ratios of roughly 1: { : 5 on one dataset, and { : 7 : 12 on another dataset, where { indicates that the system did not run to completion (due to memory problems or excessive time). While Subtle is not the fastest method on either dataset, it is the only one that could handle both.
All this indicates that di erent methods are best for di erent datasets, and a versatile framework is therefore useful. We believe that our simple framework can o er that versatility, but more experiments are needed to con rm this. 4
We have proposed an framework for testing theta-subsumption that is easy to understand, easy to implement in Prolog, and signi cantly outperforms a stateof-the-art system on a practically motivated problem. Given the NP-hardness of theta subsumption, it is to be expected that di erent algorithms will be optimal under di erent circumstances. An important advantage of our framework is that it can easily be adapted to di erent types of datasets. The simplicity of the framework also makes it possible to incorporate ideas from di erent existing systems into it.
A more extensive experimental evaluation is needed to evaluate the true potential of the method. This will include experiments on a variety of datasets, and with di erent instantiations of the method.