Although matching in Description Logics (DLs) is theoretically wellinvestigated, an implementation of a matching algorithm exists only for the DL ALE. The present paper presents an implementation of an existing polynomial time matching algorithm for the DL ALN . Benchmarks using randomly generated matching problems indicate a relatively good performance even on large matching problems. Nevertheless, striking di®erences are revealed by direct comparison of the ALN - and the ALE-algorithm w.r.t. FL:-matching problems.
¤Supported by the DFG under grant BA 1122/4-3 Syntax >; ? :P; P 2 Ncon C u D 8r:C 9r:C (· n r), n 2 (¸ n r), n 2
Semantics
¢I ; ; ¢I n P I
CI \ DI fx 2 ¢I j 8y : (x; y) 2 rI ) y 2 CI g fx 2 ¢I j 9y : (x; y) 2 rI ^ y 2 CI g fx 2 ¢I j #fy j (x; y) 2 rI g · ng fx 2 ¢I j #fy j (x; y) 2 rI g ¸ ng
ALN
x
x
x
x
x
x
been implemented [
In order to answer this question, we have conducted benchmarks on randomly generated matching problems. In addition to testing the ALN -matching algorithm individually, we have directly compared the performance of both matching algorithms, i.e., the existing one for ALE and the new one for ALN . To this end, randomly generated FL:-matching problems have been used, FL: being the largest intersection between ALE and ALN .
The present paper is structured as follows. Basic notions related to the DLs under consideration are de¯ned in Section 2. The existing ALN -matching algorithm is discussed in Section 3. The actual implementation is presented in Section 4. The results of our benchmarks can be found in Sections 4.1 and 4.2. 2
Concept descriptions are inductively de¯ned with the help of a set of concept constructors, starting with a set Ncon of concept names and a set Nrole of role names. In this paper, we consider concept descriptions built from the constructors shown in Table 1. The DL FL: provides the constructors top-concept (>), bottom-concept (?), primitive negation (:P ), conjunction (C u D), and value restriction (8r:C). ALE extends FL: by existential restrictions (9r:C) while ALN extends FL: by number restrictions ((· n r) and (¸ n r)).
In order to de¯ne matching problems we also need to introduce concept patterns. These are de¯ned w.r.t. a ¯nite set Nvar of concept variables distinct from Ncon and Nrole. Concept patterns are an extension of concept descriptions in the sense that they allow for primitive concepts A 2 Ncon and concept variables X 2 Nvar as atomic constructors. The only restriction is that concept variables may not be negated.
A concept description C1 is subsumed by a description C2 (C1 v C2) i® C1I µ C2I holds for all interpretations I. The concept descriptions C1 and C2 are equivalent (C1 ´ C2) i® they subsume each other.
An L-substitution ¾ is a mapping from Nvar into the set of all L-concept descriptions. Substitutions are extended to concept patterns by induction on the structure of the pattern, modifying only the occurrences of variables in the pattern. The notion of subsumption is extended to L-substitutions as follows. An L-substitution ¾ is subsumed by an L-substitution ¿ (¾ v ¿ ) i® ¾(X) v ¿ (X) for all X 2 Nvar. With these preliminaries we can de¯ne matching problems. De¯nition 1 Let C be an L-concept description and D be an L-concept pattern. Then, C ´? D is an L-matching problem1. An L-substitution ¾ is a matcher i® C ´ ¾(D). A matcher ¾ is the least matcher to C ´? D i® for every matcher ¿ to C ´? D it holds that ¾ v ¿ . 3
Matching in ALN has been well-investigated in [
Consider an arbitrary ALN -concept description C over Ncon, Nrole, and over sets N¸ and N· of number restrictions of the form (¸ n r) and (· n r), respectively. Exhaustively applying the equivalence 8r:(C1 u C2) ´ 8r:C1 u 8r:C2 from left to right, we can represent C as a conjunction of concepts of the form 8r1: ¢ ¢ ¢ 8rn:¦, where ¦ is the bottom-concept, a (negated) primitive concept, or a number restriction. Abbreviating 8r1: ¢ ¢ ¢ 8rn:¦ by 8r1 : : : rn:¦, we can interpret r1 : : : rn as a word over the alphabet Nrole. Collecting all these words separately for the bottom-concept, for every (negated) primitive concept, and for every number restriction, we obtain a representation of C of the form C ´
u ¦2f?g[Ncon[f:P jP 2Ncong[N¸[N· 8U¦:¦, where every U¦ is a formal language over Nrole. Note that the occurrence of ¦ on top-level can be represented by including " in the corresponding role language.
1In contrast to [
Moreover, if ¦ does not occur in C at all then U¦ = ;. ALN -concept patterns can be represented in FL0-normal form by treating variables like primitive concepts. Hence, it su±ces to extend the above representation by role languages UX for every variable X 2 Nvar. The following example illustrates this. Example 2 Let Ncon := fAg, Nrole := fr; sg, N¸ := f(¸ 3 r)g, N· := ;, and Nvar := fX; Y g. Then the pattern D := A u 8r:? u 8s:(8r:A u (¸ 3 r) u X) u X can be represented in FL0-normal form as
8frg:? u 8f"; srg:A u 8;::A u 8fsg:(¸ 3 r) u 8f"; sg:X u 8;:Y .
By means of the FL0-normal form, a matching problem can be viewed as a problem over formal languages. In order to simplify the presentation of the ALN matching algorithm, we introduce two auxiliary functions on formal languages. De¯nition 3 For arbitrary formal languages U , V over Nrole and r 2 Nrole, de¯ne U ¡±V := Tu2U fv0 j uv0 2 V g and U ¢ r¡1 := fu0 j u0r 2 U g.
We can now introduce one main result from [
Lemma 4 Let C ´? D be an ALN -matching problem over Ncon, Nrole, and over number restrictions N¸ and N·. Let the FL0-normal form of C be represented by role languages of the form U¦ quanti¯ed over every ¦ 2 f?g [ Ncon [ :Ncon [ N¸ [ N· [ Nvar. Analogously, let D be represented by role languages V¦.
Then, either C ´? D is not solvable or it has a least matcher ¾ that assigns to each variable X the concept description ¾(X) de¯ned by ¾(X) := 8W?X :? u
u ¦2Ncon[:Ncon[N¸[N· 8((VX ¡±W¦X ) n (VX ¡±EC )):¦, where EC = fw 2 Nr¤ole j C v 8w:?g, W?X is a role language of polynomial size in C with W?X ¢ Nr¤ole = VX ¡± EC , and all other role languages of the form W¦X are de¯ned as follows. if ¦ 2 Ncon [ :Ncon if ¦ =: (¸ n r) 2 N¸ >> S U(·mr) [ EC ¢ r¡1 if ¦ =: (· n r) 2 N· > >:m·n
There are two obvious strategies to decide whether the substitution ¾ de¯ned
above actually solves the matching problem C ´? D. We might either ascertain
the solvability of C ´? D before computing ¾, or we might compute ¾ ¯rst
and decide the equivalence C ´ ¾(D) afterwards. In [
As the second strategy is computationally equivalent but more easily
explained, we deviate from the original in [
Lemma 5 Let C1 and C2 be ALN -concept descriptions over Ncon, Nrole, and over number restrictions N¸ and N·. Let the FL0-normal forms of C1 and C2 be represented by role languages of the form U¦ and V¦, respectively. Then, C ´ D i® for every ¦ 2 Ncon [ :Ncon, for every (¸ n r) 2 N¸, and for every (· n r) 2 N· it holds that
EC1 = EC2
U¦ [ EC1 = V¦ [ EC2 [ U(¸mr) [ EC1 = [ V(¸mr) [ EC2 m¸n m¸n [ U(·mr) [ EC1 ¢ r¡1 = [ V(·mr) [ EC2 ¢ r¡1, m·n m·n (?) (¦) where ECi = fw 2 Nr¤ole j Ci v 8w:?g for i = 1; 2.
Informally, the ALN -matching algorithm can now be described as follows. Upon input C ´? D, (i) transform C and D into FL0-normal form, (ii) construct the candidate solution ¾ de¯ned in Lemma 4, and (iii) test whether C and ¾(D) satisfy the formal language equations shown in Lemma 5. If they do, return the least matcher ¾, otherwise return `fail'. It remains to provide a method by which to solve Steps (ii) and (iii) in polynomial time.
To this end, so-called `tree-like automata' [
Example 6 Let Nrole = fr; sg. Then the role language f"; sg [ frsg ¢ Nr¤ole can be represented by a tree-like automaton A of the form
A r s s r; s where
denotes the initial state and double circles denote ¯nal states.
It has been shown in [
As a consequence, tree-like automata can be used to construct the candidate solution ¾ de¯ned in Lemma 4 in polynomial time. It remains to show how tree-like automata can be used to test whether ¾ actually is a solution.
Consider a matching problem C ´? D in FL0-normal form with a candidate solution ¾ as de¯ned in Lemma 4. Instantiating the entire system of equations from Lemma 5 by C and ¾(D) is beyond the scope of this paper. Nevertheless, as a typical example, we discuss Equation (¦) de¯ned for every ¦ 2 Ncon [ :Ncon. Inserting the role languages from C and ¾(D), we obtain the following equation.
[
X2Nvar U¦ [ EC = V¦ [ E¾(D) [
VX ¢ ¡VX ¡±(U¦ [ EC )¢ (¤) Assume that Equation (?) has already been tested, i.e., EC = E¾(D). By de¯nition of ¡±, the union over all X 2 Nvar on the right-hand side of (¤) is always a subset of the left-hand side of the equation. Hence, Equation (¤) holds i® (i) V¦ µ UA [ EC and (ii) for all u 2 U¦ either (iia) u 2 VX [ E¾(D) or (iib) u 2 VX ¢ VX ¡±U¦ or (iic) u 2 V¦ ¢ VX ¡±EC . Condition (i) can be decided by testing the tree-like automaton of V¦ \ (U¦ [ EC ) for emptyness. For Condition (iia), merely the word problem w.r.t. the tree-like automaton for V¦ [ E¾(D) must be decided for every u 2 U¦. Since there is no concatenation de¯ned for tree-like automata, the remaining Conditions (iib) and (iic) cannot be solved by means of one single treelike automaton. Nevertheless, one can show that u 2 VX ¢ VX ¡±U¦ i® fug ¡± VX \ VX ¡± U¦ is not empty, which again can be decided by a tree-like automaton in polynomial time. Case (iic) is analogous. The other equations from Lemma 4 can be decided similarly.
This completes our overview of matching in ALN . In the following section, we will explain how the theoretical algorithm described above can be implemented.
In order to implement the ALN -matching algorithm introduced previously, appropriate data structures for the representation of concept descriptions, concept patterns, and tree-like automata are necessary.
As the algorithm is de¯ned w.r.t. the role languages of the FL0-normal form of its input, it seems expedient to begin by translating the input matching problem into an array of sets of lists over symbols, the symbols representing the alphabet Nrole. Our data structure for tree-like automata resembles the inductive representation of trees: a vector the elements of which are either atomic objects or again vectors. In our case, we only additionally have to discriminate non¯nal from ¯nal nodes and ordinary leaves from those accepting Nr¤ole. In order to decide word-problems more quickly, vectors representing non-leaf nodes are implemented as arrays instead of lists.
The overall strategy of the implementation corresponds to the steps described
in Section 3. As implementation language, we chose Common LISP because it
proved well-suited to realize our representation of tree-like automata. Moreover
choosing LISP makes our implementation compatible to the system Sonic [
Benchmarks
In order to test the performance of our implementation on a su±ciently large set
of data, we had to resort to randomly generated matching problems. A similar
approach was used for the implementation of an ALE -matching algorithm [
Randomly generating C and D independently of each other makes it very unlikely that a matcher for C ´? D exists. Hence, we randomly generate a concept C and then construct a concept pattern D from C by randomly replacing sub-concepts of C by variables. Matching problems obtained thus are not necessarily solvable because of multiple occurrences of the same variable. As a simple example, consider C := 8r:A u 8s:B and D := 8r:X u 8s:X. Then, C ´? D has no solution. Note also that assuming the concept pattern D to be smaller than C seems justi¯ed especially when viewing matching as querying over KBs.
The generated random matching problems were in°uenced by a vector of probabilities controlling the depth and width of the resulting concept C as well as the frequency of the di®erent constructors available in ALN and the variables in D. Our benchmarks comprise a total of about 22,000 matching problems in 220 groups, each of which was generated with a unique probability vector. Moreover, we have generated another 12,000 matching problems which, though random, were constructed to be always solvable. The maximum problem size, i.e., the sum of the sizes of C and D, was limited by 1000. The benchmarks were ALN-match ALN-match 1500 500 0
0 measured on a standard PC with one 1.7GHz Pentium-4 processor and 512MB of memory. Computing overall averages, the algorithm takes 0.8 seconds to solve a matching problem of size 528 with D being two thirds the size of C.
Figure 1 gives a more detailed account of our ¯ndings. Diagram (a) shows the result of our benchmarks as a scatterplot together with a ¯tting function computed by the least-squares method. One dot in the diagram represents one matching problem C ´? D. In the diagram, the horizontal position of every dot represents the sum of the sizes C and D while the vertical position represents the time necessary to solve the problem.
The ¯tting function in Figure 1(a) not only matches the overall average fairly well, but also shows the general trend of the expected computation time for larger problems. A problem of size, e.g., 800 increases the computation time to about 1.5 seconds. Nevertheless, the `darker' cluster below the ¯tting function indicates that the majority of the problems are solved in less than one second.
Astonished by the strong dispersion of the scatterplot in Figure 1(a), we have rearranged the plot so that the horizontal position of every dot representing a matching problem C ´? D is determined by the size of C alone, thus ignoring the size of D. This rearrangement produces the scatterplot in Figure 1(b).
Comparing diagrams (a) and (b), the ¯rst immediate observation is that the the size of C in°uences the computation time stronger than the size of D| although on average the size of D is two thirds the size of C. Moreover, we observe one cluster of simpler matching problems and another cluster of `hard' ones, where a problem of size 400 on average already seems to take 2 seconds to solve. Analysis of our data revealed that the `hard' cases comprise exactly those problems which, though random, were designed to be solvable.
As we do not have the means to verify these ¯ndings by matching problems from realistic applications, we cannot rule out that the above ¯ndings are speci¯c to randomly generated matching problems. Nevertheless, it seems expedient 1500 to aim future optimizations of the ALN -matching algorithm at improving the computation time for solvable matching problems. 4.2
A comparison to the ALE -matching algorithm The fact that a matching algorithm for the DL ALE has already been implemented o®ers the unique opportunity to compare the ALN - to the ALE -matching algorithm head-to-head on FL:-matching problems, the largest intersection of ALN and ALE . This comparison might be interesting for two reasons. Firstly, both algorithms take a totally di®erent approach to solving a matching problem C ´? D. While the ALN -algorithm solves a system of formal language equations, the ALE -algorithm tries to construct homomorphisms from the description tree of D into that of C. Secondly, the ALN -algorithm exploits the fact that an ALN -matching problem has at most one solution while the ALE -algorithm might look for several ones.
For our comparison, we have generated a set of 34.000 FL:-matching problems in the manner described above. The results for the ALN -algorithm are similar to the ones discussed in Section 4.1. On average, a problem of size 539 was solved in 1.2 seconds by the ALN -algorithm, compared to just 0.25 seconds by the algorithm for ALE . The resulting scatterplots for the ALN -algorithm are not shown here because they closely resemble the ones in Figure 1. The scatterplots for the ALE -algorithm are shown in Figure 2.
The plot in Figure 2(a) shows that the majority of matching problems is solved in less than 0.25 seconds with relatively fewer cases strongly deviating upwards. Moreover, the ¯tting function indicates that even a problem of size 1000 is usually solved in about 0.5 seconds.
The discrimination by ordinary matching problems and those designed to be solvable, see Figure 2(b), shows that our ¯ndings from the ALN -algorithm are exactly reversed. The ALE -algorithm apparently had no di±culty with solvable matching problems while the `hard' cases are comprised of those problems of which many have no solution. 5
In the present paper, we have presented an implementation of the ALN -matching
algorithm de¯ned in [
Our benchmarks show that even large ALN -matching problems can be solved relatively quickly. Analysis indicates that solvable matching problems tend to consume much more time than those without a solution. This suggests for potential optimizations to aim at constructing solutions more quickly and not at trying to identify unsolvable problems earlier.
The validity of our ¯ndings is weakened by the fact that only randomly generated data was available for benchmarks. It is an open questions whether both implementations, the one for ALN as well as the one for ALE , behave similar on matching problems from realistic applications. Nevertheless, our comparison suggest that without major optimization the ALE -matching algorithm seems the more auspicious starting point for an extension to matching in ALEN .