The Linked Data paradigm has become the prominent enabler for sharing huge volumes of data using Semantic Web technologies, and has created novel challenges for non-relational data management systems, such as RDF and graph engines. Efficient data access through queries is perhaps the most important data management task, and is enabled through query optimization techniques, which amount to the discovery of optimal or close to optimal execution plans for a given query.

In this post, we propose a different approach to query optimization, which is meant to complement (rather than replace) the standard optimization methodologies for SPARQL queries. Our approach is based on the use of schema information, encoded using OWL constructs, which often accompany Linked Data.

OWL adopts the Open World Assumption and hence OWL axioms are perceived primarily to infer new knowledge. Nevertheless, ontology designers consider OWL as an expressive schema language used to express constraints for validating the datasets, hence following the Closed World Assumption when interpreting OWL ontologies. Such constraints include disjointness/equivalence of classes/properties, cardinality constraints, domain and range restrictions for properties and others.

This richness of information carried over by OWL axioms can be the basis for the development of schema-aware techniques that will allow significant improvements in the performance of existing RDF query engines when used in tandem with data statistics or even other heuristics based on patterns found in SPARQL queries. As a simple example, a cardinality constraint at the schema level can provide a hint on the proper join ordering, even if data statistics are missing or incomplete.

The aim of this post is to show that the richness of information carried over by OWL axioms under the Close World Assumption can be the basis for the development of schema-aware optimization techniques that will allow considerable improvement for query processing. To attain this objective, we discuss a small set of interesting cases of OWL axioms; a full list can be found here.

Schema-Based Optimization Techniques

Here we provide some examples of queries, which, when combined with specific schema constraints expressed in OWL, can help the optimizer in formulating the (near to) optimal query plans.

A simple first case is the case of constraint violation. Consider the query below, which returns all instances of class <A> which are fillers of a specific property <P>. If the underlying schema contains the information that the range of <P> is class <B>, and that class <B> is disjoint from class <A>, then this query should return the empty result, with no further evaluation (assuming that the constraints associated with the schema are satisfied by the data). An optimizer that takes into account schema information should return an empty result in constant time instead of trying to optimize or evaluate the large star join.

SELECT ?v 
WHERE { ?v rdf : type <A> .   
        ?u <P> ?v . ?u <P> ?v1 .   
        ?u <P1 > ?v2 . ?u <P2 > ?v3 .   
        ?u <P3 > ?v4 . ?u <P4 > ?v5}

Schema-aware optimizers could also prune the search space by eliminating results that are known a priori not to be in the answer set of a query. The query above is an extreme such example (where all potential results are pruned), but other cases are possible, such as the case of the query below, where all subclasses of class <A1> can immediately be identified as not being in the answer set.

SELECT ?c
WHERE { ?x rdf: type ?c . ?x <P> ?y . 
        FILTER NOT EXISTS \{ ?x rdf: type <A1 > }}

Another category of schema-empowered optimizations has to do with improved selectivity estimation. In this respect, knowledge about the cardinality (minimum cardinality, maximum cardinality, exact cardinality, functionality) of a property can be exploited to formulate better query plans, even if data statistics are incomplete, missing or erroneous.

Similarly, taking into account class hierarchies, or the definition of classes/properties via set theoretic constructs (union, intersection) at the schema level, can provide valuable information on the selectivity of certain triple patterns, thus facilitating the process of query optimization. Similar effects can be achieved using information about properties (functionality, transitivity, symmetry etc).

As an example of these patterns, consider the query below, where class <C> is defined as the intersection of classes <C1>, <C2>. Thus, the triple pattern (?x rdf:type <C>) is more selective than (?y rdf:type <C1>) and (?z rdf:type <C2>) and this should be immediately recognizable by the optimizer, without having to resort to cost estimations. This example shows also how unnecessary triple patterns can be pruned from a query to reduce the number of necessary joins. Figure 1 illustrates the query plan obtained when the OWL intersectionOf construct is used.

SELECT ?x 
WHERE { ?x rdf: type <C> . ?x <P1 > ?y . 
        ?y rdf : type <C1 > . ?y <P2 > ?z . ?z rdf : type <C2 > }

Schema information can also be used by the query optimizer to rewrite SPARQL queries to equivalent ones that are found in a form for which already known optimization techniques are easily applicable. For example, the query below could easily be transformed into a classical star-join query if we know (from the schema) that property P4 is a symmetric property.

SELECT ?y ?y1 ?y2 ?y3 
WHERE { ?x <P1 > ?y . ?x <P2 > ?y1 . 
        ?x <P3 > ?y2 . ?y3 <P4 > ?x }

Conclusion

In this post we argued that OWL-empowered optimization techniques can be beneficial for SPARQL query optimization when used in tandem with standard heuristics based on statistics. We provided some examples which showed the power of such optimizations in various cases, namely:

• Cases where the search space can be pruned due to the schema and the associated constraints; an extreme special sub-case is the identification of queries that violate schema constraints and thus produce no results.
• Cases where the schema can help in the estimation of triple pattern selectivity, even if statistics are incomplete or missing.
• Cases where the schema can identify redundant triple patterns that do not affect the result and can be safely eliminated from the query.
• Cases where the schema can be used for rewriting a query in an equivalent form that would facilitate optimization using well-known optimization techniques.

This list is by no means complete, as further cases can be identified by optimizers. Our aim in this post was not to provide a complete listing, but to demonstrate the potential of the idea in various directions.