Three Theses of Representation in the Semantic Web

Ian Horrocks
University of Manchester
Manchester, UK
horrocks@cs.man.ac.uk

Peter F. Patel-Schneider
Bell Labs Research
Murray Hill, NJ, USA
pfps@research.bell-labs.com

Abstract:

The Semantic Web is vitally dependent on a formal meaning for the constructs of its languages. For Semantic Web languages to work well together their formal meanings must employ a common view (or thesis) of representation, otherwise it will not be possible to reconcile documents written in different languages. The thesis of representation underlying RDF and RDFS is particularly troublesome in this regard, as it has several unusual aspects, both semantic and syntactic. A more-standard thesis of representation would result in the ability to reuse existing results and tools in the Semantic Web.

Categories and Subject Descriptors

General Terms

Keywords

1 Introduction

In the short span of its existence, the World Wide Web has resulted in a revolution in the way information is transferred between computer applications. It is no longer necessary for humans to set up channels for inter-application information transfer; this is handled by TCP/IP and related protocols. It is also no longer necessary for humans to define the syntax and build parsers used for each kind of information transfer; this is handled by HTML, XML and related standards. However, it is still not possible for applications to interoperate with other applications without some pre-existing, human-created, and outside-of-the-web agreements as to the meaning of the information being transferred.

The next generation of the Web aims to alleviate this problem--making Web resources more readily accessible to automated processes by adding information that describes Web content in a machine-accessible and manipulable fashion. This coincides with the vision that Tim Berners-Lee calls the Semantic Web in his recent book ``Weaving the Web'' [5].

If such information (often called meta-data) is to make resources more accessible to automated agents, it is essential that its meaning can be understood by such agents. For this to be the case there must be some common way of providing meaning for meta-data in the Semantic Web, or at least a common underpinning for providing such meaning. Otherwise agents will not be able to combine meta-data from different sources in the Semantic Web.

**Figure:** Semantic Web architecture `http://www.w3.org/2000/Talks/1206-xml2k-tbl/`
$\includegraphics[width=\linewidth]{sweb-stack.eps}$

A common underpinning is especially important for the Semantic Web as it is envisioned to contain several languages, as in Tim Berners-Lee's ``layer cake'' diagram (Figure 1) first presented at XML 2000. The diagram depicts a Semantic Web Architecture in which languages of increasing power are layered one on top of the other. Unfortunately, the relationships between adjacent layers are not specified, either with respect to syntax or semantics.

The basis of a particular way of providing meaning for meta-data is embodied in the model theory for RDF [22], the language at the base of the Semantic Web. However, this basis is built on an unusual thesis of representation, one that is different from the representation thesis built into most logical languages. Moreover, the RDF thesis of representation has other unusual aspects that make its use as the foundation of representation in the Semantic Web difficult at best. In particular, RDF has a very limited collection of syntactic constructs, and these are treated in a very uniform manner in the semantics of RDF. The RDF thesis requires that no other syntactic constructs are to be used and that the uniform semantic treatment of syntactic constructs cannot be changed, only augmented.

We argue that it would be better, at least in the beginnings of the Semantic Web, to employ a more-standard thesis of representation. This would permit the use of much existing work on (knowledge) representation and allow the direct employment of existing reasoning tools.

1.1 Ontology Languages

A current focus of activity in the Semantic Web is the construction of an ontology language for the Semantic Web. An ontology typically consists of a hierarchical description of important concepts in a domain, along with descriptions of the properties of (the instances of) each concept. Ontologies will play a pivotal role in the Semantic Web by providing a source of shared and precisely defined terms that can be used in meta-data. The degree of formality employed in capturing these descriptions can be quite variable, ranging from natural language to logical formalisms, but increased formality and regularity clearly facilitates machine understanding.

The recognition of the key role that ontologies are likely to play in the future of the web has led to the extension of web markup languages in order to facilitate content description and the development of web based ontologies, e.g., XML Schema [12], RDF (Resource Description Framework) [26], and RDF Schema (RDFS) [7]. RDFS in particular is recognisable as an ontology/knowledge representation language: it talks about classes and properties (binary relations), range and domain constraints (on properties), and subclass and subproperty (subsumption) relations.

RDFS is, however, a very limited language (at least in some respects), and more expressive power is clearly both necessary and desirable in order to describe resources in sufficient detail. For example, it is useful to be able to state that a property is functional or transitive and it is extremely useful to be able to describe classes in terms of the properties of the individuals that belong to them. Moreover, such descriptions should be amenable to automated reasoning if they are to be used effectively by automated processes, e.g., to determine the semantic relationship between syntactically different terms.

A recognition of the limitations of RDFS led to the development of new web ontology languages such as OIL [13, 14], DAML-ONT [24] and DAML+OIL [35]. DAML+OIL has now been submitted to W3C,¹ and is being used by the W3C Web Ontology Working Group² as the basis of a new W3C web ontology language called the OWL Web Ontology Language [10].

As a second language for the Semantic Web, a decision has to be made as to whether OWL is to use the thesis of representation employed by RDFS or whether OWL should use a different thesis of representation. Some kind of language layering certainly seems to be a reasonable goal for RDFS and OWL, given that they serve similar functions and share many features (e.g., the ability to describe a hierarchy of classes based on the sub-class relationship). In persuance of this objective, OWL (like DAML+OIL) uses the same syntax as RDF (and RDFS) to represent ontologies. What this means in practice is that OWL uses RDFS resources directly where the required functionality already exists in RDFS, e.g., OWL uses rdfs:subClassOf to assert sub-class relationships, and uses OWL-specific classes and properties to extend RDFS functionality, e.g., the owl:complementOf property is used to add complementation of classes to the language. Moreover, all OWL-specific syntactic constructs are written as combinations of RDF syntactic constructs.

Although this solution satisfies the layering objective from a syntactic perspective, the semantic layering of the two languages is more problematical. The difficulty stems from the fact that OWL (like DAML+OIL) is largely based on a Description Logic [2], the semantics of which would normally be given by a ``classical'' first-order model theory in which individuals are interpreted as elements of some domain (a set), classes are interpreted as subsets of the domain and properties are interpreted as binary relations on the domain. The semantics of RDFS, on the other hand, are given by a non-standard model theory, where individuals, classes and properties are all elements in the domain, property elements have extensions which are binary relations on the domain, and class extensions are only implicitly defined by the extension of the rdf:type property. Moreover, RDFS supports reflection on its own syntax: it is defined in terms of classes and properties which are interpreted in the same way as other classes and properties and whose meaning can be extended by statements in the language. As has been discovered in the OWL effort, language layering is much more complex when different layers subscribe to these two different approaches.

A third approach, which lies somewhere between classical first-order and RDFS, is taken by a group of (relatively) new languages including SKIF [23], L $_{\rm base}$ [ 20] and Common Logic [8]. Like RDFS, these languages have a non-standard model theory, with predicates being interpreted as elements of the domain. Unlike RDFS, however, classes are treated as unary predicates whose extensions are subsets of the domain, and reflection on language syntax is not supported. It has been suggested that this approach could solve the layering problem by providing a common semantic basis for all Semantic Web languages [20].

In the remainder of this paper we will study these three approaches in more detail, discuss their advantages and disadvantages, present different visions for language layering based on the various approaches, and illustrate the consequences of each choice, both for OWL and for further layers that may come to be added on top of OWL. In particular, we will demonstrate some of the problems associated with the RDFS limited-syntax and limited-semantics approach to the Semantic Web, illustrate how it complicates the semantics of OWL, and show how some of these problems can be partially overcome.

We will take the first-order subset of SKIF (i.e., no row variables, and no variably polyadic predicates) as our exemplar of the third approach as its syntax and semantics have been clearly defined in [23]. For convenience, we will refer to the three approaches as the FOL approach, the RDFS approach and the SKIF approach respectively.

2 Background

Representation, by which we mean the relationship between constructs in a language and entities in the world, is an inherently difficult notion. Philosophers, and others, have wrestled with this notion for millenia, shedding much heat, and some light, on the subject. Although the entire notion of representation is a fundamental question for the Semantic Web, we will only concern ourselves here with part of the subject, namely the relationship between syntactic constructs in a formal language and objects in some other formal system that is supposed to be an analogue of (part of) the world.

For many languages this representation relationship is handled by means of data models, such as the the XQuery Data Model [15] for XML. Here the meaning of an XML document is a labelled tree, which is supposed to have some closer relationship to some portion of the world than the document itself.

Data models adequately handle this part of the representation relationship for simple languages like XML. However, for languages with more expressive power it is not possible to have a single data model that captures the meaning of a document, or other syntactic construct. Instead the meaning of these languages is often captured by a model-theoretic semantics. In a model-theoretic semantics there is a many-to-many relationship between documents (or whatever) and interpretations. An interpretation is similar to a data model in that it has some closer relationship to the world, but it is different from a data model in that it may have components that do not directly correspond to information in a document. Instead of the very close relationship between document and data model there is instead a much looser relationship between a document and an interpretation, where an interpretation is said to be a model of a document if it is compatable with the document, in some way formally specified by the model theory.

Our three theses of representation differ, in fundamental ways, on what the interpretations of their model-theoretic semantics contain and how these component interact. In addition, the RDFS thesis differs from the other two in how statements can be made.

2.1 DAML+OIL and OWL

Both DAML+OIL and OWL are closely related to very expressive Description Logics (DLs), with a DAML+OIL or OWL ontology corresponding to a DL terminology. DLs are built around individuals, which have membership in classes and are related to other individuals or data values via properties. Data values in DLs play a much more limited role than individuals, but do belong to datatypes. As in a DL, DAML+OIL and OWL classes can be names (URI references in the case of DAML+OIL and OWL) or expressions, and a variety of constructors are provided for building class expressions.

The meaning of such DLs (and the native meaning of DAML+OIL³) is given by a standard model-theoretic semantics [34]. An interpretation consists of a pair $\langle \Delta^{\mathcal{I}},\cdot^{\mathcal{I}} \rangle$ , where $\Delta^{\mathcal{I}}$ is the domain of discourse (a set) and $\cdot^{\mathcal{I}}$ is an interpretation function. When datatypes are supported (as in DAML+OIL and OWL), the domain is divided into two disjoint sets, the ``object domain'' $\Delta^{\mathcal{I}}_\mathcal{O}$ and the ``datatype domain'' $\Delta^{\mathcal{I}}_D$ such that $\Delta^{\mathcal{I}}= \Delta^{\mathcal{I}}_\mathcal{O}\cup \Delta^{\mathcal{I}}_D$ . The interpretation function $\mathcal{I}$ maps individuals into elements of the object domain, classes into subsets of the object domain, datatypes into subsets of the datatype domain and data values into elements of the datatype domain. In addition, two disjoint sets of properties are distinguished: object properties and datatype properties. The interpretation function maps the former into subsets of $\Delta^{\mathcal{I}}_\mathcal{O}\times \Delta^{\mathcal{I}}_\mathcal{O}$ and the latter into subsets of $\Delta^{\mathcal{I}}_\mathcal{O}\times \Delta^{\mathcal{I}}_D$ . The interpretation function is extended to composite syntactic constructs much as is done in FOL, e.g., the extension of a conjunction of classes is given by the set intersection of the interpretations of the classes.

In this framework, individuals and data values correspond to FOL constants, classes and datatypes correspond to unary predicates, properties correspond to binary predicates and sub-class/property relationships correspond to implication. As DLs include a notion of equality, they are only truely embeddable in FOLs with equality.⁴ For example, assertions that John is of type Person, Mary is the mother of John, John is the same individual as Jack, and that Person is a subclass of Animal correspond, respectively, to the FOL sentences $\textsf{Person}(\textsf{John})$ , $\textsf{isMotherOf}(\textsf{Mary},\textsf{John})$ , $\textsf{John} = \textsf{Jack}$ , and $\forall x \;.\; \textsf{Person}(x) \rightarrow \textsf{Animal}(x)$ .

2.2 SKIF

SKIF [23] derives from efforts to formalise the KIF language [16]. Like KIF, SKIF uses a LISP-compatible syntax, but otherwise looks a lot like conventional FOL. In common with Common Logic [8], and L $_{\rm base}$ [ 20], the core of SKIF is standard FOL syntax extended with the ability to use predicates and variables interchangeably. This means that it is possible to use variables in predicate position, e.g., to write sentences like $\exists x \;.\; x(\textsf{John}) \land x(\textsf{Mary})$ (there exists some predicate that is true of both John and Mary), and to use predicates in variable position, e.g., to write sentences like $P(\textsf{John}) \land Q(P)$ (

is true of John and

is true of

), or even

(

is true of

Like many other logics, the semantics of SKIF is based on interpretations. In SKIF, however, an interpretation is a triple $\langle D,\mathit{ext},V \rangle$ , where

is the domain (a set);

is a function that maps predicates, variables and constants to elements of

; and $\mathit{ext}$ is a function that maps

to sets of tuples over

. The interpretation of predicate symbols is different in SKIF than in conventional FOLs. In conventional FOLs (and in DLs) there is a mapping directly from predicate symbols (class and property names in DLs) into a set of tuples. In SKIF, on the other hand, meaning is given to predicates as predicates by first mapping the predicate symbol into an element of the domain of discourse via

. The domain element is then mapped into sets of tuples via $\mathit{ext}$ .

Because of this double mapping SKIF sentences do not have the same meaning as the corresponding FOL (or higher-order logic in the case that a variable occurs in predicate position). Hayes and Menzel [23] give a transformation from SKIF sentences into FOL sentences which, it is claimed, is truth preserving, i.e., the resulting FOL sentence should have an (FOL) interpretation iff the original SKIF sentence had a (SKIF) interpretation. The transformation uses a well known technique for embedding higher-order syntax in FOL. Each SKIF term of the form $P(x_1,\ldots,x_k)$ (and recursively its sub-terms) is replaced with a term $\mathit{Holds}_{k}(P,x_1,\ldots,x_k)$ , where $\mathit{Holds}_{0},\ldots,\mathit{Holds}_{n}$ are newly introduced predicates with arity $1,\ldots, n+1$ respectively.

It is easy to see, however, that the transformation is not truth preserving for FOL with equality: the sentence $\forall x,y \;.\; (x=y) \land P(x) \land \neg Q(x)$ is FOL satisfiable, but the transformed sentence $\forall x,y \;.\; (x=y) \land \mathit{Holds}_{1}(P,x) \land \neg \mathit{Holds}_{1}(Q,x)$ is not satisfiable (because

, giving $\mathit{Holds}_{1}(P,x) \land \neg \mathit{Holds}_{1}(P,x)$ .⁵

2.3 RDF, RDFS, and the RDF Model Theory

The Resource Description Framework (RDF) [26] and its schema extension, the RDF Schema Specification (RDFS) [7], form the lowest semantic layer of the Semantic Web. (The lower layers in the Semantic Web Architecture are only syntactic layers, in that any semantics provided therein is not carried over to the Semantic Web.)

Initially RDF and RDFS had no formal model theory, nor any formal meaning at all. This made them unlikely foundations for the Semantic Web, and even led to disagreements about the meaning of parts of the language, e.g., whether multiple range and domain constraints on a single property should be interpreted conjunctively or disjunctively. Recently, however, a model theory [22] has been proposed for RDF and RDFS as part of the workings of the W3C RDF Core Working group.⁶

The model theory starts with RDF triples [19], an intermediate form (or abstract syntax) for RDF knowledge bases, where many of the syntactic peculiarities of the XML syntax for RDF have been eliminated. An RDF triple consists of a subject, a predicate, and an object. The subject is either a URI reference or a blank node--essentially either a constant or a globally existentially quantified variable. The predicate is also a URI reference--essentially a constant representing a binary predicate, called a property in RDF. The object is either a URI reference, a blank node, or a data value, e.g., an integer. RDF triples are generally written in subject, predicate, object order as in $\textsf{John}~\textsf{loves}~\textsf{Mary}$ .

An interpretation in the RDF model theory is a triple $\langle \mit IR,IEXT,IS \rangle$ ,⁷where $\mit IR$ is the domain (of resources); $\mit IS$ is a function that maps URI references to elements of

; and $\mit IEXT$ is a function from $\mit IR$ to $\mit IR \times IR$ . The interpretation of properties in RDF is similar to the interpretation of predicates in SKIF, as properties are first mapped to domain elements and only then to a set of tuples. However, the RDF model theory has only binary predicates, not predicates of varying arity, as does SKIF.

Because RDF has only triples in its syntax and thus only binary properties in its semantics, it has to encode many of what one might expect to be its logical constants and syntactic constructs. This shows up most vividly in RDFS.

RDFS is built around the notion of a collection of interrelated classes. Class membership in RDFS, which might be expected to be represented as unary predication, is encoded in triples whose predicate is the special URI references rdf:type, whose subject is the class member, and whose object is the class itself. Inclusion between classes, which might be expected to be represented as implication, is encoded in triples whose predicate is the special URI reference rdfs:subClassOf, whose subject is the smaller class, and whose object is the larger class. Supplying domains and ranges for RDFS properties is handled by triples whose predicate is rdfs:domain or rdfs:range, respectively.

To make all these encodings work, an extension to the basic RDF model theory is needed. This extension incorporates conditions on interpretations that force the meaning of the special URI references used to encode the above notions to have the appropriate characteristics. For example, $\mit IEXT(IS({\texttt{rdfs:subClassOf}}))$ is required to be transitive in the model theory extension.

This trick of encoding works relatively well for RDF and RDFS, but, as we well see below, causes severe problems for more-expressive languages.

3 The FOL Thesis

The layering of languages is not a new idea. FOL itself could be described as being layered on top of propositional logic: it extends propositional logic with new syntax for quantifiers, it extends propositional logic semantics with interpretations of quantified terms, and it preserves the meaning of propositional logic sentences.

The extension of propositional logic to FOL gives greatly increased expressive power, but at the cost of greatly increased computational cost: determining the satisfiability of a propositional logic sentence is known to be decidable, and to have NP-complete complexity with respect to the size of the input [9], whereas for FOL this problem is known to be undecidable⁸ [ 32]. Many intermediate ``layers'' have been studied, however, with Horn clauses, the two variable fragment [18], the guarded fragment [1], and numerous description, modal and dynamic logics known to be decidable and to have complexities (for the satisfiability problem) ranging from Polynomial to NExpTime-complete [11, 29].

This established hierarchy of languages could be taken as a starting point for a layered architecture of Semantic Web languages. In this framework, classes and properties are always taken to correspond to unary and binary predicates as described in Section 2.1. The main difference between the various layers would be in the available syntax: higher layers would provide more (or less restricted) syntax, and increased expressive power, right up to full FOL. (It would even be possible to go further, e.g., to higher-order logic or other more-powerful logics that are extensions of FOL.) Languages in this framework could be given a semantics via a bespoke (FOL style) model theory, or could simply rely on their correspondence with FOL.

**Figure 2:** The FOL Universe
$\includegraphics[width=\linewidth]{fol.eps}$

The basic thesis of this FOL vision of the Semantic Web is that individual names denote elements of a domain of discourse. Names used in other ways, i.e., as predicates including classes and properties, do not denote elements of the domain of discourse. Instead, such names denote sets of tuples over this domain. Thus, in the FOL thesis, the only elements of the domain of discourse are the individuals. This state of affairs is illustrated in Figure 2.

There would be no need for a total ordering of languages within this framework: e.g., Horn- and DL-based subsets of FOL could exist side-by-side, each less expressive (and more tractable) than full FOL, but neither contained within the other. All languages would, however, subscribe to the FOL model theory and be subsets of full FOL. In the case of two languages where one is contained within the other, sentences in the less expressive language could be transfered directly into the more expressive one; otherwise sentences in two languages could be compared in the least expressive language that included both of them, which, by definition, would always be a subset of FOL.

A big advantage with this framework is that a great deal is already known about FOL and its various sub-languages. For example, DLs define decidable fragments of FOL with complexities ranging from Polynomial (for CLASSIC [6]) to NExpTime-hard (for $\mathcal{SHOIQ}$ [ 33]). Moreover, highly optimised implementations are available for many of these languages (e.g., CLASSIC, FaCT [25] and Racer [21]); these implementations exploit the features of the particular languages and of typical ontology based reasoning problems in order to achieve better performance. Similar claims can be made for ``rule'' languages, i.e., those based on Horn clauses [3].

Highly optimised implementations of full FOL are also available (e.g., Vampire [31], E-SETHEO [28]) and can be exploited in an effective manner due to the direct correspondence of ontologies with FOL sentences.

3.1 RDFS and FOL

One problem with the above architecture is that RDFS already falls outside the proposed framework: as we have seen in Section 2.3, it has a SKIF style model theory that differs from the FOL model theory. RDFS can, however, be transformed into FOL, using the standard trick of employing a $\mathit{Holds}$ predicate. This trick, however, takes the translation of RDFS ontologies outside the decidable fragments mentioned above. From the FOL point of view, this is a serious design defect: although RDFS seems to be a very simple language (much too simple for many Semantic Web applications), its transformation into FOL is not included in any of the above mentioned decidable fragments.

It is interesting, however, to consider the ``FOL subset'' of RDFS. This language would correspond to RDFS with a reinterpretation of the meta-classes and other structural vocabulary of RDFS. Classes such as rdfs:Class and rdf:Property would be removed. Vocabulary such as rdf:type and rdfs:domain would simply be a way of stating the appropriate FOL statements and would no longer denote elements of the domain of discourse. The resulting language would be equivalent to a very simple description logic, and would also be expressible in Horn languages. This language would form an ideal base layer within the FOL framework and would, via progressive extensions of the syntax, allow for a full semantic layering of languages such as DAML+OIL and OWL.

3.2 Beyond FOL

For applications where even the full power of FOL is not enough, it would be natural to extend the framework to higher-order logics (HOL). This would also provide for some of the features seen in RDFS, in particular the use of predicates in variable position, while still maintaining the desirable syntactic and semantic layering characteristics of the framework: FOL sentences are syntactically valid and semantically equivalent HOL sentences. Moreover, although HOLs are computationally highly intractable, they are relatively well understood, and reasoning systems for HOLs do already exist, e.g., HOL [17] and Isabel [30].

4 The SKIF Thesis

In the SKIF thesis, one of the SKIF style languages (e.g., L $_{\rm base}$ ) is taken to be the semantic foundation for all other Semantic Web languages. In the same way as for the FOL architecture, languages within the SKIF framework could be given their own (SKIF style) model theoretic semantics, or could simply rely on their correspondence with SKIF. This thesis is being promoted by Hayes and Guha, who state

**Figure 3:** The SKIF Universe
$\includegraphics[width=\linewidth]{skif.eps}$

The difference between the FOL and SKIF visions of the Semantic Web is thus constituted just of the differences between the fundamental assumptions in their model theories. In both model theories individual names denote elements of the domain of discourse. However, in SKIF the domain of discourse also includes elements that correspond to predicates, and predicate names are first mapped into these domain elements and only then mapped into sets of tuples. This state of affairs is illustrated in Figure 3.

One obvious advantage of using SKIF rather than FOL to provide meaning for the Semantic Web is that SKIF seems to be a better fit with RDFS in that it supports the use of predicates in variable position (e.g., classes as instances of other classes). However, as we will see below, RDFS does not really fit within SKIF.

One problem with using SKIF is that little is known about SKIF and even less is known about sub-languages of SKIF, except for those that completely correspond (not just in syntax, but also in semantics) to sub-languages of FOL. There has been little or no study of DL-based subsets of SKIF, for example.

Another problem with this framework is that there are no native reasoners for SKIF. It is true that using the transformation into FOL allows FOL reasoners to be (mostly correct) reasoners for SKIF, but this transformation may result in very slow reasoning as it interferes with many of the optimisations used in FOL reasoners. There are also no native reasoners for Horn or DL subsets of SKIF, so the only way of dealing with such sub-languages would be to employ a FOL reasoner, and, moreover, to use an optimisation-destroying transformation.

4.1 RDFS and SKIF

RDFS is even more ``liberal'' than SKIF in that it allows for (and even employs in its own specification) reflection on its own syntax. For example, in RDFS the type membership and subclass relationships are not distinguished from other predicates, and can occur as arguments of other predicates. This means that RDFS triples such as $\textsf{John}~\texttt{rdf:type}~\textsf{Person}$ and $\textsf{Person}~\texttt{rdfs:subClassOf}~\textsf{Animal}$ cannot be mapped into SKIF as $\textsf{Person}(\textsf{John})$ and $\forall x . \textsf{Person}(x) \rightarrow \textsf{Animal}(x)$ , but instead must be mapped as $\texttt{rdf:type}(\textsf{Person},\textsf{John})$ and $\texttt{rdfs:subClassOf}(\textsf{Person},\textsf{Animal})$ .

This feature of RDFS may seem relatively harmless at first sight, but in fact has serious repercussions. In particular, the meaning of predicates such as $\texttt{rdfs:subClassOf}$ is not given directly by the mapping into SKIF (as logical implication), but must be explicitly stated, or axiomatised, so that they can themselves be the object of other predicates. E.g., the fact that $\texttt{rdfs:subClassOf}$ is transitive and reflexive must be stated in axioms such as:

$\begin{displaymath} \begin{array}{l@{}l} \forall x,y,z \; . \; & \texttt{rdfs:su... ...l}{\forall x \; . \; \texttt{rdfs:subClassOf}(x,x)} \end{array}\end{displaymath}$

$\begin{displaymath} \begin{array}{l@{}l} \forall x,y \; . \; & (\forall z . \t... ...}(z,y)) \iff \ & \texttt{rdfs:subClassOf}(x,y). \end{array}\end{displaymath}$

When layering a language such as DAML+OIL or OWL on top of RDFS, a similar mapping must be used if the semantics of DAML+OIL or OWL are to correspond with those of RDFS. As DAML+OIL and OWL are more expressive languages than RDFS, a larger and more complex axiomatisation is required in order to capture the meaning of its additional constructs (e.g., cardinality constraints and restrictions). It is notoriously difficult to get such axiomatisations right, and even more difficult to prove that they are right.⁹

While this is not strictly a problem with SKIF, so much as a problem with RDFS, the fact that the SKIF approach does not provide a direct solution to the problem of layering on top of RDFS does reduce its attractiveness.

5 The RDFS Thesis

As indicated above, RDFS does not fit within either the FOL or the SKIF thesis. Instead RDFS has its own thesis of knowledge representation. This thesis can perhaps best be summed up as

**Figure 4:** The RDFS Universe
$\includegraphics[width=\linewidth]{rdf.eps}$

This thesis has dramatic consequences, both semantic and syntactic. The semantic consequences of the RDFS thesis include that all properties (predicates) are elements of the domain of discourse, as in the SKIF thesis, and all semantic relationships are reducible to properties. Part of this state of affairs is illustrated in Figure 4.

Figure 4 does not, however, capture the entirety of the semantic portion of the RDFS thesis. The semantic portion of the RDFS thesis includes the encoding of unary predicates in the binary rdf:type property and the encoding of any trinary or higher arity predicates as several (binary) properties.

Another portion of the RDFS thesis is that all syntax is (reducible to) RDF triples, and, moreover, that all RDF triples denote property relationships between elements of the domain of discourse. This part of the RDFS thesis is, of course, not much of a burden in RDF and RDFS, but it does cause severe problems in more expressive Semantic Web languages.

Even languages as simple as DAML+OIL or OWL have considerable problems with this requirement. To follow the RDFS thesis, the syntactic constructs of such languages have to be encoded in RDF triples and these syntactic RDF triples end up having semantic consequences. An RDFS-compatible model theory for such a language (e.g., the RDFS-compatible model theory for OWL) has to treat these semantic consequences extremely carefully, resulting in a complex model theory. In an attempt to sidestep any negative consequences of the complex model theory there are two views of OWL in the RDFS-compatible model theory for OWL--one where the RDF triples that correspond to OWL syntax are outside of the purview of OWL and one where these RDF triples are in the purview of OWL. The first view of OWL corresponds to a more-standard stance, and has been shown to be equivalent to an expressive but standard description logic. In the second view of OWL, reasoning is undecidable and would have to be implemented by a general first-order reasoner (via an optimisation-destroying transformation).

Languages with greater expressive power than DAML+OIL or OWL would have even worse problems with the RDFS thesis. They would have to represent syntactic constructs such as disjunction as collections of RDF triples, resulting in a model theory that would have to account for the presence of such RDF triples in the semantics. Even worse would be the representation of quantification. Incompatibility with more expressive constructs would seem to be a fundamental, and possibly fatal flaw, in the RDFS thesis.

6 Analysis

Having presented three different theses of (knowledge) representation, the question naturally arises as to which is most suitable as the basis for the Semantic Web.

The FOL thesis has many obvious advantages. Perhaps the most important of these is that it is based on a logical formalism that has been the subject of extensive and intensive study over the course of nearly a century. There exists, as a result, a great wealth of theoretical knowledge and practical experience with respect to FOL.

From a theoretical point of view, it is well known that reasoning is FOL is undecidable. There are, however, many decidable subsets of FOL, and these have also been the subject of extensive investigations. As a result, not only is the theoretical (worst case) complexity known for many of these languages, but a variety of algorithms have been devised with different characteristics with respect to completeness, worst case performance and typical case performance. This knowledge is advantageous when it comes to language layering as it allows different layers to be designed so as to satisfy particular requirements with respect to, e.g., decidability and complexity of reasoning, and the availability of suitable reasoning algorithms. DAML+OIL, for example, was carefully designed so that (subsumption/satisfiability) reasoning was decidable.

From a practical point of view, many reasoning systems have been implemented for FOL and its sub-languages. Modern implementations are often highly optimised so that they perform well with a wide range of problems. This means that applications using FOL based languages can save very significant implementation effort by exploiting existing highly optimised reasoners. DAML+OIL applications, for example, can exploit DL reasoners such as FaCT or Racer, while more expressive languages would be able to exploit FOL reasoners such as Vampire or E-SETHEO.

Moreover, because all the languages within this framework subscribe to the FOL model theory, they can all be directly mapped into FOL, i.e., with individual names being mapped to constants, and other names (e.g., classes and properties) mapped to predicates. This means that the mapping into FOL provides complete semantic interoperability between languages within the framework. For example, a Horn clause based ontology might include a statement of the form

		$\displaystyle \forall x,y,z . \textsf{father}(x,y) \land \textsf{brother}(y,z) \rightarrow \textsf{uncle}(x,z)$
		$\displaystyle \forall x . \textsf{RichUncle}(x) \iff \exists y . \textsf{uncle}(x,y) \land \textsf{Rich}(y),$

The obvious disadvantage of the FOL thesis is that treating classes like individuals (classes as instances) is not possible until the language is extended beyond FOL into HOL, and although HOL reasoners are available, their performance may not be acceptable in ontology applications.

Moreover, FOL is a relatively poor fit with RDFS due to their fundamentally different semantic foundations. Although RDFS can be mapped into FOL via a suitable axiomatisation, this does not lead to semantic interoperability with languages that have been directly mapped. For example, if the RDF triples $\textsf{Mary}\ \textsf{father}\ \textsf{John}$ , $\textsf{John}\ \textsf{brother} \textsf{Peter}$ and $\textsf{Peter}\ \texttt{rdf:type}\ \textsf{Rich}$ , were mapped into FOL using a holds predicate (i.e., to give $\mathit{holds}(\textsf{father},\textsf{Mary},\textsf{John})$ etc.), then we would obviously not be able to conclude $\textsf{RichUncle}(\textsf{Mary})$ .

The most obvious advantage of the SKIF thesis is that the unrestricted mixing of classes and instances is a basic feature of the language, and does not require HOL extensions. This also seems to make SKIF a better fit with RDFS.

Like FOL, SKIF can be used as the basis for semantic interoperability with respect to a family of sub-languages. Little is known, however, about SKIF sub-languages. As we saw in Section 4.1, even RDFS cannot be directly mapped into SKIF, and requires some kind of axiomatisation. Moreover, although languages like DAML+OIL and OWL would seem to be amenable to a direct mapping into SKIF, such a mapping would not lead to semantic interoperability with RDFS for the same reason that direct mappings into FOL of its sub-languages would not lead to semantic interoperability with a holds style mapping of RDFS.

An obvious disadvantage with SKIF is that it is relatively new, and its properties are not nearly so well understood as those of FOL. For example, it was believed up until recently that SKIF sentences that were also syntactically valid as FOL had the same meaning whether interpreted as SKIF or as FOL. As we saw in section 2.2, this is not universally true.¹⁰ The syntactic similarity of SKIF and FOL could even be seen as dangerously deceptive--users may be tempted to write SKIF believing that it has the same meaning as FOL.

From a practical point of view, there are no native reasoners for SKIF, and little or nothing is known about the computational properties of, or reasoning algorithms for, sub-languages of SKIF. Applications using SKIF-based languages would, therefore, either have to implement their own reasoners or use full FOL reasoners via a potentially performance-damaging mapping from SKIF.

The RDFS thesis is that interoperability between layered languages can best be achieved by using RDFS syntax. It is, however, a gross over-simplification to imagine that mappings into a single language automatically provide semantic interoperability. As we have seen above, this is not true when using either FOL or SKIF as the common language. The primitive nature of RDFS means that embedding more more expressive languages in RDFS will require more complex mappings, with a wide range of different and semantically incompatible mapping techniques being possible.

For example, both OIL and OWL have an RDF triple syntax. Completely different approaches were taken, however, to the mapping of the various logical constructs: sets of classes in a disjunction are represented in OIL by using a hasOperand property to link them directly to a single node of type oil:OR, while in OWL such sets are represented using a list syntax with first and rest properties. Mixing the RDF triples obtained via the two mappings would provide, at best, very limited semantic interoperability. Similarly, a mapping of typed predicate calculus into RDF triples using reification has been proposed [27] that is not semantically compatible with either the OIL or OWL mappings.

As discussed in Section 5, the requirement of the RDFS thesis that the syntax of all Semantic Web languages be encoded as RDF triples, and have the semantic consequences that RDFS gives to RDF triples, is basically incompatible with more-expressive languages. One possible benefit of this approach is that RDF tools can be used to parse all Semantic Web languages. It is, however, difficult to see any great benefit in the parsing of an encoding of complex syntactic constructs, let alone a benefit that would outweigh the problems inherent in this approach.

7 Discussion

As we have seen, the formal meaning of Semantic Web (ontology) languages is of crucial importance if automated agents are to exchange, understand and exploit Semantic Web metadata. Moreover, if the Semantic Web is to contain several language layers, as is envisioned, a common semantic underpinning will greatly facilitate interoperability between the different layers. In this paper we have studied three different approaches to providing such a common semantic underpinning: one based on conventional first order logic, one based on SKIF/L $_{\rm base}$ , and one based on RDF/RDFS.

Currently, it seems to be widely assumed that RDF/RDFS will provide such an underpinning: RDF is already a W3C Recommendation, and the RDF/RDFS based web architecture ``layer cake'' is ubiquitous. As we have seen, however, it is far from clear that this represents the best solution, and in fact it leads to serious problems when trying to layer more expressive languages on top of RDFS. Moreover, this approach does not lead directly to any ``computational pathway'', i.e., it is not clear if/how applications would be able to reason with languages layered on top of RDFS.

An alternative approach is to use conventional first order logic as the semantic underpinning. As we have seen, this approach has many advantages: FOL is well established and well understood; it naturally lends itself to the development of a family of languages based on various FOL subsets offering different tradeoffs with respect to expressive power, complexity and computability; and the direct mapping of such languages into (subsets of) FOL also provides immediate semantic interoperability (e.g., between Horn and DL based languages). The FOL approach also provides the most straightforward computational pathway: reasoning in FOL and its sublanguages is well understood, and applications would even be able to exploit existing highly optimised reasoners for FOL and many of its subset languages. This approach is not directly compatible with RDFS, but it is compatible with a simplified version of RDFS (the FOL subset of RDFS). This language would form an ideal base layer within the FOL framework and would allow for a full syntactic and semantic layering of languages such as DAML+OIL (and the DL fragment of OWL).

The third approach, based on SKIF/L $_{\rm base}$ , can be seen as a compromise between the FOL and RDF/RDFS approaches. It is similar to the FOL approach, with SKIF/L $_{\rm base}$ providing the semantic underpinning instead of FOL. SKIF style languages are, however, much less well understood than FOL, and little or nothing is known about SKIF sub-languages. SKIF does provide for the mixing of classes and instances, but this is not enough to allow a direct mapping of RDFS into SKIF. Therefore, in order to provide for semantic interoperability between languages layered on top of RDFS, either the base layer would have to be a SKIF subset of RDFS, or all languages would have to be mapped into SKIF using an RDFS compatible axiomatisation. Moreover, the computational pathway for SKIF is currently restricted to a potentially performance damaging mapping into FOL, a problem that would be further exacerbated if mappings into SKIF were via an axiomatisation (as would be the case for RDFS).

It seems clear that the FOL approach is in many respects the most attractive. It remains to be seen, however, if it is too late to issue a product recall on the Semantic Web bandwagon in order to carry out a safety modification on the RDF/RDFS component.

Acknowledgements

Bibliography

About this document ...

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.50)

The command line arguments were:
latex2html -numbered_footnotes -split 0 p50-horrocks