SPARQ2L: Towards Support for Subgraph Extraction Queries in RDF Databases

Document Type

Conference Proceeding

Publication Date

2007

Abstract

Many applications in analytical domains often have the need to "connect the dots" i.e., query about the structure of data. In bioinformatics for example, it is typical to want to query about interactions between proteins. The aim of such queries is to "extract" relationships between entities i.e. paths from a data graph. Often, such queries will specify certain constraints that qualifying results must satisfy e.g. paths involving a set of mandatory nodes. Unfortunately, most present day Semantic Web query languages including the current draft of the anticipated recommendation SPARQL, lack the ability to express queries about arbitrary path structures in data. In addition, many systems that support some limited form of path queries rely on main memory graph algorithms limiting their applicability to very large scale graphs.

In this paper, we present an approach for supporting Path Extraction queries. Our proposal comprises (i) a query language SPARQ2L which extends SPARQL with path variables and path variable constraint expressions, and (ii) a novel query evaluation framework based on efficient algebraic techniques for solving path problems which allows for path queries to be efficiently evaluated on disk resident RDF graphs. The effectiveness of our proposal is demonstrated by a performance evaluation of our approach on both real world based and synthetic dataset.

Comments

This paper was presented at the 16th World Wide Web Conference (WWW2007), Banff, Canada, May 8-12, 2007.

DOI

10.1145/1242572.1242680

Link to Full Text

Additional Files

SPARQ2L-Kemafor-www2007-1.pdf (260 kB)
PowerPoint Slides of Presentation


Share

COinS