Regular n-ary Queries in Trees and Variable Independence

Emmanuel Filiot 1, 2, * Sophie Tison 1, 2, *
* Corresponding author
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.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00274648
Contributor : Emmanuel Filiot <>
Submitted on : Monday, April 21, 2008 - 10:13:58 AM
Last modification on : Thursday, July 25, 2019 - 8:50:03 AM
Long-term archiving on : Tuesday, September 21, 2010 - 4:46:52 PM

File

variable-independence.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00274648v2⟩

Share

Metrics

Record views

232

Files downloads

574