inria-00274648, version 2
Regular n-ary Queries in Trees and Variable Independence
Emmanuel Filiot
a, 1, 2Sophie Tison a, 1, 2
5th IFIP International Conference on Theoretical Computer Science (2008) 429-443
Résumé : 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.
- a – Université des Sciences et Technologies de Lille - Lille I
- 1 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
- CNRS : UMR8022 – INRIA – IRCICA – Université Lille 1 - Sciences et Technologies
- 2 : MOSTRARE (INRIA Lille - Nord Europe)
- INRIA – CNRS : UMR8022 – Université Lille 1 - Sciences et Technologies : EA3588 – Université Charles de Gaulle - Lille III
- Domaine : Informatique/Recherche d'information
Informatique/Logique en informatique - Mots-clés : MSO – Trees – Variable Independence
- Versions disponibles : v1 (21-04-2008) v2 (21-04-2008)
- inria-00274648, version 2
- http://hal.inria.fr/inria-00274648
- oai:hal.inria.fr:inria-00274648
- Contributeur : Emmanuel Filiot
- Soumis le : Lundi 21 Avril 2008, 10:13:58
- Dernière modification le : Dimanche 2 Novembre 2008, 21:27:31
Documents associés
Exporter