Recursive queries on trees and data trees

Serge Abiteboul 1, 2 Pierre Bourhis 3 Anca Muscholl 4 Zhilin Wu 5
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : The analysis of datalog programs over relational structures has been studied in depth, most notably the problem of con- tainment. The analysis problems that have been considered were shown to be undecidable with the exception of (i) con- tainment of arbitrary programs in nonrecursive ones, (ii) containment of monadic programs, and (iii) emptiness. In this paper, we are concerned with a much less studied prob- lem, the analysis of datalog programs over data trees. We show that the analysis of datalog programs is more complex for data trees than for arbitrary structures. In particular, we prove that the three aforementioned problems are unde- cidable for data trees. But in practice, data trees (e.g., XML trees) are often of bounded depth. We prove that all three problems are decidable over bounded depth data trees. Another contribution of the paper is the study of a new form of automata called pattern automata, that are essen- tially equivalent to linear datalog programs. We use pat- tern automata to show that the emptiness problem for lin- ear monadic datalog programs with data value inequalities is decidable over arbitrary data trees.
Type de document :
Communication dans un congrès
Proceedings of the 16th International Conference on Database Theory, Mar 2013, Genoa, Italy. 2013
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00809297
Contributeur : Émilien Antoine <>
Soumis le : lundi 8 avril 2013 - 19:22:24
Dernière modification le : jeudi 9 février 2017 - 15:47:49
Document(s) archivé(s) le : lundi 3 avril 2017 - 02:28:18

Fichier

p93-abiteboul.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00809297, version 1

Collections

Citation

Serge Abiteboul, Pierre Bourhis, Anca Muscholl, Zhilin Wu. Recursive queries on trees and data trees. Proceedings of the 16th International Conference on Database Theory, Mar 2013, Genoa, Italy. 2013. 〈hal-00809297〉

Partager

Métriques

Consultations de
la notice

451

Téléchargements du document

158