Provenance Circuits for Trees and Treelike ...
Type de document :
Communication dans un congrès avec actes
URL permanente :
Titre :
Provenance Circuits for Trees and Treelike Instances
Auteur(s) :
Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Bourhis, Pierre [Auteur]
Linking Dynamic Data [LINKS ]
Senellart, Pierre [Auteur]
National University of Singapore [NUS]
Data, Intelligence and Graphs [DIG]
Data, Intelligence and Graphs [DIG]
Bourhis, Pierre [Auteur]
Linking Dynamic Data [LINKS ]
Senellart, Pierre [Auteur]
National University of Singapore [NUS]
Data, Intelligence and Graphs [DIG]
Titre de la manifestation scientifique :
ICALP 2015
Ville :
Kyoto
Pays :
Japon
Date de début de la manifestation scientifique :
2015-06
Titre de l’ouvrage :
ICALP 2015
Date de publication :
2015-06
Discipline(s) HAL :
Informatique [cs]/Base de données [cs.DB]
Résumé en anglais : [en]
Query evaluation in monadic second-order logic (MSO) is tractable on trees and treelike instances, even though it is hard for arbitrary instances. This tractability result has been extended to several tasks related to query ...
Lire la suite >Query evaluation in monadic second-order logic (MSO) is tractable on trees and treelike instances, even though it is hard for arbitrary instances. This tractability result has been extended to several tasks related to query evaluation, such as counting query results or performing query evaluation on probabilistic trees. These are two examples of the more general problem of computing augmented query output, that is referred to as provenance. This article presents a provenance framework for trees and treelike instances, by describing a linear-time construction of a circuit provenance representation for MSO queries. We show how this provenance can be connected to the usual definitions of semiring provenance on relational instances, even though we compute it in an unusual way, using tree automata; we do so via intrinsic definitions of provenance for general semirings, independent of the operational details of query evaluation. We show applications of this provenance to capture existing counting and probabilistic results on trees and treelike instances, and give novel consequences for probability evaluation.Lire moins >
Lire la suite >Query evaluation in monadic second-order logic (MSO) is tractable on trees and treelike instances, even though it is hard for arbitrary instances. This tractability result has been extended to several tasks related to query evaluation, such as counting query results or performing query evaluation on probabilistic trees. These are two examples of the more general problem of computing augmented query output, that is referred to as provenance. This article presents a provenance framework for trees and treelike instances, by describing a linear-time construction of a circuit provenance representation for MSO queries. We show how this provenance can be connected to the usual definitions of semiring provenance on relational instances, even though we compute it in an unusual way, using tree automata; we do so via intrinsic definitions of provenance for general semirings, independent of the operational details of query evaluation. We show applications of this provenance to capture existing counting and probabilistic results on trees and treelike instances, and give novel consequences for probability evaluation.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Date de dépôt :
2022-06-13T02:40:32Z