DIG 2.0 Proposal for a Concrete Domain Interface

This version:
http://www.sts.tu-harburg.de/~al.kaplunova/dig-cd-interface.html
Last change: 
2006/09/21 
Authors:
Alissa Kaplunova, Hamburg University of Technology
Ralf Möller, Hamburg University of Technology

Abstract

A proposal for an interface for concrete domain within DIG 2.0.


Concrete Domain

In many practical applications, reasoning over specific domains with fixed (concrete) semantics such as integers, reals and strings is required. For this propose, modern DL reasoners provide for a so-called concrete domain support, such that constraints over values from concrete domains referred to by multiple individuals can be postulated (e.g., linear inequations over polynomials or equations over strings). We refer to e.g. [Baader and Hanschke 91], [Haarslev et al. 01], [Horrocks and Sattler 05] for further details on DLs with concrete domain.

Concept Language

In the current DIG standard, concrete domain expressions such as intmin, stringrange and other can be used in TBox (and ABox) axioms. So, we can define the (concrete) predicate exists restriction for the attribute teenager-age as follows:
 <intequals val="18">
<attribute name="teenager-age"/>
</intequals>
The same restriction can be expressed using new tags somep and op:
 <somep>
<attribute name="teenager-age"/>
<ival> 18 </ival>
<op name="="/>
</somep>

It is also possible to use feature chains of arbitrary length such that the last argument in each chain is a concrete domain attribute. In DIG 2.0, we can use a functional dataProperty instead of an attribute. In the following example, let hasMother be a feature and age be an attribute. Using the predicate > we can express that a grandmother is older as a mother:

 <somep>
<chain>
<feature name="hasMother"/>
<feature name="hasMother"/>
<attribute name="age"/>
</chain>
<chain>
<feature name="hasMother"/>
<attribute name="age"/>
</chain>
<op name=">"/>
</somep>

We also can use the lambda expression in order to pose arbitrary predicates between feature chains.

<somep>
<chain>
<feature name="f1"/>
<feature name="f2"/>
<attribute name="a1"/>
</chain>
<chain>
<feature name="g1"/>
<feature name="g2"/>
<feature name="g3"/>
<attribute name="a2"/>
</chain>
<lambda>
<parameters>
<cdvar name="x1"/>
<cdvar name="x2"/>
</parameters>
<predicate>
<cdvar name="x2"/>
<cdvar name="x1"/>
<op name="<"/>
</predicate>
</lambda>
</somep>

We can combine different predicate statements by means of boolean operators or and and. In the next example we define conditions for a leep-year using the attribute year and the predicates divisible and not-divisible:

<and>
<somep>
<attribute name="year"/>
<ival> 4 </ival>
<op name="divisible"/>
</somep>
<or>
<somep>
<attribute name="year"/>
<ival> 100 </ival>
<op name="not-divisible"/>
</somep>
<somep>
<attribute name="year"/>
<ival> 400 </ival>
<op name="divisible"
  </somep>
</or>
</and>

Tell Language

In the current DIG standard, it is possible to make e.g. the following assertion about the age of the individual eve:
<instanceof>
<individual name="eve"/>
<intequals val="18">
<attribute name="age"/>
</intequals>
</instanceof>
However, in order also to deal with variables ranged over concrete domain values (so-called objects), we introduce new tags constrained and cdvar. The usage of these constructs is illustrated by the following example asserting that the age of the individual mary is ageMary:
<constrained>
<individual name="mary"/>
<cdvar name="ageMary"/>
<attribute name="age"/>
</constrained>
The first example can be reformulated using the new notation as follows:
<constrained>
<individual name="eve"/>
<ival> 18 </ival>
<attribute name="age"/>
</constrained>
Now, certain constraints between concrete domain objects (values or variables) can be defined. For this propose the tags constraint and predicate are introduced. E.g., the following assertion states that mary is older than 18 (as defined above, ageMary refers to the age of mary):
<constraint>
<predicate>
<cdvar name="ageMary"/>
<ival> 18 </ival>
<op name="<"/>
</predicate>
</constraint>
Within the predicate statement complex expressions can be built by means of a expr tag. We can use this tag everywhere, where also cdvar can be used.

<lambda>
<parameters>
<cdvar name="x"/>
<cdvar name="y"/>
<cdvar name="z"/>
</parameters>
<predicate>
<expr>
<cdvar name="x"/>
<cdvar name="y"/>
<op name="+">
</expr>
<cdvar name="z"/>
<op name="<"/>
</predicate>
</lambda>

Ask Language

DL systems with support for concrete domains offer an additional inference service considering the entailment of certain predicates. Therefore, it is appropriate to foresee the new ask statement for this type of queries. We denote it with entailed. As each other asks element, this statement must have a unique id. The response to the entailed query is true if a specified constraint is entailed by a knowledge base, and false otherwise. The following code illustrates the idea:
 <asks
xmlns="http://dl.kr.org/dig/lang/schema"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://dl.kr.org/dig/lang/schema
http://dig.cs.manchester.ac.uk/schema.xsd"
uri="'urn:uuid:...">
<entailed id="q1">
<predicate>
<cdvar name="x"/>
<cdvar name="y"/>
<op name="<"/>
</predicate>
</entailed>
</asks>
To sum up, we present a complete example of using the concrete domain interface within DIG. Given two ABox individuals charles and william which have a concrete domain attribute age, we assert that william is younger than charles and the age of william is 24. Then the reasoner is asked whether charles is older than 20, what is obviously true.
 <tells
xmlns="http://dl.kr.org/dig/lang/schema"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://dl.kr.org/dig/lang/schema
http://dig.cs.manchester.ac.uk/schema.xsd"
uri="'urn:uuid:...">

<constrained>
<individual name="charles"/>
<cdvar name="age_charles"/>
<attribute name="age"/>
</constrained>

<constrained>
<individual name="william"/>
<cdvar name="age_william"/>
<attribute name="age"/>
</constrained>

<constraint>
<predicate>
<cdvar name="age_charles"/>
<cdvar name="age_william"/>
<op name=">"/>
</predicate>
</constraint>

<constraint>
<predicate>
<cdvar name="age_william"/>
<ival> 24 </ival>
<op name="="/>
</predicate>
</constraint>
</tells>

<asks
xmlns="http://dl.kr.org/dig/lang/schema"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://dl.kr.org/dig/lang/schema
http://dig.cs.manchester.ac.uk/schema.xsd"
uri="'urn:uuid:...">
<entailed id="q2">
<predicate>
<cdvar name="age_charles"/>
<ival> 20 </ival>
<op name=">"/>
</predicate>
</entailed>
</asks>

<responses
xmlns="http://dl.kr.org/dig/lang/schema"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://dl.kr.org/dig/lang/schema
http://dig.cs.manchester.ac.uk/schema.xsd"
<true id="q2"/>
</responses>

Decidability Issues

The DL reasoner is responsible for determining whether sound and complete reasoning can be provided for various combinations or feature chains, GCIs (or transitive roles and role hierarchies) and particular concrete domains. (see e.g. [Lutz 03]).

References

[Baader and Hanschke 91]
Franz Baader and Philipp Hanschke. A schema for integrating concrete domains into concept languages. In Proc. of the 12th Int. Joint Conf. on Artificial Intelligence (IJCAI'91), pages 452-457, 1991.
[Bechhofer et al. 03]
S. Bechhofer, R. Möller, and P. Crowther. The DIG Description Logic Interface. In Proceedings of the International Workshop on Description Logics (DL-2003), Rome, Italy, September 5-7, 2003.
[DIG1.0]
Sean Bechhofer. The DIG Description Logic Interface: DIG/1.0. http://dl-web.man.ac.uk/dig/2002/10/interface.pdf
[DIG1.1]
Sean Bechhofer. The DIG Description Logic Interface: DIG/1.1. http://dl-web.man.ac.uk/dig/2003/02/interface.pdf
[Haarslev et al. 01]
Volker Haarslev, Ralf Möller and Michael Wessel. The Description Logic ALCNHR+ Extended with Concrete Domains: A Practically Motivated Approach. In R. Goré, A. Leitsch, and T. Nipkow, editors, International Joint Conference on Automated Reasoning, IJCAR'2001, June 18-23, Siena, Italy, pages 29-44. Springer-Verlag, 2001.
[Horrocks and Sattler 05]
Ian Horrocks and Ulrike Sattler. A tableaux decision procedure for SHOIQ. In Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005), pages 448-453, 2005.
[Lutz 03]
Carsten Lutz. Description Logics with Concrete Domains - A Survey. In Philippe Balbiani, Nobu-Yuki Suzuki, Frank Wolter, and Michael Zakharyaschev, editors, Advances in Modal Logics Volume 4. King's College Publications, 2003.