Dynamic Query Planning for Querying Ontologies

A project within the collaborative research center (SFB TRR 62) "A Companion Technology for Cognitive Technical Systems"

A knowledge base with background knowledge for the application domain is an essential part of an intelligent companion system. If such knowledge is available in a formal knowledge representation language, automated reasoning methods can be used to derive implicitly specified knowledge.

The ontology language OWL is one of the most popular knowledge representation languages. Within the setting an ontology consists of a set of axioms that describe a particular application domain. The basic modelling constructs in OWL are classes, roles and individuals. These elements are interpreted through a well-defined model theorie based on description logics. Classes are, thereby, interpreted as sets of elements, e.g., the class Joint could represent the class of all joints within the (human) body. Individuals are interpreted as concrete elements, e.g., the individual metacarpophalangealJoint could be modelled as an instance of the class Joint. Roles are used to model the relationship between two individuals. Using so-called constructors one can build complex classes and axioms from the basis modelleing constructs. For example, the axiom:
JointDisease EquivalentTo Desease and affects some Joint
models that a joint disease is a disease that affects at least one (some) joint. Every instance of the class JointDisease is, therefore, in a relationship with some instance of the class Joint via the role affects.

The well-defined semantics allows for deriving implicit consequences from the explicitly stated axioms. If, for example, the ontology further contains the axiom Arthritis SubClassOf JointDisease
a so-called reasoner can derive that Arthritis is a Disease and, furthermore, that Arthritis affects at least one Joint.

In order to query the knowledge in the ontology, one can use query languages such as SPARQL. In contrast to the database query language SQL, SPARQL was developed as a query language for knowledge-based systems and was standardised by the World Wide Web Consortium (W3C). SPARQL and SQL allow for retrieving knowledge/data that satisfies given selection criteria. In order to specify such criteria the query languages offer a range of language constructs, e.g., for specifying alternative or optional criteria or filters to filter out certain results.

The implicit consequences of an ontology can also be considered when computing the query answers. For example, Arthritis would be an answer for the SPARQL query

SELECT ?x WHERE { ?x SubClassOf  Disease }

although this is not explicitly stated in the ontology. For the efficient evaluation of complex selection criteria, which consist of several parts, the different parts have to be evaluated in a "good'" order in order to keep the number of intermediate results small. The order is typically determined by a so-called query planner.

In case also implicit answers are to be considered, query planning requires different implementation and optimisation techniques compared to database systems. For this reason, the development and adaptation of query planning algorithms is a hot topic in the area of ontological reasoning and the topic of this project. The goal of the project is to develop dynamic query planning algorithms. Traditionally, query plans are static, which means that the execution order is completely determined before the query execution based on statistical information. Since statistical information are usually not available for the implicit knowledge and generating such statistics is quite expensive as it requires reasoning, it seems reasonable to consider dynamic query planning. In this way, the knowledge obtained while executing some query part can be used to dynamically decide which part should be executed next. The development and evaluation of such query planning algorithms if the goal of this project.

Project period: March 2012 to August 2012

• Birte Glimm (principal investigator)

• Ilianna Kollia (scientific staff)