Résumé de séminaire

Résumé :

Node selection in trees is one of the most fundamental database querying problem in the context of XML. This is the problem to define monadic node queries in trees. This problem has been widely studied on both practical and theoretical point of view.

However, many applications of semi-structured documents need to solve more complex querying problems. The next more general problem is to define selection for tuples of nodes in trees, i.e., to express n-ary queries.

We devise formalisms for expressing n-ary queries in trees following two directions: first, we extend the tree automaton approach proposed by Frick, Grohe and Koch. Tuples of nodes are selected by successful runs of tree automata. We prove this formalism to capture the MSO-definable queries, that is, queries that can be defined by a formula from the monadic second-order logic (MSO). Then, we consider the restricted case of non-ambiguous tree automata and provide results about such defined queries.

As a second approach, we develop a logical formalism called composition. The underlying idea is to "compose" monadic queries to define n-ary ones. We prove several properties of our formalism related to minimality and expressiveness.

Références :

Home page : http://www.lifl.fr/~talbot/