Enabling Inferencing

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

Abstract

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

Example

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"
              xmlns:P="http://www.images.org/image-desc-schema.rdf"
              xmlns:vocab="http://vocab.org/useful#"
              xmlns:rdf="http://www.w3.org/TR/rdf.rdf">        

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

       <!-- 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#"
              xmlns:rdf="http://www.w3.org/TR/WD-rdf-syntax#">        

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

 </rdf:RDF>

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 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.

• Analogy: In relational databases, we have Relational Algebra which provides the logical model and syntaxes such as tab delimited tables which provide the physical model. The former is important for defining query languages (such as SQL) and the later is important for transfering content across the wire.

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.

   Examples:

   • In Relational Databases the "order" of rows in a table carries no semantics. However, in a tab-delimited file the rows have to appear in some order. By operating at the relational level (as opposed to the file format level), SQL hides an aspect of the data that does not carry any semantics.
   • In predicate logic, "A or B" is semantically equivalent to "B or A", even though the two physical strings are very different. A logical model for predicate logic (such as Tarskian semantics) hides this difference.

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.

• It can be used for a wide range of queries from simple graph traversal to complex datalog like queries. For the sake of efficiency, a concrete query language might add a number of "utility" functions for the simple graph traversal.
• One of the results of a query is itself an RDF knowledge base. This means that it is possible to issue a query against the result of another query. In this sense, this query language is similar to relational query languages. This feature will make it possible to construct recursive queries.

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.

Examples

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

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

and 
  (($y . [anonymous-resource]))

Query 2 : A photograph depicting a male

        <rdf:RDF 
	     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">
                <P:depicts>
                   <cx:Lion>
                        <vocab:color resource="http://vocab.org/useful#tan"/>
                        <vocab:gender resource="http://vocab.org/useful#female"/>
                   </cx:Lion>
                </P:depicts>               
                <P:depicts>
                 <cx:Person rdf:about="http://registries.org/people/Fred" >
                       <vocab:gender rdf:resource="http://vocab.org/#male"/>
                 </cx:Person>
               </P:depicts>
            </P:Photograph>
        </rdf:RDF>

        <!-- 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 -->

Conclusion

Notes

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.

References