Regular n-ary Queries in Trees and Variable Independence

Emmanuel Filiot 1, 2, * Sophie Tison 1, 2, *
* Auteur correspondant
2 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Regular n-ary queries in trees are queries which are definable by an MSO formula with n free first-order variables. We investigate the variable independence problem -- originally introduced for databases -- in the context of trees. In particular, we show how to decide whether a regular query is equivalent to a union of cartesian products, independently of the input tree. As an intermediate step, we reduce this problem to the problem of deciding whether the number of answers to a regular query is bounded by some constant, independently of the input tree. As a (non-trivial) generalization, we introduce variable independence w.r.t. a dependence forest between blocks of variables, which we prove to be decidable.
Type de document :
Communication dans un congrès
5th IFIP International Conference on Theoretical Computer Science, Sep 2008, Milano, Italy. pp.429-443, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00274648
Contributeur : Emmanuel Filiot <>
Soumis le : lundi 21 avril 2008 - 10:13:58
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 21 septembre 2010 - 16:46:52

Fichier

variable-independence.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00274648, version 2

Collections

Citation

Emmanuel Filiot, Sophie Tison. Regular n-ary Queries in Trees and Variable Independence. 5th IFIP International Conference on Theoretical Computer Science, Sep 2008, Milano, Italy. pp.429-443, 2008. 〈inria-00274648v2〉

Partager

Métriques

Consultations de la notice

178

Téléchargements de fichiers

142