Chasing Tree Patterns under Recursive DTDs
Author(s)
Wang, Junhu
Yu, Jeffrey Xu
Griffith University Author(s)
Year published
2010
Metadata
Show full item recordAbstract
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 ...
View more >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.
View less >
View more >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.
View less >
Conference Title
DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, PT I, PROCEEDINGS
Volume
5981
Issue
PART 1
Subject
Database systems