Looping caterpillars semistructured data querying

摘要

There are two main paradigms for querying semi structured data: regular path queries and XPath. The aim of this paper is to provide a synthesis between these two. This synthesis is given by a small addition to tree walk automata and the corresponding caterpillar expressions. These are evaluated on unranked finite sibling-ordered trees. At the expression level we add an operator whose meaning is intersection with the identity relation. This language can express every first-order definable relation and its expressive power is characterized by pebble tree walk automata that cannot inspect pebbles. We also define an expansion of the caterpillar expressions whose expressive power is characterized by ordinary pebble tree walk automata. Combining results from Bloem-Engelfriet and Gottlob-Koch, we also define an XPath like query language which is complete for all MSO definable binary relations.