Regular n-ary Queries in Trees and Variable Independence - Archive ouverte HAL Access content directly
Conference Papers Year : 2008

Regular n-ary Queries in Trees and Variable Independence

(1, 2) , (1, 2)
1
2

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.
Fichier principal
Vignette du fichier
variable-independence.pdf (227.33 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00274648 , version 1 (20-04-2008)
inria-00274648 , version 2 (21-04-2008)

Identifiers

  • HAL Id : inria-00274648 , version 2

Cite

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. ⟨inria-00274648v2⟩
78 View
208 Download

Share

Gmail Facebook Twitter LinkedIn More