A proposal for an interface for ABox queries as part of DIG 2.0.
In many practical application systems based on DLs, a powerful ABox query language is one of the main requirements. Answering queries in DL systems goes beyond query answering in relational databases. In databases, query answering amounts to model checking (a database instance is seen as a model of the conceptual schema). Query answering w.r.t. TBoxes and ABoxes must take all models into account, and thus requires deduction. The aim is to define expressive but decidable query languages.
Well known classes of queries such as conjunctive queries and unions of conjunctive queries are topics of current investigations in this context. In the literature, two different semantics for these kinds of queries are discussed. In standard conjunctive queries, variables are bound to (possibly anonymous) domain objects. In so-called grounded conjunctive queries, variables are bound to named domain objects (object constants). However, in grounded conjunctive queries the standard semantics can be obtained for so-called tree-shape queries by using existential restrictions in query atoms.
For an ABox query language as part of DIG 2.0 we do not commit to a certain semantics. The semantics depends on the reasoner. The standard semantics is implemented in the system QuOnto [QuOnto] (for a Description Logic of the DL-Lite family) whereas the grounded semantics is implemented in RacerPro [Wessel and Möller 05], [Wessel and Möller 06], and also KAON2 [KAON2]. For all systems, an interface corresponding to the DIG 2.0 standard will be developed. A possibility to identify the fragment of the query language supported by a reasoner is foreseen in the DIG 2.0 protocol.
DIGDescribe request is sent to a DIG
server, the server must response with DIGDescription
that contains the name of the DIG server, its version, an
optional identification message, flags
for annotations and imports, and a set of names of supported
requests. This
set also can contain the request element Retrieve supportsQueryLanguage attribute of the DIGDescription
response <DIGDescription
name="Racer"
version="1.9.5"
message="Racer running on localhost"
supportsLanguage="SHIQ(D)"
supportsAnnotations="true"
supportsImports="true"
supportsQueryLanguage="ugcq">
<SupportedRequest requestName="Retrieve"/>
<SupportedRequest requestName="..."/>
...
</DIGDescription>
ConceptQueryAtom),
role query
atoms (denoted with RoleQueryAtom), same-as query atoms
(denoted with SameAsQueryAtom), different-from query atoms
(denoted with DifferentFromQueryAtom) as well as concrete domain
query atoms (denoted with ConcreteDomainQueryAtom).
The latter are introduced to provide support for querying
the concrete domain part of a knowledge base. Retrieve request is derived from the RequestToOntology class (which has an ontologyURI parameter). Additionaly, it has an attribute queryID as unique identification of the query (important for iterative query answering and query management) and takes a
query head (denoted with QueryHead) and a
query body (denoted with QueryBody). Within the QueryHead
tag Abox individuals and variables (denoted as QueryVariable)
can be used. Variables are bound to
those individuals which satisfy the query. For boolean queries, the
head must be empty. QueryObjectIntersectionOf), union (QueryObjectUnionOf)
and negation (QueryObjectComplementOf) (for the latter,
for instance, negation as failure semantics is assumed).
Concept query atoms consist of variables (or individuals)
and complex concept expressions. Role query atoms consists of at least
two
identifiers for variables (or indidivuals) followed by a role
expression.
The following conjunctive query with id q1 asks for all individuals of the concept woman
which have female children. The requested
knowledge base is identified by means of a URI:
<Retrieve ontologyURI="myOntology.owl" queryID="q1">The following query
<QueryHead>
<QueryVariable URI="#x"/>
</QueryHead>
<QueryBody>
<QueryObjectIntersectionOf>
<ConceptQueryAtom>
<QueryVariable URI="#x"/>
<owl:ObjectIntersectionOf>
<owl:OWLClass owl:URI="#woman"/>
<owl:ObjectSomeValuesFrom>
<owl:ObjectProperty owl:URI="#hasChild"/>
<owl:OWLClass owl:URI="#female"/>
</owl:ObjectSomeValuesFrom>
</owl:ObjectIntersectionOf>
</ConceptQueryAtom>
</QueryObjectIntersectionOf>
</QueryBody>
</Retrieve>
q2 consists of
conjunction of
a concept query atom and a role query atom. It returns all mother-child
pairs (bound to variables x and y): <Retrieve ontologyURI="myOntology.owl" queryID="q2">The boolean query
<QueryHead>
<QueryVariable URI="#x"/>
<QueryVariable URI="#y"/>
</QueryHead>
<QueryBody>
<QueryObjectIntersectionOf>
<ConceptQueryAtom>
<QueryVariable URI="#x"/>
<owl:OWLClass owl:URI="#woman"/>
</ConceptQueryAtom>>
<RoleQueryAtom>
<QueryVariable URI="#x"/>
<QueryVariable URI="#y"/>
<owl:ObjectProperty owl:URI="#hasChild"/>
</RoleQueryAtom>
</QueryObjectIntersectionOf>
</QueryBody>
</Retrieve>
q3 asks if there
are any individuals of the concept woman in
the current ABox:
<Retrieve ontologyURI="myOntology.owl" queryID="q3">Instead of variables, also ABox individuals can be used in the query, as illustrated by example of the following (boolean) query
<QueryHead>
</QueryHead>
<QueryBody>
<QueryObjectIntersectionOf>
<ConceptQueryAtom>
<QueryVariable URI="#x"/>
<owl:OWLClass owl:URI="#woman"/>
</ConceptQueryAtom>
</QueryObjectIntersectionOf>
</QueryBody>
</Retrieve>
<Retrieve ontologyURI="myOntology.owl" queryID="q4">As mentioned above, within the
<QueryHead>
</QueryHead>
<QueryBody>
<QueryObjectIntersectionOf>
<ConceptQueryAtom>
<owl:Individual owl:URI="#eve"/>
<owl:OWLClass owl:URI="#woman"/>
</ConceptQueryAtom>
</QueryObjectIntersectionOf>
</QueryBody>
</Retrieve>
Retrieve
statement we can build unions
of conjunctive queries using the operator QueryObjectUnionOf
in front of the conjunctive queries:<TheQueryObjectUnionOf>
<QueryObjectIntersectionOf>
[...]
</QueryObjectIntersectionOf>
[...]
<QueryObjectIntersectionOf>
[...]
</QueryObjectIntersectionOf>
</QueryObjectUnionOf>
QueryObjectComplementOf operator can be used in front of
query
body atoms, conjunctive queries and unions of conjunctive queries. For
the semantics, see below.<QueryObjectComplementOf>If a queried reasoner supports retrieving of concrete domain datatype values, this can be done by means of concrete domain query atoms (denoted as
<QueryObjectUnionOf>
<QueryObjectComplementOf>
<QueryObjectIntersectionOf>
[...]
<QueryObjectComplementOf>
[...]
</QueryObjectComplementOf>
</QueryObjectIntersectionOf>
</QueryObjectComplementOf>
</QueryObjectUnionOf>
</QueryObjectComplementOf>
ConcreteDomainQueryAtom
which consist of
variables (or individuals), concrete domain variables (or values) and
attributes. We refer to [DIG 2.0 CD
Proposal] for details on the concrete domain
interface for DIG. Please note that we distinguish between
concrete domain variables used in the query language (denoted
as ConcreteDomainQueryVariable) and concrete domain
variables (cdvar) used in the tell language.
Furthermore, we use the new tag PredicateQueryAtom as
well as tags predicate, lambda
and op (introduced in [DIG
2.0 CD Proposal]) or just op to
pose certain constraints between concrete domain objects (values or
variables). PredicateQueryAtom statement and forbid multiple occurrences of concrete domain query
variables in different ConcreteDomainQueryAtom statements.age a concrete domain attribute of
type integer. The following query retrieves all adults as well as their
ages: <Retrieve ontologyURI="myOntology.owl" queryID="q5">In the following example, we request for all individuals which have the same age (implicitly expressed by using
<QueryHead>
<QueryVariable URI="#x"/>
<ConcreteDomainQueryVariable URI="#y"/>
</QueryHead>
<QueryBody>
<QueryObjectIntersectionOf>
<ConcreteDomainQueryAtom>
<QueryVariable URI="#x"/>
<ConcreteDomainQueryVariable URI="#y"/>
<owl:DataProperty owl:URI="#age"/>
</ConcreteDomainQueryAtom>
<PredicateQueryAtom>
<ConcreteDomainQueryVariable URI="#y"/>
<owl:Constant owl:datatypeURI="&xsd;integer">
18
</owl:Constant>
<op name=">"/>
</PredicateQueryAtom>
</<QueryObjectIntersectionOf>>
</QueryBody>
</Retrieve>
y
twice):<Retrieve ontologyURI="myOntology.owl" queryID="q6">A
<QueryHead>
<QueryVariable URI="#x"/>
<QueryVariable URI="#z"/>
<ConcreteDomainQueryVariable URI="#y"/>
</QueryHead>
<QueryBody>
<QueryObjectIntersectionOf>
<ConcreteDomainQueryAtom>
<QueryVariable URI="#x"/>
<ConcreteDomainQueryVariable URI="#y"/>
<owl:DataProperty owl:URI="#age"/>
</ConcreteDomainQueryAtom>
<ConcreteDomainQueryAtom>
<QueryVariable URI="#z"/>
<ConcreteDomainQueryVariable URI="#y"/>
<owl:DataProperty owl:URI="#age"/>
</ConcreteDomainQueryAtom>
</QueryObjectIntersectionOf>
</QueryBody>
</Retrieve>
SameAsQueryAtom can be used to enforce a
binding of a variable (e.g., <QueryVariable URI="#betty"/>) to an individual (e.g., <owl:Individual owl:URI="#betty"/>), or to enforce that two
non-injective variables are bound to the same individual.<Retrieve ontologyURI="myOntology.owl" queryID="q7">Instead of
<QueryHead>
<QueryVariable URI="#x"/>
</QueryHead>
<QueryBody>
<QueryObjectIntersectionOf>
<RoleQueryAtom>
<QueryVariable URI="#x"/>
<QueryVariable URI="#y"/>
<owl:ObjectProperty owl:URI="#loves"/>
</RoleQueryAtom>
<ConceptQueryAtom>
<QueryVariable URI="#y"/>
<owl:OWLClass owl:URI="#human"/>
</ConceptQueryAtom>
<SameAsQueryAtom>
<QueryVariable URI="#x"/>
<QueryVariable URI="#y"/>
</SameAsQueryAtom>
</QueryObjectIntersectionOf>
</QueryBody>
</Retrieve>
SameAsQueryAtom one may use DifferentFromQueryAtom
to search some human that does not love
himself.QueryObjectComplementOf). We refer to [Wessel
and Möller 05], [Wessel
and Möller 06] for the semantics and a motivating
example. For DIG we propose a tag QueryProject
which can be used in any position within a query body and contains a
head and a body parts.
The following query returns all mothers which do not have a
known (i.e. explicitly modeled in an ABox) child:
<Retrieve ontologyURI="myOntology.owl" queryID="q8">In case a reasoner has to deal with large result sets for queries, iterative query answering can help to improve performance. Therefore, result sets can be retrieved iteratively using small chunks of tuples. To support the incremental loading the answer tuple by tuple, the statement
<QueryHead>
<QueryVariable URI="#x"/>
</QueryHead>
<QueryBody>
<QueryObjectIntersectionOf>
<ConceptQueryAtom>
<QueryVariable URI="#x"/>
<owl:OWLClass owl:URI="#mother"/>
</ConceptQueryAtom>
<QueryObjectComplementOf>
<QueryProject>
<QueryHead>
<QueryVariable URI="#x"/>
</Queryhead>
<QueryBody>
<RoleQueryAtom>
<QueryVariable URI="#x"/>
<QueryVariable URI="#y"/>
<owl:ObjectProperty owl:URI="#hasChild"/>
</RoleQueryAtom>
</QueryBody>
</QueryProject>
</QueryObjectComplementOf>
</QueryObjectIntersectionOf>
</QueryBody>
</Retrieve>
Retrieve can have an optional
attribute ntuples instantiated with the
maximum number of tuples which are assumed to be returned. If ntuplesis
not specified, all tuples have to be returned. In addition, DIG
2.0 supports instructions to let a query answering engine compute
results "proactively" to provide faster retrieval of subsequent chunks
of tuples. This can be achieved by setting the optional mode attribute:
<Retrieve ontologyURI="myOntology.owl" queryID="q9" ntuples=10 mode="proactive">The statement
<QueryHead>
[...]
</QueryHead>
<QueryBody>
[...]
</QueryBody>
</Retrieve>
Retrieve without head and body
is used to retrieve the next tuple(s) for a particular query identified
with queryID. The value of queryID
can be a query id or an answer set id (asID):<Retrieve ontologyURI="myOntology.owl" queryID="as9999" ntuples=5/>
ReleaseQuery, which has an attribute queryID, to which the reasoner should respond with the Confirmation response.
<ReleaseQuery queryID="q5"/>
QueryAnswers response to a Retrieval request have an
attribute queryID
which corresponds with the id of the submitted query. The answer set id
(asID)
will be generated by the reasoner. The response contains tuples
of bindings for variables mentioned in the query head. The response
head is the same as the head of the corresponding query. The head
is inserted
just for convenience; the reasoner may not reorder components of
bindings. For example, the following answer is returned for the query
with the id q2 posed above:
<QueryAnswers queryID="q2" asID="asid1000">In case of concrete domain queries, concrete domain variables (and values) can be returned. Therefore, for concrete domain query variables we introduce
<QueryHead>
<QueryVariable URI="#x"/>
<QueryVariable URI="#y"/>
</QueryHead>
<Binding>
<owl:Individual owl:URI="#mary"/>
<owl:Individual owl:URI="#betty"/>
</Binding>
<Binding>
<owl:Individual owl:URI="#susan"/>
<owl:Individual owl:URI="#peter"/>
</Binding>
</QueryAnswer>
ConcreteDomainBinding which consists of a concrete domain variable name and possible of a
value (if it can be uniquely determined). For example, the
response for the query q5 can be the
following:
<QueryAnswers queryID="q5">The response to a boolean query is a set of an empty set of bindings for
<QueryHead>
<QueryVariable URI="#x"/>
<ConcreteDomainQueryVariable URI="#y"/>
</QueryHead>
<Binding>
<owl:Individual owl:URI="#mary"/>
<ConcreteDomainBinding>
<cdvar name="age_mary"/>
<owl:Constant owl:datatypeURI="&xsd;integer">
30
</owl:Constant>
</ConcreteDomainBinding>
</Binding>
<Binding>
<owl:Individual owl:URI="#eve"/>
<ConcreteDomainBinding>
<cdvar name="age_mary"/>
</ConcreteDomainBinding>
</Binding>
</QueryAnswers>
true or an empty set for false True:
<QueryAnswers queryID="...">
<QueryHead>
[...]
</QueryHead>
<Binding>
</Binding>
</QueryAnswers>
False:
<QueryAnswers queryID="...">
<QueryHead>
[...]
</QueryHead>
</QueryAnswers>
Within the bindings statement, the tag notifier
can be used for reasoner-specific messages. E.g., considering an
incremental query answering, the reasoner can report that the given
tuple is the last one:
<QueryAnswers queryID="...">
<QueryHead>
[...]
</QueryHead>
<Binding>
[...]
</Binding>
<notifier message="last tuple"/>
</QueryAnswers>
Other messages are possible. For instance, a reasoner could
indicate
that subsequent requests for tuple will require considerably more
resources.
Motivated by this example, a reasoner might decide to return fewer
tuples
than requested with the attribute ntuples
(see above).