Query preservation is a notion for information preservation when the structure of the data is updated. We discuss the decidability of several query preservation problems for tree-structured data.
Firstly, we consider the problem of deciding whether a query can be preserved by a nondeterministic view. It is known that preservation is decidable if views are given by single-valued non-copying devices such as compositions of single-valued extended linear top-down tree transducers with regular look-ahead, and queries are given by deterministic MSO tree transducers. In this presentation, we show an extension of the previous result to the case that views are given by nondeterministic devices that are not always single-valued.
Secondly, we discuss the decidability of node query preservation problems. We assume a view given by a deterministic linear top-down data tree transducer (abbreviated as DLTTV) and an n-ary query based on runs of a tree automaton. We show that weak preservation problem is coNP-complete and strong preservation problem is in 2-EXPTIME. We also show that the problems are decidable when a given transducer is a single-valued extended linear top-down data tree transducer with regular look-ahead, which is a more expressive transducer than DLTTV.