UNORDERED TREE MATCHING AND TREE PATTERN QUERIES IN XML DATABASES

Yangjun Chen

2009

Abstract

With the growing importance of XML in data ex¬change, much research has been done in providing flexible query facilities to extract data from structured XML docu¬ments. In this paper, we discuss an efficient algorithm for tree mapping problem in XML databases based on unordered tree matching. Given a target tree T and a pattern tree Q, the algorithm can find all the embeddings of Q in T in O(|D||Q|) time, where D is a largest data stream associated with a node of Q. More importantly, the algorithm is index-oriented: with XB-trees constructed over data streams, disk access can be dramatically decreased.

Paper Citation

in Harvard Style

Chen Y. (2009). UNORDERED TREE MATCHING AND TREE PATTERN QUERIES IN XML DATABASES . In Proceedings of the 4th International Conference on Software and Data Technologies - Volume 2: ICSOFT, ISBN 978-989-674-010-8, pages 191-198. DOI: 10.5220/0002238801910198

in Bibtex Style

@conference{icsoft09,
author={Yangjun Chen},
title={UNORDERED TREE MATCHING AND TREE PATTERN QUERIES IN XML DATABASES},
booktitle={Proceedings of the 4th International Conference on Software and Data Technologies - Volume 2: ICSOFT,},
year={2009},
pages={191-198},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002238801910198},
isbn={978-989-674-010-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Conference on Software and Data Technologies - Volume 2: ICSOFT,
TI - UNORDERED TREE MATCHING AND TREE PATTERN QUERIES IN XML DATABASES
SN - 978-989-674-010-8
AU - Chen Y.
PY - 2009
SP - 191
EP - 198
DO - 10.5220/0002238801910198