• Articles • Previous Articles     Next Articles

HCH for checking containment of XPath fragment

Jian-Hua Feng, Yu-Guo Liao, and Yong Zhang   

  1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  • Received:2006-04-18 Revised:2007-03-07 Online:2007-09-10 Published:2007-09-10

XPath is ubiquitous in XML applications for navigating XML trees and selecting a set of element nodes. In XPath query processing, one of the most important issues is how to efficiently check containment relationship between two XPath expressions. To get out of the intricacy and complexity caused by numerous XPath features, we investigate this issue on a frequently used fragment of XPath expressions that consists of node tests, the child axis (/), the descendant axis (//), branches ([\,]) and label wildcards ($*$). Prior work has shown that homomorphism technology can be used for containment checking. However, homomorphism is the sufficient but not necessary condition for containment. For special classes of this fragment, the homomorphism algorithm returns false negatives. To address this problem, this paper proposes two containment techniques, conditioned homomorphism and hidden conditioned homomorphism, and then presents sound algorithms for checking containment. Experimental results confirm the practicability and efficiency of the proposed algorithms.

Key words: programming language; recursive function; context-free language; interpreter; parsing; formal specification;

[1] James Clark, Steve DeRose. XML path language (XPath), version 1.0. W3C Recommendation, http://www.w3.org/TR/xpath.

[2] Scott Boag, Don Chamberlin -\it et al}. XQuery 1.0: An XML query language. W3C Candidate Recommendation. http://www.w3.org/TR/xquery.

[3] Steven DeRose, Eve Maler -\it et al}. XML linking language (XLink), version 1.0. W3C Recommendation, http://www.w3.org/TR/xlink.

[4] Steven DeRose, Ron Daniel Jr. -\it et al}. XML pointer language (XPointer). W3C Working draft, http://www. w3.org/TR/xptr.

[5] James Clark. XSL transformations (XSLT), version 1.0. W3C Recommendation, http://www.w3.org/TR/xslt.

[6] Gerome Miklau, Dan Suciu. Containment and equivalence for a fragment of XPath. -\it Journal of the ACM}, 2004, 51(1): 2$\sim$45.

[7] Thomas Schwentick. XPath query containment. -\it ACM SIGMOD Record}, 2004, 33(1): 101$\sim$109.

[8] Ashok K Chandra, Philip M Merlin. Optimal implementation of conjunctive queries in relational data bases. In -\it Proc. the 9th ACM Symposium on Theory of Computing}, Boulder, Colorado, USA, May 4$\sim$4, 1977, pp.77$\sim$90.

[9] Peter Buneman, Susan Davidson -\it et al}. Reasoning about keys for XML. In -\it Proc.the 8th Int. Workshop on Database Programming Languages $($DBPL$)$}, Kinloch Rannoch, Scotland, Sept. 1$\sim$3, 1999, pp.133$\sim$148.

[10] Tova Milo, Dan Suciu T. Index structures for path expressions. In -\it Proc. the 7th Int. Conference on Database Theory $($ICDT$)$}, Jerusalem, Israel, Jan. 10$\sim$12, 1999, pp.277$\sim$295.

[11] Peter T Wood. Minimizing simple xpath expressions. In -\it Proc. the 4th Int. Workshop on the Web and Databases $($WebDB$)$}, Santa Barbara, California, USA, May 24$\sim$25, 2001, pp.13$\sim$18.

[12] Sihem Amer-Yahia, SungRan Cho -\it et al}. Minimization of tree pattern queries. In -\it Proc. the ACM SIGMOD Conf. Management of Data}, Santa Barbara, California, USA, May 21$\sim$24, 2001, pp.497$\sim$508.

[13] Oded Shmueli. Equivalence of datalog queries is undecidable. -\it The Journal of Logic Programming}, 1993, 15(3): 231$\sim$242.

[14] Peter T Wood. On the equivalence of XML patterns. In -\it Proc. the First Int. Conference on Computational Logic $($CL$)$}, London, UK, July 24$\sim$28, 2000, pp.1152$\sim$1166.

[15] Frank Neven, Thomas Schwentick. XPath containment in the presence of disjunction, DTDs, and variables. In -\it Proc. the 9th Int. Conf. Database Theory $($ICDT$)$}, Siena, Italy, Jan. 8$\sim$10, 2003, pp.315$\sim$329.

[16] Daniela Florescu, Alon Levy -\it et al}. Query containment for conjunctive queries with regular expressions. In -\it Proc. the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems $($PODS$)$}, Seattle, Washington, USA, June 1$\sim$3, 1998, pp.139$\sim$148.

[17] Diego Calvanese, Giuseppe De Giacomo -\it et al}. View-based query answering and query containment over semistructured data. In -\it Proc. the 8th Int. Workshop on Database Programming Languages $($DBPL$)$}, Frascati, Italy, Sept. 8$\sim$10, 2001, pp.40$\sim$61.

[18] Sihem Amer-Yahia, SungRan Cho -\it et al}. Tree pattern query minimization. -\it The VLDB Journal}, 2002, 11(4): 315$\sim$331.

[19] Frank Neven. Automata theory for XML researchers. -\it ACM SIGMOD Record}, 2002, 31(3): 39$\sim$46.

[20] Peter T Wood. Containment for XPath fragments under DTD constraints. In -\it Proc. the 9th Int. Conference on Database Theory $($ICDT$)$}, Siena, Italy, Jan. 8$\sim$10, 2003, pp.300$\sim$314.
[1] Chuan-Kang Li, Hong-Xin Zhang, Jia-Xin Liu, Yuan-Qing Zhang, Shan-Chen Zou, Yu-Tong Fang. Window Detection in Facades Using Heatmap Fusion [J]. Journal of Computer Science and Technology, 2020, 35(4): 900-912.
[2] Xin-Yu Ou, Ping Li, He-Fei Ling, Si Liu, Tian-Jiang Wang, Dan Li. Objectness Region Enhancement Networks for Scene Parsing [J]. , 2017, 32(4): 683-700.
[3] Lin-Er Yang, Mao-Song Sun, Yong Cheng, Jia-Cheng Zhang, Zheng-Hao Liu, Huan-Bo Luan, Yang Liu. Neural Parse Combination [J]. , 2017, 32(4): 749-757.
[4] Xin-Qi Bao, Yun-Fang Wu. A Tensor Neural Network with Layerwise Pretraining: Towards Effective Answer Retrieval [J]. , 2016, 31(6): 1151-1160.
[5] Suchakrapani Datt Sharma, Student Member, IEEE, Michel Dagenais, Senior Member, IEEE. Enhanced Userspace and In-Kernel Trace Filtering for Production Systems [J]. , 2016, 31(6): 1161-1178.
[6] Guo-Dong Zhou, and Pei-Feng Li. Improving Syntactic Parsing of Chinese with Empty Element Recovery [J]. , 2013, 28(6): 1106-1116.
[7] Jie Tang, Chen Liu, Shao-Shan Liu, Zhi-Min Gu, and Jean-Luc Gaudiot. Pinned OS/Services: A Case Study of XML Parsing on Intel SCC [J]. , 2013, 28(1): 3-13.
[8] Dong-Xi Liu. CSchema: A Downgrading Policy Language for XML Access Control [J]. , 2007, 22(1): 44-53 .
[9] Hai-Ming Chen and Yun-Mei Dong. Practical Type Checking of Functions Defined on Context-Free Languages [J]. , 2004, 19(6): 0-0.
[10] QI Xuan (齐璇), ZHOU Huiping (周会平) and CHEN Huowang (陈火旺). An Interlingua-Based Chinese-English MT System [J]. , 2002, 17(4): 0-0.
[11] WANG Yunfeng(王云峰),PANG Jun(庞军),ZHA Ming(查鸣),YANG Zhaohui(杨朝晖)and ZHENG Guoliang(郑国梁). A Formal Software Development Approach Using Refinement Calculus [J]. , 2001, 16(3): 0-0.
[12] CHEN Haiming(陈海明)and DONG Yunmei(董韫美). Pattern Matching Compilation of Function Defined in Context-Free Languages [J]. , 2001, 16(2): 0-0.
[13] CHEN Haiming;. Function Definition Language FDL andIts Implementation [J]. , 1999, 14(4): 414-421.
[14] Lin Hong; Chen Guoliang;. Program Constructionby Verifying Specification [J]. , 1998, 13(6): 597-607.
[15] Dong Yunmei;. An Interactive Learning Algorithm for Acquisition of Concepts Represented as CFL [J]. , 1998, 13(1): 1-8.
Full text



[1] Feng Yulin;. Hierarchical Protocol Analysis by Temporal Logic[J]. , 1988, 3(1): 56 -69 .
[2] Tai Juwei; Wang Jue; Chen Xin;. A Syntactic-Semantic Approach for Pattern Recognition and Knowledge Representation[J]. , 1988, 3(3): 161 -172 .
[3] Cai Shijie; Zhang Fuyan;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[4] Zhang Bo; Zhang Ling;. A Relation Matrix Approach to Labelling Temporal Relations in Scheduling[J]. , 1991, 6(4): 339 -346 .
[5] LIU Bin; LU Zengxiang; GAN Quan; FENG Ao; WANG Pu;. Infomarker—A New Internet Information Service System[J]. , 2000, 15(3): 300 -304 .
[6] Ji-Gang Wu and Thambipillai Srikanthan. Power Efficient Sub-Array in Reconfigurable VLSI Meshes[J]. , 2005, 20(5): 647 -653 .
[7] Jing Li, Thomas Fang Zheng, William Byrne, and Dan Jurafsky. A Dialectal Chinese Speech Recognition Framework[J]. , 2006, 21(1): 106 -115 .
[8] Wen-Cheng Wang, Feng Wei, and En-Hua Wu. View Dependent Sequential Point Trees[J]. , 2006, 21(2): 181 -188 .
[9] Gang Xu and Guo-Zhao Wang. AHT Bézier Curves and NUAHT B-Spline Curves[J]. , 2007, 22(4): 597 -607 .
[10] Zhang-Lin Cheng, Xiao-Peng Zhang, and Bao-Quan Chen. Simple Reconstruction of Tree Branches from a Single Range Image[J]. , 2007, 22(6): 846 -858 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved