Graph summaries for optimizing graph pattern queries on RDF databases
Angela Maduko · 2009
Abstract. The adoption of the Resource Description Framework (RDF) as a metadata and semantic data representation standard is spurring the development of high-level mechanisms for storing and querying RDF data. A common approach for managing and querying RDF data is to build on Relational/Object Relational Database systems and translate queries in an RDF query language into queries in the native language of the underlying system, typically SQL. The standard query paradigm for RDF is graph pattern matching which matches a query graph against a data graph. When translated into SQL, such queries involve join operations. To process join operations, the database query optimizer attempts to determine an optimal join order using a cost model which employs the expected cardinality of join results as a key parameter. This parameter is estimated from a statistical summary of the data that is maintained in memory. One limitation that arises with this approach is that it could lead to the selection of a sub-optimal query plan due to estimation errors, from the fact that the data summarization technique employed by database systems are oblivious of the graph structure of RDF data. In this work, we present data summarization techniques that take cognizance of the graph structure of RDF data for providing estimates of RDF graph patterns. Our approach is to take an RDF query and formalize it as a query graph pattern which itself may be made up of smaller graph patterns. These patterns may be viewed as a graph template which can match actual subgraphs in the RDF data. Our