Castor: Using Constraint Programming to Solve SPARQL Queries
Vianney le Clément de Saint-Marcq, Yves Deville, Christine Solnon, Pierre-Antoine Champin · 2011
As the amount of available data continues to grow in the semantic web, so does the need for efficient query engines. SPARQL [3] is a query language for RDF graphs standardized by the W3C. It is implemented by many triple stores like Sesame, 4store, Virtuoso, etc. However, they are still orders of magnitude slower than traditional relational databases. A key challenge is that SPARQL queries are known to be NP-hard [2]. The execution model of current SPARQL engines is based on relational algebra. A query is subdivided in many small parts that are computed separately. The answer sets are then joined together. User-specified filters — which allow the users to add constraints to be satisfied by answer sets — are often processed after such join operations. Constraint Programming (CP), on the other hand, is able to actively exploit constraints during the search, thus reducing the search space. Such techniques have been used effectively on various NP-hard problems, e.g., graph matching problems that are closely related to SPARQL pattern matching [1]. We propose a new engine, Castor, which is a lightweight CP solver dedicated to solving SPARQL queries. This work has been presented at the CP community [4]. In