Chasing Tree Patterns under Recursive DTDs

There are no files associated with this record.

Title Chasing Tree Patterns under Recursive DTDs
Author Wang, Junhu; Yu, Jeffrey Xu
Publication Title 15th International Conference, DASFAA 2010 Proceedings Part I
Editor Kitagawa, H.; Ishikawa, Y.; Li, W.; Watanabe, C.
Year Published 2010
Place of publication Germany
Publisher Springer
Abstract Finding a homomorphism between tree patterns is an important technique for testing tree pattern containment, and it is the main technique behind algorithms for rewriting tree pattern queries using views. Recent work has shown that for tree patterns P and Q that involve parent-child (/) edges, ancestor-descendant (//) edges, and branching ([]) only, under a non-disjunctive, non-recursive dtd G, testing whether P is contained in Q can be done by chasing P into P using five types of constraints derivable from G, and then testing whether P is contained in Q without G, which in turn can be done by finding a homomorphism from Q to P. We extend this work to non-disjunctive, recursive dtds. We identify three new types of constraints that may be implied by a nondisjunctive recursive dtd, and show that together with the previous five types of constraints, they are necessary, and sufficient in some important cases, to consider for testing containment of tree patterns involving /, //, and [] under G. We present two sets of chase rules to chase a tree pattern repeatedly, and compare the advantages of these chase rules.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1007/978-3-642-12026-8_20
ISBN 9783642120251
Conference name Database Systems for Advanced Applications
Location Tsukuba, Japan
Date From 2010-04-01
Date To 2010-04-04
URI http://hdl.handle.net/10072/36772
Date Accessioned 2010-10-27
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Database Management
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice