Article

Tree inclusion algorithm, signatures and evaluation of path-oriented queries

Authors:

Yangjun Chen,

Yong Shi,

Yibin ChenAuthors Info & Claims

SAC '06: Proceedings of the 2006 ACM symposium on Applied computing

Pages 1020 - 1025

https://doi.org/10.1145/1141277.1141521

Published: 23 April 2006 Publication History

Get Access

Abstract

In this paper, a method to evaluate path-oriented queries in document databases is proposed. The main idea of this method is to handle the evaluation of a path-oriented query as a tree inclusion problem. A new algorithm for tree-inclusion is discussed, which integrates a top-down process into a bottom-up searching strategy. On the one hand, the algorithm can be arranged to access the data on disk page-wise and fits therefore within a database environment. On the other hand, the algorithm can be combined with the signature indexing technique to cut off useless subtree inclusion checking as early as possible. Experiments have been conducted to compare this method with some existing approaches, which shows that the integration of the signatures into the top-down tree inclusion is highly promising.

References

[1]

L. Alonso and R. Schott. On the tree inclusion problem. In Proceedings of Mathematical Foundations of Computer Science pages 211--221, 1993.

Digital Library

Google Scholar

[2]

W. Chen. More efficient algorithm for ordered tree inclusion. Journal of Algorithms, 26:370--385, 1998.

Digital Library

Google Scholar

[3]

S. Christodoulakis and C. Faloutsos, "Design consideration for a message file server," IEEE Trans. Software Engineering, 10(2) (1984) 201--210.

Digital Library

Google Scholar

[4]

D. Florescu and D. Kossman, Storing and Querying XML Data using an RDBMS, IEEE Data Engineering Bulletin, 22(3), 1999.

Google Scholar

[5]

P. Kilpelainen and H. Mannila. Ordered and unordered tree inclusion. SIAM Journal of Computing, 24:340--356, 1995.

Digital Library

Google Scholar

[6]

T. Richter. A new algorithm for the ordered tree inclusion problem. In Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM), in Lecture Notes of Computer Science (LNCS), volume 1264, pages 150--166. Springer, 1997.

Digital Library

Google Scholar

[7]

Sangwon Park, Hyoung-Joo Kim: A New Query Processing Technique for XML. Based on Signature. DASFAA 2001: 22--27.

Digital Library

Google Scholar

[8]

C. Seo, S. Lee, and H. Kim, An Efficient Index Technique for XML Documents Using RDBMS, Information and Software Technology 45(2003) 11--22, Elsevier Science B.V.

Digital Library

Google Scholar

[9]

E. Tousidou, P. Bozanis, Y. Manolopoulos, "Signature-based structures for objects with set-values attributes," Information Systems, 27(2):93--121, 2002.

Digital Library

Google Scholar

[10]

G. Salton and M. J. McGill, "Introduction to Modern Information Retrieval," McGray-Hill Int. Book Com., Hamburg, 1983.

Digital Library

Google Scholar

[11]

H. Wang, S. Park, W. Fan, and P. S. Yu, Vist: A Dynamic Index Method for Querying XML Data by Tree Structures, SIGMOD Int. Conf. on Management of Data, San Diego, CA., June 2003.

Digital Library

Google Scholar

[12]

C. Zhang, J. Naughton, D. DeWitt, Q. Luo and G Lohman, "On Supporting Containment Queries in Relational Database Management Systems, in Proc. of ACM SIGMOD Intl. Conf. on Management of Data, California, USA, 2001.

Digital Library

Google Scholar

[13]

http://www.connexor.com/demos/index.html.

Google Scholar

Cited By

View all

Amavi JChabin JHalfeld Ferrari MRéty P(2011)Weak Inclusion for XML TypesImplementation and Application of Automata10.1007/978-3-642-22256-6_4(30-41)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22256-6_4
Yin-Fu Huang Shing-Hang Wang (2008)An Efficient XML query processing based on combining T-Bitmap and index techniques2008 IEEE Symposium on Computers and Communications10.1109/ISCC.2008.4625596(858-863)Online publication date: Jul-2008
https://doi.org/10.1109/ISCC.2008.4625596
Hadzic FDillon T(2007)Application of Tree Mining to Matching of Knowledge Structures of Decision Tree TypeOn the Move to Meaningful Internet Systems 2007: OTM 2007 Workshops10.1007/978-3-540-76890-6_60(1319-1328)Online publication date: 2007
https://doi.org/10.1007/978-3-540-76890-6_60

Index Terms

Tree inclusion algorithm, signatures and evaluation of path-oriented queries
1. Information systems
  1. Data management systems
    1. Database management system engines

Recommendations

Constrained tree inclusion
CPM'03: Proceedings of the 14th annual conference on Combinatorial pattern matching

The tree matching problem is considered of given labeled trees P and T, determining if the pattern tree P can be obtained from the text tree T by deleting degree-one and degree-two nodes and, in the case of unordered trees, by also permuting siblings. ...
A Linear-Space Top-Down Algorithm for Tree Inclusion Problem
CSSS '12: Proceedings of the 2012 International Conference on Computer Science and Service System

We consider the following tree-matching problem: Giv en labeled, ordered trees P and T, can P be obtained from T by de leting nodes__ __ Deleting a node v entails removing all edges incident to v and, if v has a parent u, replacing the edges from u to v ...
A top down algorithm for constrained tree inclusion

Given two ordered labeled trees P and T, the constrained tree inclusion problem is to determine whether it is possible to obtain P from T through a sequence of deleting degree-one or degree-two nodes. Valiente proposed a bottom up algorithm which solves ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SAC '06: Proceedings of the 2006 ACM symposium on Applied computing

April 2006

1967 pages

ISBN:1595931082

DOI:10.1145/1141277

Conference Chair:
Hisham M. Haddad
Kennesaw State University, Kennesaw, Georgia

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC06

Sponsor:

SIGAPP

SAC06: The 2006 ACM Symposium on Applied Computing

April 23 - 27, 2006

Dijon, France

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
239
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Amavi JChabin JHalfeld Ferrari MRéty P(2011)Weak Inclusion for XML TypesImplementation and Application of Automata10.1007/978-3-642-22256-6_4(30-41)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22256-6_4
Yin-Fu Huang Shing-Hang Wang (2008)An Efficient XML query processing based on combining T-Bitmap and index techniques2008 IEEE Symposium on Computers and Communications10.1109/ISCC.2008.4625596(858-863)Online publication date: Jul-2008
https://doi.org/10.1109/ISCC.2008.4625596
Hadzic FDillon T(2007)Application of Tree Mining to Matching of Knowledge Structures of Decision Tree TypeOn the Move to Meaningful Internet Systems 2007: OTM 2007 Workshops10.1007/978-3-540-76890-6_60(1319-1328)Online publication date: 2007
https://doi.org/10.1007/978-3-540-76890-6_60

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Constrained tree inclusion

A Linear-Space Top-Down Algorithm for Tree Inclusion Problem

A top down algorithm for constrained tree inclusion