Journal of Computer Science

An Efficient Algorithm for Tree Mapping in XML Databases

Yangjun Chen

DOI : 10.3844/jcssp.2007.487.493

Journal of Computer Science

Volume 3, Issue 7

Pages 487-493


In this article, we discuss an efficient algorithm for tree mapping problem in XML databases. Given a target tree T and a pattern tree Q, the algorithm can find all the embeddings of Q in T in O(|T||Q|) time while the existing approaches need exponential time in the worst case.


© 2007 Yangjun Chen. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.