Research Article Open Access

An Efficient Algorithm for Tree Mapping in XML Databases

Yangjun Chen

Abstract

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.

Journal of Computer Science
Volume 3 No. 7, 2007, 487-493

DOI: https://doi.org/10.3844/jcssp.2007.487.493

Submitted On: 6 May 2007 Published On: 21 July 2007

How to Cite: Chen, Y. (2007). An Efficient Algorithm for Tree Mapping in XML Databases. Journal of Computer Science, 3(7), 487-493. https://doi.org/10.3844/jcssp.2007.487.493

  • 2,303 Views
  • 1,865 Downloads
  • 1 Citations

Download

Keywords

  • Tree mapping
  • XML databases
  • query evaluation
  • tree encoding