Composing Monadic Queries in Trees

E. Filiot, J. Niehren, J-M. Talbot and S. Tison

bib

Abstract

Node selection in trees is a fundamental operation to XML databases, programming languages, and information extraction. We propose a new class of querying languages to define n-ary node selection queries as compositions of monadic queries. The choice of the underlying monadic querying language is parametric. We show that compositions of monadic MSO-definable queries capture n-ary MSO-definable queries, and distinguish an MSO-complete n-ary query language that enjoys an efficient query answering algorithm.