Motivation

Matching in Description Logics (DLs) has been first introduced by Borgida and McGuinness in the context of the Classic system [5] as a means to filter out irrelevant aspects of large concept descriptions. A matching problem (modulo equivalence) consists of a concept description C and a concept pattern D, i.e., a concept description with variables. Matching D against C means finding a substitution of the variables in D by concept descriptions such that C is equivalent to the instantiated concept pattern D.

To some extent, matching can help to find redundancies in or to integrate Knowledge Bases (KBs) [3,6]. Matching can also be employed for queries over KBs: a domain expert unable to specify uniquely the concept he is looking for in a KB can use a concept pattern to retrieve all those concepts for which a matcher exists. The structural constraints expressible by patterns exceed the capabilities of simple "wildcards" familiar from ordinary searches [7].

Matching algorithms are well-investigated for the DLs ALN , ALE, and respective sublanguages [2,1]. Only the ALE-matching algorithm, however, has Table 1: Syntax and semantics of concept descriptions.

been implemented [8]. In the present paper, we present an implementation of the ALN -matching algorithm defined in [2]. While matching in ALE is NPhard, matching in ALN is polynomial. This relation gives rise to the question whether the implementations of both matching algorithms reflect the difference in computational complexity of the theoretical problems.

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 defined 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.

Preliminaries

Concept descriptions are inductively defined with the help of a set of concept constructors, starting with a set N con of concept names and a set N role 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 D), and value restriction (∀r.C). ALE extends FL ¬ by existential restrictions (∃r.C) while ALN extends FL ¬ by number restrictions ((≤ n r) and (≥ n r)).

In order to define matching problems we also need to introduce concept patterns. These are defined w.r.t. a finite set N var of concept variables distinct from N con and N role . Concept patterns are an extension of concept descriptions in the sense that they allow for primitive concepts A ∈ N con and concept variables X ∈ N var as atomic constructors. The only restriction is that concept variables may not be negated.

A concept description C 1 is subsumed by a description

C 2 (C 1 C 2 ) iff C I 1 ⊆ C I2

holds for all interpretations I. The concept descriptions C 1 and C 2 are equivalent (C 1 ≡ C 2 ) iff they subsume each other.

An L-substitution σ is a mapping from N var 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 τ (σ τ ) iff σ(X) τ (X) for all X ∈ N var . With these preliminaries we can define matching problems.

Definition 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 iff C ≡ σ(D). A matcher σ is the least matcher to C ≡ ? D iff for every matcher τ to C ≡ ? D it holds that σ τ .

Matching in ALN

Matching in ALN has been well-investigated in [2]. In particular, it has been shown that solvable ALN -matching problems always have exactly one least matcher unique up to equivalence that can be computed in polynomial time. As the focus of this work is on implementation rather than theory, we will present the relevant matching algorithm only as detailed as necessary. For further details, see [2]. The algorithm relies on the so-called FL 0 -normal form of ALN -concept descriptions which must be introduced first.

Consider an arbitrary ALN -concept description C over N con , N role , and over sets N ≥ and N ≤ of number restrictions of the form (≥ n r) and (≤ n r), respectively. Exhaustively applying the equivalence ∀r.(C 1 C 2 ) ≡ ∀r.C 1 ∀r.C 2 from left to right, we can represent C as a conjunction of concepts of the form ∀r 1 . • • • ∀r n .Π, where Π is the bottom-concept, a (negated) primitive concept, or a number restriction. Abbreviating ∀r 1 . • • • ∀r n .Π by ∀r 1 . . . r n .Π, we can interpret r 1 . . . r n as a word over the alphabet N role . 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 ≡ Π∈{⊥}∪Ncon∪{¬P |P ∈Ncon}∪N ≥ ∪N ≤ ∀U Π .Π,

where every U Π is a formal language over N role . Note that the occurrence of Π on top-level can be represented by including ε in the corresponding role language.

Moreover, if Π does not occur in C at all then U Π = ∅. ALN -concept patterns can be represented in FL 0 -normal form by treating variables like primitive concepts. Hence, it suffices to extend the above representation by role languages U X for every variable X ∈ N var . The following example illustrates this. By means of the FL 0 -normal form, a matching problem can be viewed as a problem over formal languages. In order to simplify the presentation of the ALNmatching algorithm, we introduce two auxiliary functions on formal languages.

Definition 3 For arbitrary formal languages U , V over N role and r ∈ N role , define U • −V := u∈U {v | uv ∈ V } and U • r −1 := {u | u r ∈ U }.

We can now introduce one main result from [2] which shows how the least matcher to a solvable ALN -matching problem can be constructed. To simplify notation, let

¬N con := {¬A | A ∈ N con }.

Lemma 4 Let C ≡ ? D be an ALN -matching problem over N con , N role , and over number restrictions N ≥ and N ≤ . Let the FL 0 -normal form of C be represented by role languages of the form U Π quantified over every Π ∈ {⊥} ∪ N con ∪ ¬N con ∪ N ≥ ∪ N ≤ ∪ N var . 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) defined by

σ(X) := ∀W X ⊥ .⊥ Π∈Ncon∪¬Ncon∪N ≥ ∪N ≤ ∀((V X • −W X Π ) \ (V X • −E C )).Π,

where

E C = {w ∈ N * role | C ∀w.⊥}, W X ⊥ is a role language of polynomial size in C with W X ⊥ • N * role = V X • −E C

, and all other role languages of the form W X Π are defined as follows.

W X Π :=            U Π ∪ E C if Π ∈ N con ∪ ¬N con m≥n U (≥mr) ∪ E C if Π =: (≥ n r) ∈ N ≥ m≤n U (≤mr) ∪ E C • r −1 if Π =: (≤ n r) ∈ N ≤

There are two obvious strategies to decide whether the substitution σ defined above actually solves the matching problem C ≡ ? D. We might either ascertain the solvability of C ≡ ? D before computing σ, or we might compute σ first and decide the equivalence C ≡ σ(D) afterwards. In [2], the former strategy is taken: a system of formal language equations, so-called 'solvability equations', is proposed which is solvable iff C ≡ ? D is solvable. To decide solvability of these equations, however, necessitates computing exactly those role languages which occur in the FL 0 -normal form of σ(X) constructed in Lemma 4.

As the second strategy is computationally equivalent but more easily explained, we deviate from the original in [2] by computing a candidate solution first and testing for equivalence afterwards. To this end, we utilize a characterization of equivalence from [2] based on FL 0 -normal forms.

Lemma 5 Let C 1 and C 2 be ALN -concept descriptions over N con , N role , and over number restrictions N ≥ and N ≤ . Let the FL 0 -normal forms of C 1 and C 2 be represented by role languages of the form U Π and V Π , respectively. Then, C ≡ D iff for every Π ∈ N con ∪ ¬N con , for every (≥ n r) ∈ N ≥ , and for every (≤ n r) ∈ N ≤ it holds that

E C 1 = E C 2 (⊥) U Π ∪ E C 1 = V Π ∪ E C 2 (Π) m≥n U (≥mr) ∪ E C 1 = m≥n V (≥mr) ∪ E C 2 m≤n U (≤mr) ∪ E C 1 • r −1 = m≤n V (≤mr) ∪ E C 2 • r −1 ,

where

E C i = {w ∈ N * role | C i ∀w.⊥} 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 FL 0 -normal form, (ii) construct the candidate solution σ defined 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' [2], can be utilized. Intuitively, these are deterministic finite automata whose structure differs from a tree only in that they either have ordinary leaves or leaves with an r-transition to themselves for every r ∈ N role . Consider the following example. It has been shown in [2] that tree-like automata have the following properties.

• A tree-like automaton A that accepts E C can be constructed in polynomial time in the size of C. From A, a language U of polynomial size in C with E C = U • N * role can be constructed in linear time.

• The operations union, intersection, and complement on treelike automata can be defined in such a way that the size of the resulting automaton does not exceed the maximum of the sizes of the input automata. Moreover, all operations can be performed in linear time.

• If U, V, W are finite languages, then a tree-like automaton that accepts

U • − (V ∪ W • N * role

) can be constructed in polynomial time in the size of the input.

As a consequence, tree-like automata can be used to construct the candidate solution σ defined 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 FL 0 -normal form with a candidate solution σ as defined 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 (Π) defined for every Π ∈ N con ∪ ¬N con . Inserting the role languages from C and σ(D), we obtain the following equation.

U Π ∪ E C = V Π ∪ E σ(D) ∪ X∈Nvar V X • V X • −(U Π ∪ E C ) ( * )

Assume that Equation (⊥) has already been tested, i.e., E C = E σ(D) . By definition of • −, the union over all X ∈ N var on the right-hand side of ( * ) is always a subset of the left-hand side of the equation. Hence, Equation ( * ) holds iff (i)

V Π ⊆ U A ∪ E C and (ii) for all u ∈ U Π either (iia) u ∈ V X ∪ E σ(D) or (iib) u ∈ V X •V X • −U Π or (iic) u ∈ V Π •V X • −E C

. Condition (i) can be decided by testing the tree-like automaton of V Π ∩ (U Π ∪ E C ) 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 ∈ U Π . Since there is no concatenation defined 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 ∈

V X • V X • −U Π iff {u} • −V X ∩ V X • −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 defined w.r.t. the role languages of the FL 0 -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 N role . 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 nonfinal from final nodes and ordinary leaves from those accepting N * role . 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 [9] which provides an interface between the KB editor OilEd [4] and non-standard reasoning services. This may help to make our algorithm available to users.

Benchmarks

In order to test the performance of our implementation on a sufficiently 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 [8].

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 := ∀r.A ∀s.B and D := ∀r.X ∀s.X. Then, C ≡ ? D has no solution. Note also that assuming the concept pattern D to be smaller than C seems justified especially when viewing matching as querying over KBs.

The generated random matching problems were influenced by a vector of probabilities controlling the depth and width of the resulting concept C as well as the frequency of the different 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 The fitting 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 fitting 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 first immediate observation is that the the size of C influences the computation time stronger than the size of Dalthough 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 findings by matching problems from realistic applications, we cannot rule out that the above findings are specific to randomly generated matching problems. Nevertheless, it seems expedient to aim future optimizations of the ALN -matching algorithm at improving the computation time for solvable matching problems.

A comparison to the ALE-matching algorithm

The fact that a matching algorithm for the DL ALE has already been implemented offers 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 different 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 fitting 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 findings from the ALN -algorithm are exactly reversed. The ALE-algorithm apparently had no difficulty with solvable matching problems while the 'hard' cases are comprised of those problems of which many have no solution.

Conclusion

In the present paper, we have presented an implementation of the ALN -matching algorithm defined in [2]. Upon input C ≡ ? D, the algorithm first computes a candidate solution σ and verifies its validity afterwards. More precisely, the algorithm reduces matching problems to problems over formal languages and decides them in polynomial time with the help of tree-like automata.

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 findings 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 .