Circuits de provenance pour les arbres et ...
Document type :
Communication dans un congrès avec actes
Title :
Circuits de provenance pour les arbres et les instances quasi-arborescentes
Author(s) :
Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Bourhis, Pierre [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Senellart, Pierre [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Image & Pervasive Access Lab [IPAL]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Bourhis, Pierre [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Senellart, Pierre [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Image & Pervasive Access Lab [IPAL]
Conference title :
BDA
City :
Porquerolles
Country :
France
Start date of the conference :
2015-09
Book title :
BDA
Publication date :
2015-09
HAL domain(s) :
Informatique [cs]/Base de données [cs.DB]
French abstract :
<p>L’évaluation de requêtes en logique monadique du second ordre (MSO) est de faible complexité sur les arbres et les instances quasi-arborescentes (c’est-à-dire de largeur d’arbre bornée), alors qu’elle est difficile sur ...
Show more ><p>L’évaluation de requêtes en logique monadique du second ordre (MSO) est de faible complexité sur les arbres et les instances quasi-arborescentes (c’est-à-dire de largeur d’arbre bornée), alors qu’elle est difficile sur les instances arbitraires. Ce résultat a été étendu à certaines tâches liées à l’évaluation de requêtes, comme compter les résultats d’une requête ou évaluer des requêtes sur des arbres probabilistes. Nous voyons le comptage et l’évaluation probabiliste comme deux cas particuliers du problème plus général consistant à calculer des résultats de requête enrichis avec des informations de provenance.Cet article présente une construction de provenance pour les arbres et les instances quasi-arborescentes, en expliquant comment calculer en temps linéaire une représentation de la provenance sous forme de circuit pour les requêtes MSO. Nous montrons comment cette provenance se rattache aux définitions habituelles des semianneaux de provenance sur les instances relationnelles, quand bien même nous la calculons d’une manière inhabituelle, en passant par des automates d’arbres : nous établissons cette connexion au travers de définitions intrinsèques de la provenance pour des semianneaux généraux, qui ne dépendent pas des détails opérationnels de l’évaluation de la requête. Nous montronscomment cette provenance permet de capturer des résultats existants pour le comptage et l’évaluation probabiliste sur les arbres et les instances quasi-arborescentes, et nous en déduisons de nouvelles conséquences pour l’évaluation de requêtes sur diverses représentations <br/>probabilistes.Cet article a été accepté à ICALP 2015. Cette version intègre certains changements mineurs. Par ailleurs, son appendice est inédite et contient du contenu technique et des preuves supplémentaires.</p>Show less >
Show more ><p>L’évaluation de requêtes en logique monadique du second ordre (MSO) est de faible complexité sur les arbres et les instances quasi-arborescentes (c’est-à-dire de largeur d’arbre bornée), alors qu’elle est difficile sur les instances arbitraires. Ce résultat a été étendu à certaines tâches liées à l’évaluation de requêtes, comme compter les résultats d’une requête ou évaluer des requêtes sur des arbres probabilistes. Nous voyons le comptage et l’évaluation probabiliste comme deux cas particuliers du problème plus général consistant à calculer des résultats de requête enrichis avec des informations de provenance.Cet article présente une construction de provenance pour les arbres et les instances quasi-arborescentes, en expliquant comment calculer en temps linéaire une représentation de la provenance sous forme de circuit pour les requêtes MSO. Nous montrons comment cette provenance se rattache aux définitions habituelles des semianneaux de provenance sur les instances relationnelles, quand bien même nous la calculons d’une manière inhabituelle, en passant par des automates d’arbres : nous établissons cette connexion au travers de définitions intrinsèques de la provenance pour des semianneaux généraux, qui ne dépendent pas des détails opérationnels de l’évaluation de la requête. Nous montronscomment cette provenance permet de capturer des résultats existants pour le comptage et l’évaluation probabiliste sur les arbres et les instances quasi-arborescentes, et nous en déduisons de nouvelles conséquences pour l’évaluation de requêtes sur diverses représentations <br/>probabilistes.Cet article a été accepté à ICALP 2015. Cette version intègre certains changements mineurs. Par ailleurs, son appendice est inédite et contient du contenu technique et des preuves supplémentaires.</p>Show less >
Language :
Français
Peer reviewed article :
Oui
Audience :
Nationale
Popular science :
Non
Collections :
Source :