Query Rewriting for Nondeterministic Tree Transducers

Kazuki MIYAHARA  Kenji HASHIMOTO  Hiroyuki SEKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.6   pp.1410-1419
Publication Date: 2016/06/01
Publicized: 2016/05/02
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015FOP0007
Type of Manuscript: Special Section PAPER (Special Section on Formal Approach)
Category: Formal Methods
Keyword: 
tree transducers,  query rewriting,  query preservation,  

Full Text: PDF(432.9KB)>>
Buy this Article



Summary: 
We consider the problem of deciding whether a query can be rewritten by a nondeterministic view. It is known that rewriting 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 paper, we extend the result to the case that views are given by nondeterministic devices that are not always single-valued. We define two variants of rewriting: universal preservation and existential preservation, and discuss the decidability of them.