Exécution et génération de requêtes pour PatBin

Exécution et génération de requêtes pour PatBin

Motivation

L’implémentation de PatBin nous a permis d’évaluer les performances de compression de l’algorithme, et de programmer la méthode de matérialisation basée sur l’encodage. Grâce à ces étapes, il nous est possible de compresser des flux et des graphes RDF, et de les modifier afin d’y ajouter de nouveaux triplets. Toutefois, la gestion de l’application des requêtes sur des graphes compressés n’est pas totalement assurée : dans nos sections précédentes, nous avons montré comment manipuler le graphe de la clause WHERE pour réaliser de la matérialisation et vérifier la validité d’une requête sur un graphe. Mais une requête est souvent constituée de nombreux autres éléments (variables, filtres, agrégats…) qu’il faut également prendre en compte ; or une requête SPARQL standard n’est pas aisément directement applicable sur un graphe encodé. Nous avons développé un langage de requête inspiré de PatBin, qui reprend notre encodage, en ajoutant des éléments de requête dans le binding. Nous avons également développé une méthode de génération de requêtes à partir de fichiers et d’informations, qui permet d’obtenir une requête compressée ; cette approche a été choisie en raison de la simplicité de la forme compressée de nos requêtes, et pour faciliter les interactions entre les opérateurs et le raisonnement. En effet, il est souvent complexe pour des non-initiés de manipuler des données sémantisées : notre approche vise à résoudre cette difficulté, en plus de permettre la création de requêtes compressées. 90 Exécution et génération de requêtes pour PatBin Ces deux contributions sont employées par le module RAMSSES, qui sera décrit en fin de chapitre. 

Le requêtage avec PatBin

Comme nous l’avons montré précédemment, PatBin permet de compresser de manière efficace des graphes RDF, et peut être utilisé dans les flux de données. Nous avons également détaillé notre gestion de la matérialisation dans les formes compressées ; il nous reste encore à expliquer comment PatBin peut être utilisé pour le requêtage. Sous forme compressée, les flux de données ne sont constitués que de bindings : un flux, et donc son motif associé, ne change que très rarement ; seuls les objets du graphe vont varier, e.g., les mesures provenant des capteurs. Une requête SPARQL contient toujours une clause WHERE, qui contient un graphe RDF avec des variables : ce graphe peut aussi être converti au format PatBin (comme pour la matérialisation). Le binding sera forcément différent de ceux issus des flux (puisqu’il y aura des variables), mais le pattern peut aussi varier. Il peut y avoir trois cas : — le pattern du flux et celui de la requête sont identiques, — certaines propriétés du flux ne sont pas dans la requête, — certaines propriétés de la requête ne sont pas dans le flux. Le premier cas est trivial. Le second cas est sans doute le plus courant : il s’agit de situations dans lesquelles certaines informations du flux ne sont pas nécessaires dans la requête. Le troisième cas correspond au besoin de matérialisation, que nous avons traité précédemment. Il est possible que les deux derniers cas soient combinés : une requête qui ne reprend pas tout le graphe du flux, mais ajoute des informations provenant d’une base de connaissances statiques en lien avec les informations du flux. Toutefois une requête ne se limite pas à la clause WHERE ; il y a d’autres éléments qui peuvent être ajoutés pour préciser le résultat (FILTER…), exécuter des requêtes sur des ensembles de graphes (agrégats, HAVING…), combiner des graphes (UNION, OPTIONAL…), etc. Tous peuvent être modélisés sous une forme compressée, et traités efficacement pour obtenir le résultat voulu. Le binding de la requête, quant à lui, sera essentiellement vide ; les seuls objets présents seront ceux qui permettent de préciser la requête, et les variables (les nœuds intermédiaires sont laissés vides). Un exemple simple de requête est présenté dans la figure 27 (b). L’exemple 91 (a) Extrait de flux compressé 31:(5:8):40:(44:(49:53):66:(12:74):67:(12:74)) ; »Postal Bank »; »Bank#041″; ; ;450; »US$ »; ; »Dupond »; »CCP XXX »; ; »Durand »; »CCP YYY » (b) Requête compressée basique 31:(8):40:(44:(49:53)) ; »Bank#041″; ; ;?var1; »US$ » (c) Requête compressée avec filtre 31:(8):40:(44:(49:53)) ; »Bank#041″; ; ;?var1>300; »US$ » (d) Requête compressée avec agrégat 31:(8):40:(44:(49:53)) ; »Bank#041″; ; ;?var1?SUM; »US$ » Figure 27 – Exemples de requêtes compressées utilisé ici se base sur un flux de transactions financières ; un extrait du flux est présenté en (a). La requête de base renvoie simplement le montant des transactions en dollars américains effectuées par la banque 041. Certaines parties du graphe du flux sont ignorées car elles ne sont pas pertinentes dans notre cas. La variable est préfixée par un point d’interrogation, afin d’être retrouvée aisément : les littéraux dans un triplet RDF ne sont jamais préfixés ainsi. Les filtres peuvent être ajoutés à la suite des variables, comme montré en figure. 27 (c). Il est possible d’opérer un filtrage sur plusieurs variables, mais les filtres seront tous vérifiés lors de l’exécution de la requête (comme s’ils étaient séparés par une conjonction). On pourrait ajouter des opérateurs booléens à la suite de la représentation pour préciser le traitement à lui appliquer : par exemple, rajouter une barre (|) pour représenter une disjonction et un plus (+) pour une conjonction. Mais l’ordre des variables dans le binding peut varier par rapport à une requête SPARQL, ce qui complique l’opération. En outre, même avec ce genre de représentation, il est impossible d’utiliser des parenthèses pour définir davantage de priorités. Les agrégats peuvent être ajoutés de la même manière, comme précisé dans la partie (c). Toutefois, la requête s’effectue alors sur un ensemble d’éléments du flux avant de renvoyer sa réponse ; ce paramètre doit être défini ailleurs, et ré-utilisé pour la requête. Il est possible également d’ajouter des 92 HAVING aux agrégats, en reprenant le format du filtre, et en l’ajoutant à la suite de l’agrégat (dans notre exemple, on aurait ?var1 ?SUM>500 pour une somme de transactions supérieure à 500). Plusieurs opérateurs du langage SPARQL combinent les résultats de graphes RDF au sein d’une même requête : UNION, INTERSECT, mais aussi OPTIONAL, etc. Dans notre cas, chacun de ces graphes peut être représenté par sa forme compressée, puis les résultats affinés en fonction de l’opérateur utilisé. Il s’agit du seul cas où un élément de la requête n’est pas modélisé au sein de la forme compressée. 

Exécution de requêtes

L’exécution de requêtes est résumée dans l’algorithme 5 ; on considère qu’il s’agit de la toute première exécution, qui comporte son initialisation. Un exemple complet est également présenté, étape par étape, en Fig. 28. C’est à cette étape que la validité de la requête est vérifiée (qu’elle est bien applicable sur le flux), et que l’on effectue la matérialisation (si besoin) ; toutes les modifications effectuées à ce moment sont enregistrées pour être appliquées lors de l’exécution de la requête sur les échantillons suivants. Ainsi, si la requête est valide, son application future prendra moins de temps (les vérifications initiales ne seront plus nécessaires). Pour que l’algorithme fonctionne, il faut naturellement fournir la compression PatBin de la requête, mais également un échantillon PatBin provenant du flux de données. C’est le pattern qui est le plus important ; le binding peut éventuellement être factice, et géré plus tard (on peut séparer la gestion de la première exécution de la requête des exécutions suivantes). Les flux (séries de bindings) sont stockés en mémoire principale afin d’optimiser le traitement des requêtes ; il est possible de faire persister les flux par sérialisation si un traitement ultérieur est nécessaire. Il faut dans un premier temps initialiser une structure de résultat, qui permettra de renvoyer les variables attendues, mais aussi d’enregistrer l’évolution des agrégats, qui doivent se faire sur plusieurs échantillons. Ensuite vient l’étape mentionnée en section 6.2, pour comparer les patterns respectifs de la requête et du flux. En effectuant l’intersection des encodages, on obtient Pi , soit le pattern commun au flux et à la requête (Fig. 28 a). Puis, en soustrayant Pi au pattern de la requête, on obtient Pm : ce qui reste à matérialiser (figure 28 b). En effet, si certains prédicats (par extension, des 93 triplets) sont présents dans la requête, mais pas dans le flux, il y a un besoin de matérialisation. On peut résoudre cette étape en requêtant une base de connaissance statique liée au projet, qui contiendra les informations manquantes (Fig. 28 c), et les ajouter au pattern, et à chaque binding qui arrivera du flux (le pattern donnera la position des objets issus de la base statique dans le binding). Ensuite vient le traitement du cas inverse : si la taille du pattern de flux est supérieure à celle du pattern de requête, c’est qu’il y a certains éléments du flux qui ne sont pas nécessaire à la requête ; on peut donc les retirer, et normaliser les deux patterns pour qu’ils soient identiques (Fig. 28 d). Notons qu’à chaque étape, le retrait (respectivement l’ajout) d’un élément d’un pattern entraîne le retrait d’un élément du binding à la position correspondante (les séparateurs du pattern sont des :, ceux du binding des ;). Lors de la comparaison entre les éléments des patterns, il est possible d’utiliser les bénéfices de l’encodage de LiteMat afin de réécrire la requête. Cette étape se déroule lors du calcul de l’intersection : pour chaque élément encodé du flux étant strictement supérieur à la valeur à la position correspondante dans la requête, il est possible que l’élément en question corresponde à une sous-propriété de l’élément de la requête. Cette vérification peut s’effectuer en se basant sur les spécificités de LiteMat (nombre de bits pour l’encodage) : si une sous-propriété de l’identifiant de la requête correspond à l’identifiant du flux, cet identifiant est adopté en remplacement dans la requête. La réécriture ne s’effectue qu’une fois pour toute, à l’initialisation, et elle n’est valide que pour l’application de la requête sur ce flux spécifique (elle devra potentiellement être réécrite d’une autre manière pour d’autres flux). A cette étape, pour que la requête puisse être exécutée, les patterns de la requête et du flux doivent être identiques ; les étapes précédentes ne sont pas toujours nécessaires, mais elles s’assurent que les encodages correspondent au maximum. Il faut également s’assurer que le binding de la requête est inclus dans celui du flux, c’est-à-dire que les littéraux spécifiés dans la requête sont présents dans le binding du flux, et qu’ils correspondent. Si ces deux conditions ne sont pas remplies, alors soit le graphe du flux est différent de celui de la requête (il n’est donc pas possible de l’appliquer), soit les littéraux spécifiés ne sont pas identiques, et dans ce cas les éléments fournis ne correspondent pas.