In this paper a new query answering system is presented for querying knowledge bases in the Semantic Web. The implementation follows the DAML+OIL Query Language Abstract Specication (DQL) and supports acyclic conjunctive queries. The system uses a Description Logic (DL) reasoner to answer the queries and the conjunctive queries are transformed into DL retrieval or boolean queries. After the introduction to the new DQL implementation, a comparison with other systems follows. This includes the recently introduced new Racer Query Language (nRQL), the DQL implementation provided by the Knowledge Systems Laboratory of the Stanford University and a DQL implementation provided by the University of Maryland, Baltimore County. The paper highlights and compares the dierent approaches of these systems.
Current Description Logic (DL) systems [
The DQL Specication To overcome some of these limitations, the DAML
Joint Committee announced in August 2002 the DAML Query Language (DQL)
Abstract Specication and replaced it in April 2003 with a new release [
DQL Implementations Recently a new system, developed at the University of Manchester,1 became available. The implementation relies on DL reasoners transforming incoming queries to DL statements that can be passed to a DL reasoner. This transformation process is described in detail in the next section.
Two other implementations were already available: one provided by the
Knowledge Systems Laboratory of the Stanford University (KSL) 2 and the other
developed at the University of Maryland, Baltimore County (UMBC). All three
systems use dierent approaches to answer queries, and Section 3 provides a brief
comparison. The comparison also includes the DL reasoner Racer, which has
recently been extended with its own new Racer Query Language (nRQL) [
If one intends to use a DL reasoner to answer DQL queries, a transformation of
the query is in most cases necessary. One reason for this is, that DQL allows to
query for n-tuples of individuals, which is currently not supported by standard
DL reasoners. With DQL a user can also use dierent kinds of variables in a
query. To understand the dierent variables, the semantics of a DQL query and
a query answer has to be explained. A DQL query contains a query pattern that
represents a set of DAML+OIL (OWL) sentences in which some URI references
1http://www.cs.man.ac.uk/~glimmbx/download/DQL.zip
2http://ksl.stanford.edu/projects/owl-ql/owql-20040623.zip
are replaced by variables. A query answer provides bindings of URI references
or literals to some of the variables. After applying the bindings to the variables
and treating the remaining variables as existentially quantied, the resulting
statement must be entailed by the knowledge bases (KB) used to answer the
query. Variables for which a binding is required are called distinguished or
must-bind variables , variables for which no binding should be returned are called
non-distinguished or don’t-bind variables , and variables for which a binding may
be returned are called may-bind variables . May-bind variables do not add any
power to the language, because the query answer can also be computed by a
sequence of queries using only must-bind and don’t-bind variables [
Conjunctive queries are of the form h~xi ← conj(~x; ~y; ~z). The vector ~x consists of so called distinguished variables that will be bound to individual names of the knowledge base used to answer the query. The vector ~y consists of nondistinguished variables, which are existentially quantied variables. The vector ~z consists of individual names, and conj(~x; ~y; ~z) is a conjunction of atoms. An atom is of the form v1:C or hv2, v3i:r where C is a concept name, r is a role name and v1, v2, v3 are individual names from ~z or variables from ~x or ~y. For easy readability, must-bind variable names in a query are prexed with ?, don’t-bind variables are prexed with !, and individual names are not prexed and start with a letter. Concept names are written in upper case letters, while role and individual names are written in lower case. 2.2
A conjunctive query q can be represented as a directed labelled graph G(q) := hV, Ei, where V is a set of vertices, and E is a set of edges. The set V consists of the union of the elements in ~x, ~y, and ~z. The set E consists of all pairs hv1, v2i, such that v1, v2 ∈ V and hv1, v2i:r is an atom in q. A node v ∈ V is labelled with a concept C1 u . . . u Cn such that, for each Ci, v:Ci is an atom in q. Each edge e ∈ E is labelled with a set of role names {r | hv1, v2i:r is an atom in q}.
The function L(v), v ∈ V returns the label for v. If L(v) is empty, the top concept (>) is returned. The function L(e), e ∈ E returns a set of edge labels for e. The function L−(e), e ∈ E returns a set of inverted edge labels, such that L−(e) = {r|r− ∈ L(e)}. The function f lip(G, hv1, v2i), hv1, v2i ∈ E creates a new graph G0 := hV 0, E0i, with V 0 := V , E0 := (E \ {hv1, v2i}) ∪ {hv2, v1i}, and L(hv2, v1i) = L−(hv1, v2i). The function pred(v1), v1 ∈ V returns a set of vertices {v1|v1, v2 ∈ V ∧ hv2, v1i ∈ E}.
Two vertices v1, v2 ∈ V are adjacent, if L(hv1, v2i) 6= ∅ or L(hv2, v1i) 6= ∅. The vertex v1 ∈ V is reachable from v2 ∈ V , if v1 is adjacent to v2 or if there is a another vertex v3 ∈ V such that v3 is adjacent to v1, and v2 is reachable from v3. The graph G(q) is cyclic, if there is a v ∈ V , such that L(hv, vi) 6= ∅ or if there is a v0 ∈ V , such that v is adjacent to v0 and if one element is removed from L(hv, v0i), v0 is still reachable from v. q is an acyclic conjunctive query if G(q) is not cyclic. 2.3
Conjunctive queries are not supported directly by a DL reasoner. If a query contains only distinguished variables, one could replace all variables with individual names from the knowledge base and use a sequence of instantiation queries to determine if the statement is true in the knowledge base. To compute a complete query answer set with this approach, it is necessary to test all possible combinations of individual names. This is very costly, and furthermore, this approach is not applicable to queries with non-distinguished variables.
In 2001 Tessaris [
The basic principle behind the rolling-up technique is based on the semantic
equivalence of the two formulae h?xi ← ?x:C ∧ h?x, !yi:r and h?xi ← ?x:(C
u ∃ r.>) [
First of all, the query graph is transformed into a tree with the distinguished variable as root. The function f lip(G, e), e ∈ E is applied to change edge directions if necessary to transform the graph into a proper tree. The left hand part of Figure 2 shows the resulting tree. Then the rolling-up starts from the leaves of the tree. A leaf, e.g. !z, is selected and the vertex and its incoming edge are replaced by conjoining the concept ∃ L(pred(!z), !z).L(!z) to the label of pred(!z). The right hand part of Figure 2 shows the result of the rst rolling-up step. The > conjunct could be omitted without changing the semantics. This step is applied to each leaf until only the distinguished variable at the root is remaining. The label of the root node can now be used to retrieve the individual names that are valid bindings for the distinguished variable. For this example these are instances of the concept PERSON u ∃ owns.> u ∃ loves.(> u ∃ haschild−.>).
Queries with Individual Names In a DL that supports the oneOf
constructor, which allows the denition of a concept by enumerating its instances,
the rolling-up can use the individual name directly in the concept expression.
Nodes for an individual name can then be treated like a non-distinguished
variable with the concept {individual name} as label. E.g., the query h?xi ←
h?x, maryi:loves is rolled-up into a retrieval query for instances of the
concept ∃ loves.{mary}. Unfortunately most reasoners do not support the oneOf
constructor, but it is still possible to deal with such queries using a so called
representative concept [
= {T , A} = {CAR v ∃ ownedby.PERSON} = {acar:CAR} Queries with Multiple Distinguished Variables If a query contains multiple distinguished variables, the query can not be rolled-up into a single DL retrieval query. To avoid a test of all possible combinations of individual names, as necessary for the simple approach described in Section 2.3, the rolling-up technique is nevertheless helpful. To start the query answering process, one of the distinguished variables is selected as the root node, and all other variables are treated as non-distinguished. The query graph is transformed into a tree and the rolling-up process is applied as described above for the case with only one distinguished variable. The retrieved individual names are candidates for the binding of the variable. This step is repeated for all distinguished variables.
Not every combination of the retrieved candidates is possible, and to determine the valid combinations further boolean tests are necessary. To avoid as many boolean tests as possible further optimisations can be used at this point. 2.4
One promising approach is to use an iterative process that eliminates unsuitable combinations as soon as possible. Consider, e.g., the query and its query graph in Figure 3, where ?x has four candidates (i.e., x1 . . . x4), ?y has two candidates (y1, y2), and ?z has ten candidates (z1, . . . , z10) after the rolling-up.
If we had not used the rolling-up to retrieve the candidates, the number of necessary boolean tests would have been factorial in the number of named individuals in the KB. With the rolling-up and boolean tests for all possible candidate combinations, the number of tests is still the product of the number of candidates, i.e., 80 tests in this example. An optimised strategy could start at the variable with the most candidates (i.e., ?z) and retrieve the concept instances of ∃ s−.Py1, where Py1 is the representative concept for y1. In this way, one can determine which of the candidates for ?z are related to y1. This is repeated for y2. By testing for valid pairs rst, one can skip many unnecessary test, e.g., if y1 and z1 are not related, no tests for candidates of ?x are necessary. The process is repeated for the variable with the next highest number of candidates (i.e., ?x). Compared to the 80 boolean tests necessary before, this approach needs four retrieval queries to determine the valid candidate combinations.
Another optimisation could use structural knowledge about the roles in the KB to exclude impossible candidate combinations even before the above tests are used. The system developed in Manchester does not yet fully implement these optimisations.
The algorithm described in the previous section was used to implement a web
service, compliant with the DQL specication (except for some unsupported
features, e.g., the use of multiple KBs to answer a query). The system answers
acyclic conjunctive queries correctly and completely and can be used with any
DIG [
As an example, consider again the KB in Example 2.1 on page 5. The query h?xi ← ?x:CAR ∧ h?x, !yi:ownedby ∧ !y:PERSON is correctly answered with the binding acar for ?x. However, the slightly modied query h?xi ← ?x:CAR ∧ h?x, !yi:ownedby ∧ !y:CAR, asking for a car that is owned by a car, is also answered with the binding acar for ?x.
Both implementations were also tested with a second, more complicated query: h?xi ← h?x, !yi:r u h!y, b1i:r u !y:C against the KB in gure 4. The query asks for individuals that have an r successor that is a C and that has b1 as r successor. The diculty is that in this case there is no nameable instance of the concept C, but it can be inferred that either c1 or c2 is a C. Using this inference, a1 is clearly a correct binding for ?x. However, the KSL implementation also provides c1 and c2 as a binding for ?x.
It seems that the system has diculties with non-distinguished variables, and queries often cause unexpected results. The reasons for this behaviour could be due to the communication with the used theorem prover or in the theorem prover itself. If the implementation is improved in this respect, however, it would provide a powerful and complete implementation of the DQL specication. For practical use, the system would benet from better error handling and error explanation and a detailed documentation would be desirable.
The UMBC Implementation Another DQL implementation (compliant to
the predecessor of the current DQL specication) has been realised by the
University of Maryland, Baltimore County (UMBC). 4 DQL was implemented by
the UMBC for communication between agents in a multi-agent environment.
The implementation is based on the FIPA protocol, 5 and has no publicly
available query interface. DQL is only used internally for specic agent to agent
communication tasks. Therefore the implementation is probably not interesting
for users who look for a better query support in general, and the system is not
further introduced here. The reasoning in this system is based on JESS (Java
Expert System Shell).6
The new Racer Query Language The recently introduced new Racer
Query Language (nRQL) [
Another feature, which was added to nRQL, is negated query atoms, implemented using a negation as failure semantics. This is contrary to the Open World semantics normally used in DL systems (and also by Racer). nRQL uses the same operator ( not) for negated query atoms and for concept negation, which could probably lead to confusion and the users have to be care4http://www.cs.umbc.edu/~finin/papers/dqlFIPA.html 5http://www.fipa.org/ 6http://herzberg.ca.sandia.gov/jess/ ful with the formulation of such a query. The nRQL query (retrieve (?x) (not (?x PERSON))), using the negation as failure semantics, therefore returns acar. Due to the Open World semantics for concept negation, the modied query (retrieve (?x) (?x (not PERSON))) returns an empty answer set, since Racer cannot prove that acar is not an instance of the concept person.
nRQL oers more features than the ones described here and for details the reader is referred to the Racer documentation.7 4
Eorts are currently being made, to develop better query support for knowledge representation systems. The establishment of OWL as a W3C recommendation may also promote the proposed OWL-QL specication 8 and so encourage improvements for the currently available systems or the development of new query answering systems.
So far, all introduced systems have some drawbacks. The Stanford implementation covers all features dened by the DQL specication, but delivers in some cases incorrect answers and rejects some queries, without providing an answer. The Manchester implementation does not support all DQL features and is restricted to acyclic conjunctive queries. Both systems are available as Java applications and the Stanford implementation is also available as a servlet, while the Manchester implementation is also available as a web service. Both provide a web client interface and are able to deal with OWL and DAML+OIL knowledge bases.
The UMBC implementation is not publicly available and does not, therefore, help to improve query support for knowledge bases in general. nRQL provides richer query support, but is not meant as a DQL implementation and is therefore missing many DQL features. In addition, the restriction that a binding is required for all variables, even for those not expected to appear in the answer set, would make it dicult to formulate queries such as the one in Section 3 against the KB in gure 4. Apart from this, nRQL is easy to use, and the documentation provides a good introduction to the new features of nRQL.
For all described systems there are still improvements possible. One main topic for query answering systems is scalability. The query answering times for knowledge bases with large amounts of individuals are still far away from the results achieved by databases. For the DQL implementation developed in Manchester, the boolean queries that are necessary to check valid combinations of variable bindings, can cause major delays in case of many candidates. The 7The documentation, which includes a section about nRQL, is available from the Racer download page: http://www.cs.concordia.ca/~haarslev/racer/download.html 8http://ksl.stanford.edu/projects/owl-ql system would clearly benet of a further optimisation of this phase in the query answering process, some of which were discussed in Section 2.4.