Although OWL is rather expressive, it has a very serious limitation on datatypes; i.e., it does not support customised datatypes. It has been pointed out that many potential users will not adopt OWL unless this limitation is overcome, and the W3C Semantic Web Best Practices and Deployment Working Group has set up a task force to address this issue. This paper provides a solution for this issue by presenting two decidable datatype extensions of OWL DL, namely OWL-Eu and OWL-E. OWL-Eu provides a minimal extension of OWL DL to support customised datatypes, while OWL-E extends OWL DL with both customised datatypes and customised datatype predicates.
1 Introduction
The OWL Web Ontology Language [
It has been pointed out that many potential users will not adopt OWL unless this
limitation is overcome [
Example 1. Customised datatypes are useful in capturing the intended meaning of some vocabulary in ontologies. For example, users might want to use the customised datatype ‘atLeast18’ in the following definition of the class ‘Adult’: which says that an Adult is a Person whose age is at least 18. The datatype constraint ‘at least 18’ can be defined as an XML Schema user-defined datatype <simpleType name = “atLeast18”> <restriction base = “xsd:integer”>
<minInclusive value = “18”/> </restriction> </simpleType> in which the facet ‘minInclusive’ is used to restrict the value space of atLeast18 (a customised datatype) to be a subset of the value space of integer (an XML Schema built-in datatype).
User-defined datatypes (like the above one) cannot, however, be used in the OWL datatyping, which (only) provides the use of some built-in XML Schema datatypes and enumerated datatypes, which are defined by explicitly specifying their instances. The OWL datatyping does not support XML Schema customised datatypes for the following two reasons: (i) XML Schema does not provide a standard way to access a user-defined datatype. (ii) OWL DL does not provide a mechanism to guarantee the computability of the kinds of customised datatypes it supports.
This paper provides a solution for this issue by presenting two decidable datatype extensions of OWL DL, namely OWL-Eu and OWL-E. OWL-Eu provides a minimal extension of OWL DL to support customised datatypes, while OWL-E extends OWL DL with both customised datatypes and customised datatype predicates. The rest of the paper is organised as follows: Section 2 further discusses the motivations of introducing customised datatypes and datatype predicates. Section 3 extends the OWL datatyping to unary datatype groups, which enables the use of customised datatypes. Section 4 and 5 present the OWL-Eu and the OWL-E languages, respectively; the latter one is based on datatype groups, which are general forms of unary datatype groups. Section 6 concludes the paper and suggests some future work. 2
Motivations Allowing users to define their own vocabulary is one of the most useful features that ontologies can provide over other approaches, such as the Dublin Core, of providing semantics in the Semantic Web. In the Dublin Core standard, the meaning of the set of 15 information properties are described in English text. The main drawback of the Dublin Core is its inflexibility; it is impossible to ‘predefine’ information properties for all sorts of applications.
Ontologies, however, are more flexible in that users can define their own vocabulary based on existing vocabularies. In ontology languages, a set of class constructors are usually provided so that users can build class expressions based on, for example, existing class names. The intended meaning of the vocabulary, therefore, can be captured by the axioms in the ontologies. Let us revisit Example 1 and consider the intended meaning of the Adult class. According to its definition, an Adult is a Person who is at least 18 years old. As a result, programs can also understand the meaning of customised vocabulary, with the help of ontologies.
Although OWL DL provides a set of expressive class constructors to build customised classes, it does not provide enough expressive power to support, for example, XML Schema customised datatypes. In order to capture the intended meaning of Adult, Example 1 has already shown the necessity of customised datatypes. In what follows, we give some more examples to illustrate the usefulness of customised datatypes and datatype predicates in various SW and ontology applications.
Example 2. Semantic Web Service: Matchmaking
Matchmaking is a process that takes a service requirement and a group of service advertisements as input, and returns all the advertisements that may potentially satisfy the requirement. In a computer sales ontology, a service requirement may ask for a PC with memory size greater than 512Mb, unit price less than 700 pounds and delivery date earlier than 15/03/2004.
Here ‘greater than 512’, ‘less than 700’ and ‘earlier than 15/03/2004’ are customised datatypes of base datatypes integer, integer and date, respectively.
Example 3. Electronic Commerce: A ‘No Shipping Fee’ Rule
Electronic shops may need to classify items according to their sizes, and to reason that an item for which the sum of height, length and width is no greater than 15cm belongs to a class in their ontology, called ‘small-items’. Then they can have a rule saying that for ‘small-items’ no shipping costs are charged. Accordingly, the billing system will charge no shipping fees for all the instances of the ‘small-items’ class.
Here ‘greater than 15’ is a customised datatype, ‘sum’ is a datatype predicate, while ‘sum no greater than 15’ is a customised datatype predicate. 3
Unary Datatype Groups
The OWL datatyping is defined based on the notion of datatype maps [
Definition 1 A unary datatype group G is a triple (Md,B,dom), where Md is the datatype map of G, B is the set of primitive base datatype URI references in G and dom is the declared domain function. We call S the set of supported datatype URI references of G, i.e., for each u ∈ S, Md(u) is defined; we require B ⊆ S. We assume that there exist unary datatype URI reference rdfs:Literal, owlx:DatatypeBottom 6∈ S. The declared domain function dom has the following properties: for each u ∈ S, if u ∈ B, dom(u) = u; otherwise, dom(u) = v, where v ∈ B.
Definition 1 ensures that all the primitive base datatype URIrefs of G are supported (B ⊆ S) and that each supported datatype URIref relates to a primitive base datatype URIref through the declared domain function dom.
Example 4. G1 = (Md1, B1, dom1) is a unary datatype group, where – Md1 = {xsd:integer 7→ integer, xsd:string 7→ string, xsd:nonNegativeInteger 7→≥0, xsdx:integerLessThanN 7→<N}, – B1 = {xsd:string, xsd:integer}, and – dom1 = {xsd:integer 7→ xsd:integer, xsd:string 7→ xsd:string, xsd:nonNegativeInteger 7→ xsd:integer, xsdx:integerLessThanN 7→ xsd:integer}.
According to Md1, we have S1 = {xsd:integer, xsd:string, xsd:nonNegativeInteger, xsdx:integerLessThanN}, hence B1 ⊆ S1. ♦
Based on a unary datatype group, we can provide a formalism (called datatype expressions) for constructing customised datatypes using supported datatypes. Definition 2 Let G be a unary datatype group. The set of G-unary datatype expressions in abstract syntax (corresponding DL syntax can be found in Table 5 on page 8), abbreviated Dexp(G), is inductively defined as follows:
2. relativised negated expressions not(u) ∈ Dexp(G), for a datatype URIref u; 3. enumerated expressions oneOf(l1, . . . , ln) ∈ Dexp(G), for literals l1, . . . , ln; 4. conjunctive expressions and(E1, ..., En) ∈ Dexp(G), for unary datatype expressions
E1, ..., En ∈ Dexp(G); 5. disjunctive expressions or(E1, ..., En) ∈ Dexp(G), for unary datatype expressions
E1, ..., En ∈ Dexp(G).
Example 5. G-unary datatype expressions can be used to represent XML Schema nonlist simple types. Given the unary datatype group G1 presented in Example 4 (page 3), – the following XML Schema derived union simple type <simpleType name = “cameraPrice”> <union> <simpleType> <restriction base = “xsd:nonNegativeInteger”>
<maxExclusive value = “100000”/> </restriction> </simpleType> <simpleType> <restriction base = “xsd:string”> <enumeration value = “low”/> <enumeration value = “medium”/> <enumeration value = “expensive”/> </restriction> </simpleType> </union> <simpleType> can be represented by the following disjunctive expression or( ).
and(xsd:nonNegativeInteger, xsdx:integerLessThan100000) oneOf(“low”ˆˆxsd:string,“medium”ˆˆxsd:string, “expensive”ˆˆxsd:string) Note that “low”ˆˆxsd:string is a typed literal, which represents a value of the xsd:string datatype. “low”, instead, is a plain literal, where no datatype information is provided. ♦
Abstract Syntax DL Syntax a datatype URIref u u oneOf(l1, . . . , ln) {l1, . . . , ln} not(u) u Definition 3 A datatype interpretation ID of a unary datatype group G = (Md, B, dom) is a pair (ΔD, ·D), where ΔD (the datatype domain) is a non-empty set and ·D is a datatype interpretation function, which has to satisfy the following conditions: 1. (rdfs:Literal)D = ΔD and (owlx:DatatypeBottom)D = ∅; 2. for each plain literal l, lD = l ∈ PL and PL ⊆ ΔD (PL is the value space for plain literals); 3. for any two primitive base datatype URIrefs u1, u2 ∈ B: u1D ∩ u2D = ∅; 4. for each supported datatype URIref u ∈ S, where d = Md(u): (a) uD = V (d) ⊆ ΔD, L(u) ⊆ L(dom(u)) and L2V (u) ⊆ L2V (dom(u)); (b) if s ∈ L(d), then (“s”ˆˆu)D = L2V (d)(s); otherwise, (“s”ˆˆu)D is not defined; 5. ∀u 6∈ S, uD ⊆ ΔD, and “v”ˆˆu ∈ uD.
Moreover, we extend ·D to G unary datatype expression as shown in Table 5 (page 8). Let E be a G unary datatype expression, the negation of E is of the form ¬E, which is interpreted as ΔD \ ED.
Next, we introduce the kind of basic reasoning mechanisms required for a unary datatype group.
Definition 4 Let V be a set of variables, G = (Md, B, dom) a unary datatype group and u ∈ B a primitive base datatype URIref. A datatype conjunction of u is of the form k l C = ^ uj(vj) ∧ ^ 6=i (v1(i), v2(i)), j=1 i=1 (1) where the vj are variables from V, v1(i), v(i) are variables in Vk 2 j=1 uj (vj ), uj are datatype URI references from S such that dom(uj ) = u, and 6=i are the inequality predicates for primitive base datatypes Md(dom(ui)) where ui appear in Vk j=1 uj (vj ).
A datatype conjunction C is called satisfiable iff there exists an interpretation (ΔD, ·D) of G and a function δ mapping the variables in C to data values in ΔD s.t. δ(vj ) ∈ ujD (for all 1 ≤ j ≤ k) and {δ(v1(i)), δ(v2(i))} ⊆ uiD and δ(v1(i)) 6= δ(v2(i)) (for all 1 ≤ i ≤ l). Such a function δ is called a solution for C w.r.t. (ΔD, ·D).
We end this section by elaborating the conditions that computable unary datatype groups require.
1. for any u ∈ S \ B: there exists u0 ∈ S \ B such that u0D = uD, and 2. for each primitive base datatype in G, the satisfiability problems for finite datatype conjunctions of the form (1) is decidable. 4
OWL-Eu In this section, we present a small extension of OWL DL, i.e., OWL-Eu. The underpinning DL of OWL-Eu is SHOIN (G1), i.e., the SHOIN DL combined with a unary datatype group G (1 for unary). Specifically, OWL-Eu (only) extends OWL data range (i.e., enumerated datatypes as well as some built-in XML Schema datatypes) to OWLEu data ranges defined as follows.
Definition 6 An OWL-Eu data range is a G unary datatype expression. Abstract (as well as DL) syntax and model-theoretic semantics of OWL-Eu data ranges are presented in Table 5 (page 8).
The consequence of the extension is that customised datatypes, represented by OWL-Eu data ranges, can be used in datatype exists restrictions (∃T.u) and datatype value restrictions (∀T.u), where T is a datatype property and u is an OWL-Eu data range. Hence, this extension of OWL DL is as large as is necessary to support customised datatypes.
Example 6. PCs with memory size greater than or equal to 512 Mb and with price cheaper than 700 pounds can be represented in the following OWL-Eu concept description in DL syntax (cf. Table 5 on page 8):
PC u ∃memorySizeInM b.<512 u ∃priceInP ound. <700, where <512 is a relativised negated expression and <700 is a supported datatype in G1. ♦
It turns out that OWL-Eu (i.e., the SHOIN (G1) DL) is decidable.
Theorem 1. The SHOIN (G1)-concept satisfiability problem w.r.t. a knowledge base is decidable if the combined unary datatype group is conforming.
Proof: (Sketch) We will show the decidability of SHOIN (G1)-concept satisfiability w.r.t. TBoxes and RBoxes by reducing it to the SHOIN -concept satisfiability w.r.t. TBoxes and RBoxes. The basic idea behind the reduction is that we can replace each datatype group-based concept C in T with a new atomic primitive concept AC in T 0. We then compute the satisfiability problem for all possible conjunctions of datatype group-based concepts (and their negations) in T (of which there are only a finite number), and in case a conjunction C1 u . . . u Cn is unsatisfiable, we add an axiom AC1 u . . . u ACn v ⊥ to T 0. For example, unary datatype group-based concepts ∃T. >1 and ∀T. ≤0 occurring in T would be replaced with A∃T.>1 and A∀T.≤0 in T 0, and A∃T.>1 u A∀T.≤0 v ⊥ would be added to T 0 because ∃T. >1 u ∀T. ≤0 is unsatisfiable (i.e., there is no solution for the predicate conjunction >1 (v) ∧ ≤0 (v)).
OWL-E: A Step Further In this section, we present a further extension of OWL-Eu, called OWL-E, which supports not only customised datatypes, but also customised datatype predicates.
A datatype predicate (or simply predicate) p is characterised by an arity a(p), or a minimum arity amin(p) if p can have multiple arities, and a predicate extension (or simply extension) E(p). The notion of predicate maps can be defined in an obvious way. For example, =int is a (binary) predicate with arity a(=int) = 2 and extension E(=int) = {hi1, i2i ∈ V (integer)2 | i1 = i2}, where V (integer) is the value space for the datatype integer.
Now we can generalise unary datatype groups by the definition of datatype groups. In fact, datatypes and datatype predicates can be unified in datatype groups. Roughly speaking, a datatype group is a group of built-in predicate URIrefs ‘wrapped’ around a set of primitive datatype URIrefs. A datatype group G is a tuple (Mp,B,dom), where Mp is the predicate map of G, B is the set of primitive datatype URI references in G and dom is the declared domain function. We call S the set of built-in predicate URI references of G, i.e., for each u ∈ S, Mp(u) is defined; we require B ⊆ S. The declared domain function dom has the following properties: for each u ∈ S, u if u ∈ B, (v1, . . . , vn), where v1, . . . , vn ∈ B if u ∈ S \ B and a(Mp(u)) = n, dom(u) = {(v, . . . , v) | i ≥ n}, where v ∈ B if u ∈ S \ B and |i ti{mzes} amin(Mp(u)) = n.
Example 7. G2 = (Mp2, B2, dom2) is a datatype group, where – Mp2 = {xsd:integer 7→ integer, xsd:string 7→ string, xsd:integerGreaterThanOr
EqualToN 7→ ≥N, xsdx:integerLessThanN 7→ <N, xsdx:integerEquality 7→ =int}, – B2 = {xsd:string, xsd:integer}, and – dom2 = {xsd:integer 7→ xsd:integer, xsd:string 7→ xsd:string, xsd:integerGreaterThanOrEqualToN 7→ xsd:integer, xsdx:integerLessThanN 7→ xsd:integer, xsdx:integerEquality 7→ (xsd:integer, xsd:integer)}.
According to Mp2, we have S2 = {xsd:integer, xsd:string, xsd:nonNegativeInteger, xsdx:integerLessThanN, xsdx:integerEquality}, hence B2 ⊆ S2. ♦
Furthermore, based on datatype groups, we can extend unary datatype expressions to general (n-ary) datatype expressions. While enumerated expressions remain the same, relativised negated, conjunctive and disjunctive unary datatype expressions can be easily extended to the n-nary case. There is a new kind of datatype expression called domain expression: domain(u1, . . . , un), where ui is either rdfs:Literal or supported unary datatype predicate URIrefs, or their relativised negations. For example, the customised predicate ‘sumNoGreaterThanOrEqualTo15’, with extension E(sumN oGreaterT hanOrEqualT o15) = {hi0, i1, i2, i3i ∈ V (integer)4 | i0 = Abstract Syntax DL Syntax Semantics not(u) u ΔD \ uD if u ∈ B (dom(u))D \ uD if u ∈ S \ B
Sn≥1(ΔD)n \ uD otherwise domain(u1, . . . , un) [u1, . . . , un] u1D × . . . × unD
Table 2. Syntax and semantics of (new) datatype expressions i1 + i2 + i3 and ¬(i0 ≥ 15)} and arity a(sumN oGreaterT hanOrEqualT o15) = 4, can be represented by
xsdx:integerAddition ∧ [ xsdx:integerGreaterThanOrEqualTo15, xsd:integer, xsd:integer, xsd:integer ], which is a conjunctive expression, where the first conjunct is a predicate URIref (that represents +int) and the second conjunct is a domain expression.
We can extend the datatype interpretation ID presented in Definition 3 to give semantics to datatype groups. For each u ∈ S, uD = E(Mp(u)) ⊆ (dom(u))D, where (dom(u))D is defined as follows: if dom(u) = (d1, . . . , dn) and a(Mp(u)) = n, then (dom(u))D = dD 1 × . . . × dnD; if dom(u) = {(d, . . . , d) | i ≥ n} and amin(Mp(u)) = | {z } i times n, then (dom(u))D = Si≥n (dD)i. The abstract syntax, DL syntax and semantics of relativised negated and domain expressions are presented in Table 5.
The following definition summarises the conditions that computable datatype groups require.
Definition 7 (Conforming Datatype Group) A datatype group G is conforming iff w ∈ B, and 2. for any u ∈ S \ B: there exist u0 ∈ S \ B such that u0D = uD, and 3. the satisfiability problem for finite negation-free predicate conjunctions is decidable, and 4. for each primitive datatype URIref ui ∈ B, there exists wi ∈ S, s.t. Mp(wi) =6=ui where 6=ui is the binary inequality predicate for Mp(ui).
Finally, OWL-E extends OWL-Eu with the datatype group-related class constructors presented in Table 3.
Assume that electronic-shops want to define small items as items of which the sum of height, length and width is no greater than or equal to 15cm. The SmallItem class can be represented by the following datatype group-based concept description: ∃Ts, Th, Tl, Tw.(+int ∧ [≥15, integer, integer, integer]), where Ts, Th, Tl, Tw are concrete roles representing “sum in cm”, “hight in cm”, “length in cm” and “width in cm”, respectively, and (+int ∧ [≥15, integer, integer, integer]) is a conjunctive datatype expression representing the customised predicate “sum no larger than or equal to 15”.1 ♦
Like OWL-Eu, OWL-E (i.e., the SHOIQ(G) DL) is also a decidable extension of OWL-DL.
Theorem 2. The SHOIN (G)- and SHOIQ(G)-concept satisfiability and subsumption problems w.r.t. TBoxes and RBoxes are decidable.
According to Tobies [13, Lemma 5.3], if L is a DL that provides the nominal constructor, knowledge base satisfiability can be polynomially reduced to satisfiability of TBoxes and RBoxes. Hence, we obtain the following theorem.
Theorem 3. The knowledge base satisfiability problems of SHOIN (G) and SHOIQ(G) are decidable. 6
Conclusion In this paper, we propose OWL-Eu and OWL-E, two decidable extensions of OWL DL that support customised datatypes and customised datatype predicates. OWL-Eu provides a general framework for integrating OWL DL with customised datatypes, such as XML Schema non-list simple types. OWL-E further extends OWL-Eu to support customised datatype predicates.
We have implemented a prototype extension of the FaCT [