BGP Query Answering against Dynamic RDF Databases

A promising method for efficiently querying RDF data consists of translating SPARQL queries into efficient RDBMS-style operations. However, answering SPARQL queries requires handling RDF reasoning, which must be implemented outside the relational engines that do not support it. We introduce the expressive database (DB) fragment of RDF for which we devise novel sound and complete techniques for answering Basic Graph Pattern (BGP) queries. Our techniques explore the two established approaches for handling RDF semantics, namely reformulation and saturation; we show how they cope with updates, a complex problem due to the rich RDF semantics. Our algorithms can be deployed on top of any RDBMS(-style) engine, and we experimentally study their performance trade-offs.Une méthode prometteuse pour l'interrogation efficace de don- nées RDF consiste à traduire les requêtes SPARQL en opérations typiques des SGBDR. Toutefois, répondre aux requêtes SPARQL nécessite de tenir compte de la sémantique de RDF, ce qui implique d'utilisation de mécanismes de raison- nement en dehors des moteurs relationnels. Nous introduisons le fragment base de données (DB) de RDF, pour lequel nous étudions de nouvelles techniques exactes pour répondre aux requêtes de type Basic Graph Pattern (BGP). Nos techniques couvrent les deux approches de raisonnement bien établies pour la prise en compte de la sémantique de RDF, c'est-à-dire la reformulation de requêtes et la saturation des données ; nous montrons comment elles s'adaptent aux mises à jour, un problème complexe du fait de la sémantique de RDF. Nos algorithmes peuvent être mis en œuvre au- dessus de tout moteur de type SGBDR, et nous comparons expérimentalement leurs performances