Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > publis

PhD thesis

Castor: a Constraint-based SPARQL Engine with Active Filter Processing [PDF]
12/2013
Établissement : Université Claude Bernard Lyon 1
Soutenue le Dec 16, 2013
Jury
PU Lecoutre Christophe, CRIL, Lens, France Rapporteur
Dr. Napoli Amedeo, LORIA, Nancy, France Rapporteur
MdC Champin Pierre-Antoine, LIRIS, Lyon, France Examinateur
PU Mille Alain, LIRIS, Lyon, France Examinateur
Pr. Pecheur Charles, ICTEAM, Louvain-la-Neuve, Belgique Examinateur
Pr. Deville Yves, ICTEAM, Louvain-la-Neuve, Belgique Directeur
PU Solnon Christine, LIRIS, Lyon, France Directeur
Pr. Van Roy Peter, ICTEAM, Louvain-la-Neuve, Belgique Président
Contact : vianney.leclement@uclouvain.be
Mots-clés : Semantic Web Constraint Programming SPARQL

TEL : tel-01127937

Résumé

SPARQL est le langage de requête standard pour les graphes de données du Web Sémantique. L'évaluation de requêtes est étroitement liée aux problèmes d'appariement de graphes. Il a été démontré que l'évaluation est NP-difficile. Les moteurs SPARQL de l'état-de-l'art résolvent les requêtes SPARQL en utilisant des techniques de bases de données traditionnelles. Cette approche est efficace pour les requêtes simples qui fournissent un point de départ précis dans le graphe. Par contre, les requêtes couvrant tout le graphe et impliquant des conditions de filtrage complexes ne passent pas bien à l'échelle. Dans cette thèse, nous proposons de résoudre les requêtes SPARQL en utilisant la Programmation par Contraintes (CP). La CP résout un problème combinatoire en exploitant les contraintes du problème pour élaguer l'arbre de recherche quand elle cherche des solutions. Cette technique s'est montrée efficace pour les problèmes d'appariement de graphes. Nous reformulons la sémantique de SPARQL en termes de problèmes de satisfaction de contraintes (CSPs). Nous appuyant sur cette sémantique dénotationnelle, nous proposons une sémantique opérationnelle qui peut être utilisée pour résoudre des requêtes SPARQL avec des solveurs CP génériques. Les solveurs CP génériques ne sont cependant pas conçus pour traiter les domaines immenses qui proviennent des base de données du Web Sémantique. Afin de mieux traiter ces masses de données, nous introduisons Castor, un nouveau moteur SPARQL incorporant un solveur CP léger et spécialisé. Nous avons apporté une attention particulière à éviter tant que possible les structures de données et algorithmes dont la complexité temporelle ou spatiale est proportionnelle à la taille de la base de données. Des évaluations expérimentales sur des jeux d'essai connus ont montré la faisabilité et l'efficacité de l'approche. Castor est compétitif avec des moteurs SPARQL de l'état-de-l'art sur des requêtes simples, et les surpasse sur des requêtes complexes où les filtres peuvent être exploités activement pendant la recherche.

Abstract

SPARQL is the standard query language for graphs of data in the Semantic Web. Evaluating queries is closely related to graph matching problems, and has been shown to be NP-hard. State-of-the-art SPARQL engines solve queries with traditional relational database technology. Such an approach works well for simple queries that provide a clearly defined starting point in the graph. However, queries encompassing the whole graph and involving complex filtering conditions do not scale well. In this thesis we propose to solve SPARQL queries with Constraint Programming (CP). CP solves a combinatorial problem by exploiting the constraints of the problem to prune the search tree when looking for solutions. Such technique has been shown to work well for graph matching problems. We reformulate the SPARQL semantics by means of constraint satisfaction problems (CSPs). Based on this denotational semantics, we propose an operational semantics that can be used by off-the-shelf CP solvers. Off-the-shelf CP solvers are not designed to handle the huge domains that come with Semantic Web databases though. To handle large databases, we introduce Castor, a new SPARQL engine embedding a specialized lightweight CP solver. Special care has been taken to avoid as much as possible data structures and algorithms whose time or space complexity are proportional to the database size. Experimental evaluations on well-known benchmarks show the feasibility and efficiency of the approach. Castor is competitive with state-of-the-art SPARQL engines on simple queries, and outperforms them on complex queries where filters can be actively exploited during the search.

BibTex

Download

@PhDThesis{Liris-6398,
  title         = {{Castor: a Constraint-based SPARQL Engine with Active 
    Filter Processing}},
  author        = {Vianney {Le clément de saint-Marcq}},
  year          = {2013},
  month         = dec,
  school        = {Université Claude Bernard Lyon 1},
  type          = {Thèse de Doctorat en Informatique},
   language      = {en},
  url           = {http://liris.cnrs.fr/publis/?id=6398}
}