Enabling Inferencing

R.V. Guha (Netscape) <guha@netscape.com>
Ora Lassila (Nokia) <ora.lassila@research.nokia.com>
Eric Miller (OCLC) <emiller@oclc.org>
Dan Brickley (ILRT, University of Bristol) <daniel.brickley@bristol.ac.uk>

Date: 18 Nov 1998

Status of this document:
This is a position paper for the W3C Query Languages meeting in Boston, December 3-4th 1998.


The world wide web today is a network of hyperlinked resources. The content of these resources is in most part opaque to computers. Browsers display them and search engines locate occurances of words within them, but the level of "machine understanding" of the content, if any, is very limited. A search engine, for example, might know that a resource contained the textual string "lion" but not that it was a representation of a lion, where lions are known to be members of the class of mammals. By enabling richer representation such as this, RDF makes it possible to express queries that go beyond simple text-matching.

This paper presents an overview of the query services that might be built on top of XML/RDF data. It does not present a specific proposal for an RDF query language; instead, it argues for a query language that is expressed in terms of the RDF logical data model rather than one particular concrete syntax

Evolving the Web from a Document Repository to a Knowledge Base

With the advent of RDF and XML, we how have an opportunity to encode or annotate the content in a more machine understandable way. This will help the web evolve from a set of opaque pages to a rich knowledge base. This in turn will enable many new interesting applications, one of the most important of which will be the precise search and retrieval of content.

The content of images is typically very opaque to computers. Searching for images that contain particular kinds of scenes or items is usually done by searching for words which might occur on a page which refers to the image. This method is highly inaccurate. If the image were associated with a piece of RDF that clearly specified its content, significantly more precise retrieval would be possible. E.g., a photo of a lion could be annotated as depicting a lion. The following piece of RDF does this.

 <!-- somewhere on the web.. some RDF statements about a picture -->

 <RDF xmlns:cx="http://www.wwc.org/cat.rdf"

          <P:Photograph rdf:about="http://www.imagelib.com/lion1.jpg">
                        <vocab:color resource="http://vocab.org/useful#tan"/>
                        <vocab:gender resource="http://vocab.org/useful#female"/>
                  <P:depicts rdf:resource="http://registries.org/people/Fred"/>

       <!-- a picture of a tan coloured female lion and a 
            person identified only by URI -->

  <!-- somewhere else on the web... -->

 <rdf:RDF  xmlns:vocab="http://vocab.org/useful#"

    <vocab:Person rdf:about="http://registries.org/people/Fred">
       <vocab:gender rdf:resource="http://vocab.org/useful#male"/>
       <vocab:name> Fred </vocab:name>


see footnote for explanation of syntax

With this information, a search engine could do a very precise search for pictures of lions. Searching for the word "lion" on the other hand retrieves 784150 pages in Alta Vista, most of which are references to the Lions Club, Lion King, etc.

While this kind of simple matching based retrieval would be useful, it does not even come close to exploiting the full potential of having machine understandable content (MUC).

In order to fully exploit this, we need to be able to build inferential services on top of this MUC. Such a service would combine the "raw" MUC with a set of axioms/rules, enabling machines to infer knowledge that is implicit in the MUC.

Example: inference-based image retrieval

Imagine an appropriately captioned photograph of a child's birthday party. Now consider someone searching for an image with decorations. Typically, children's birthday parties have decorations. However, since the caption does not explicitly state that the image scene contains decorations, a simple matching based algorithm will not find this image.
An inferential service could draw on a rich set of rules about the world (including events like birthday parties) to infer that the photograph probably includes some decorations, thereby improving the retrieval.

Example: class hierarchies

The RDF Schema specification language provides facilities for machine-readable vocabularies to be specified using a hierarchical type system. This allows a resource to be described as member of some specific class (eg. 'Snow Leopard') and have it's membership of more general classes (eg. 'Big Cat', 'Mammal') implied by the RDF type system. This makes it feasible to express searches for resources using general categories, and have the results include resources whose membership of those broad categories is inferred from their membership of some more detailed sub-category.

Logical vs Physical Models

Inferencing engines typically work by applying a set of "rules" --- statements such as, if (a and b) then infer c) --- to a set of ground atomic facts (this is a gross simplification of inferencing, but will suffice for the purposes of this paper). The application of rules to derive new conclusions can occur either when a query is posed or when new facts or obtained. The set of rules and facts can be centralized or distributed.

Inferencing engines always work on a "logical model". The logical model is an (typically set-theoretic) abstraction.

The logical model is by definition an abstract entity. Logical models are typically grounded in one or more concrete syntaxes (aka physical models).

W3C logical models are based on RDF and syntax models are based on XML.

The distinction between the Logical Model vs the Syntax Model has evolved over decades of work in math and computer science and is found wherever representation of information is involved.

Any particular concrete manipulation is always on a physical model. Therefore, it is often tempting to either confuse the two or try make do with just the physical model. However, there are several reasons why complex applications such as inferencing engines are based on the logical model.

  1. There is a one-to-many mapping from a logical model to the concrete representations of that logical model. A concrete syntax needs to make certain commitments that a logical model need not. The logical model hides details of the physical model that don't carry any semantics. This in turn makes it easier to build applications such as inferencing engines and higher level query languages.


  2. Logical models provide support for certain operations which may be difficult or impossible to properly define at a physical level.

    For example, if the logical model of a knowledge is a directed labelled graph (as with RDF), the aggregation of multiple knowledge bases can be defined cleanly as graph superposition at the logical level, even though it would be hard to define the concept of "aggregation" two XML files.

  3. Most interesting inferencing systems have infinite deductive closures. This means that the deductive closure --- the set of all the statements implied --- can never have a completele concrete representation. In such cases, a query language for determining whether a proposition is in the deductive closure necceserily needs to be in terms of the logical model.

Given the importance of the logical model, it is clear that we need query languages not just for XML but also for RDF.

Query languages for RDF.

This position paper suggests a general outline for an RDF querying system. RDF's simple yet powerful data model allows for an equally simple yet powerful query language. The query language is based on a single query mechanism : subgraph matching.

Every query is against an RDF knowledge base (KB), which in turn could be an aggregation of two or more RDF knowledge bases. Every RDF/XML block (i.e., the RDF within a <RDF> ...</RDF>) can be thought of as a serialised RDF knowledge base.

The query is itself simply an RDF model (i.e., a directed labelled graph), some of whose resources and properties may represent variables. There are two outputs to every query,

  1. A subgraph (of the KB against which the query is issued) which matches the query.
  2. A table of sets of legal bindings for the variables, i.e., when these bindings are applied to the variables in the query, we get (1).

Here are a couple of salient points about the query language outlined above.

RDF Schema constructs such as subClassOf and subPropertyOf allow some simple inferences. In future, more complex rules will be expressible and more powerful inference engines will become possible. Ideally, the query language used by an inferencing system to access the knowledge base should be the same the query language the inferencing system responds to.

To enable this, a query can take an additional parameter which specifies whether its answer should be based on either the "raw RDF graph" or on the deductive closure of the knowledge base.


Note: The syntax of these queries could easily be represented in RDF/XML syntax. For the purposes of this paper we use a simple syntax in which '$x' and '$y' represent variables and properties are shown using namespace prefixes.

Query 1: A lion
The query: rdf:type($y, cx:Lion).

(the example syntax used here means "Find resources 'y' which have a http://www.w3.org/TR/WD-rdf-syntax#type property whose value is the resource http://www.wwc.org/cat.rdf#Lion").


        <rdf:RDF xmlns:P = "http://www.images.org/image-desc-schema.rdf#"
             xmlns:rdf = "http://www.w3.org/TR/WD-rdf-syntax#">

  (($y . [anonymous-resource]))
Query 2 : A photograph depicting a male
The query: P:depicts($x, $y) and rdf:type($x, P:Photograph) and vocab:gender($y, vocab:male)

(meaning: "Find values for 'x' and 'y' where resource 'x' has an http://www.images.org/image-desc-schema.rdf#depicts property whose value is 'y', and where 'x' has an http://www.w3.org/TR/WD-rdf-syntax#type property with value http://www.images.org/image-desc-schema.rdf#Photograph and 'y' has an http://vocab.org/useful#gender property whose value is http://vocab.org/useful#male )


	     xmlns:cx = "http://www.wwc.org/cat.rdf"
             xmlns:P = "http://www.images.org/image-desc-schema.rdf#"
             xmlns:rdf = "http://www.w3.org/TR/WD-rdf-syntax#">

          <P:Photograph rdf:about="http://www.imagelib.com/lion1.jpg">
                        <vocab:color resource="http://vocab.org/useful#tan"/>
                        <vocab:gender resource="http://vocab.org/useful#female"/>
                 <cx:Person rdf:about="http://registries.org/people/Fred" >
                       <vocab:gender rdf:resource="http://vocab.org/#male"/>

        <!-- note that the sub-graph returned here includes information
             from two sources; statements about the photograph and about 
             Fred when taken together tell us that this is a photograph of
             a male -->
(($x . [http://www.imagelib.com/lion1.jpg])($y . [http://registries.org/people/Fred]))

Similarly, the query "P:depicts($x, $y) and rdf:type($y, cx:Lion) and vocab:gender($y, vocab:female)" would retrieve only illustrations of female Lions.


With the advent of simple and powerful data models such as RDF and formal, flexible syntaxes such as XML, we how have an opportunity to encode or annotate web content in a more machine understandable way. These standards provide the ability to layer inferencing services that will facilitate the evolution of the web from a set of opaque pages to a rich knowledge base. As such, the web of today, the vast unstructured mass of information, may in the future be transformed into something more manageable - and thus something far more useful.


The following is a human-readable interpretation of the RDF used in the example...

The first block of RDF uses four vocabularies to state that there is a resource (http://www.imagelib.com/lion1.jpg) which is a member of the class 'Photograph' and which depicts an object that is an member of the class 'Lion' and which in turn has a color property with value 'tan', and a gender property with value 'female'. The photograph also depicts a second object identified only by URI (http://registries.org/people/Fred). A second source of information provides further RDF statements about [http://registries.org/people/Fred]. In this case, we learn a name ("Fred") and that Fred is male.


W3C Data Formats (W3C NOTE 29-October-1997) http://www.w3.org/TR/NOTE-rdfarch

Resource Description Framework (RDF) Schemas; http://www.w3.org/TR/WD-rdf-schema

Resource Description Framework (RDF) Model and Syntax; http://www.w3.org/TR/WD-rdf-syntax/

Extensible Markup Language (XML) 1.0; http://www.w3.org/TR/1998/REC-xml-19980210