TREE EMBEDDING AND XML QUERY EVALUATION

Yangjun Chen

2008

Abstract

Tree pattern matching is one of the most fundamental tasks for XML query processing. Prior work has typically decomposed the tree pattern into binary structural (parent-child and ancestor-descendent) relationships or paths, and then stitch together these basic matches by join operations. In this paper, we propose a new algorithm that explores both the document tree and the twig pattern in a bottom-up way and show that the join operation can be completely avoided. The new algorithm runs in O(|T|×|Q|) time and O(|Q|×leafT) space, where T and Q are the document tree and the tree pattern query, respectively; and leafT represents the number of leaf nodes in T.

Paper Citation

in Harvard Style

Chen Y. (2008). TREE EMBEDDING AND XML QUERY EVALUATION . In Proceedings of the Tenth International Conference on Enterprise Information Systems - Volume 1: ICEIS, ISBN 978-989-8111-36-4, pages 173-178. DOI: 10.5220/0001690301730178

in Bibtex Style

@conference{iceis08,
author={Yangjun Chen},
title={TREE EMBEDDING AND XML QUERY EVALUATION},
booktitle={Proceedings of the Tenth International Conference on Enterprise Information Systems - Volume 1: ICEIS,},
year={2008},
pages={173-178},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001690301730178},
isbn={978-989-8111-36-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Tenth International Conference on Enterprise Information Systems - Volume 1: ICEIS,
TI - TREE EMBEDDING AND XML QUERY EVALUATION
SN - 978-989-8111-36-4
AU - Chen Y.
PY - 2008
SP - 173
EP - 178
DO - 10.5220/0001690301730178