Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 22 Issue 5
September  2007
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Jian-Hua Feng, Yu-Guo Liao, Yong Zhang. HCH for checking containment of XPath fragment[J]. Journal of Computer Science and Technology, 2007, 22(5): 736-748.
Citation: Jian-Hua Feng, Yu-Guo Liao, Yong Zhang. HCH for checking containment of XPath fragment[J]. Journal of Computer Science and Technology, 2007, 22(5): 736-748.
shu

HCH for checking containment of XPath fragment

  • Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

More Information
  • Received Date: April 17, 2006
  • Revised Date: March 06, 2007
  • Published Date: September 14, 2007
    Abstract
  • XPath is ubiquitous in XML applications for navigatingXML trees and selecting a set of element nodes. In XPath queryprocessing, one of the most important issues is how to efficientlycheck containment relationship between two XPath expressions. To getout of the intricacy and complexity caused by numerous XPath features,we investigate this issue on a frequently used fragment of XPathexpressions that consists of node tests, the child axis (/), thedescendant axis (//), branches ([\,]) and label wildcards (∗). Prior workhas shown that homomorphism technology can be used for containmentchecking. However, homomorphism is the sufficient but not necessarycondition for containment. For special classes of this fragment, thehomomorphism algorithm returns false negatives. To address thisproblem, this paper proposes two containment techniques, conditionedhomomorphism and hidden conditioned homomorphism, and then presentssound algorithms for checking containment. Experimental results confirmthe practicability and efficiency of the proposed algorithms.
    • FullText(HTML)
    • References (20)
  • [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∼45.
    [7]
    Thomas Schwentick. XPath query containment. -\it ACM SIGMOD Record}, 2004, 33(1): 101∼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∼4, 1977, pp.77∼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∼3, 1999, pp.133∼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∼12, 1999, pp.277∼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∼25, 2001, pp.13∼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∼24, 2001, pp.497∼508.
    [13]
    Oded Shmueli. Equivalence of datalog queries is undecidable. -\it The Journal of Logic Programming}, 1993, 15(3): 231∼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∼28, 2000, pp.1152∼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∼10, 2003, pp.315∼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∼3, 1998, pp.139∼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∼10, 2001, pp.40∼61.
    [18]
    Sihem Amer-Yahia, SungRan Cho -\it et al}. Tree pattern query minimization. -\it The VLDB Journal}, 2002, 11(4): 315∼331.
    [19]
    Frank Neven. Automata theory for XML researchers. -\it ACM SIGMOD Record}, 2002, 31(3): 39∼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∼10, 2003, pp.300∼314.
    • Relative Articles

  • Related Articles

    [1]Jun-Feng Zhou, Tok Wang Ling, Zhi-Feng Bao, Xiao-Feng Meng. Related Axis: The Extension to XPath Towards Effective XML Search[J]. Journal of Computer Science and Technology, 2012, 27(1): 195-212. DOI: 10.1007/s11390-012-1217-0
    [2]Guo-Liang Li, Jian-Hua Feng. An Effective Semantic Cache for Exploiting XPath Query/View Answerability[J]. Journal of Computer Science and Technology, 2010, 25(2): 347-361.
    [3]Jian-Hua Feng, Guo-Liang Li, Na Ta. A Semantic Cache Framework for Secure XML Queries[J]. Journal of Computer Science and Technology, 2008, 23(6): 988-997.
    [4]Byron Choi, Gao Cong, Wenfei Fan, Stratis D. Viglas. Updating Recursive XML Views of Relations[J]. Journal of Computer Science and Technology, 2008, 23(4): 516-537.
    [5]Jian-Hua Feng, Qian Qian, Jian-Yong Wang, Li-Zhu Zhou. Efficient Mining of Frequent Closed XML Query Pattern[J]. Journal of Computer Science and Technology, 2007, 22(5): 725-735.
    [6]Dong-Xi Liu. CSchema: A Downgrading Policy Language for XML Access Control[J]. Journal of Computer Science and Technology, 2007, 22(1): 44-53.
    [7]Guo-Ren Wang, Xiao-Lin Zhang. Declarative XML Update Language Based on a Higher Data Model[J]. Journal of Computer Science and Technology, 2005, 20(3): 373-377.
    [8]LU Zhengding, LI Chunlin, LI Layuan. Coordinating Mobile Agents by the XML-Based Tuple Space[J]. Journal of Computer Science and Technology, 2002, 17(6).
    [9]Sun Yudong, Xie Zhiliang. Macro-Dataflow Computational Model and Its Simulation[J]. Journal of Computer Science and Technology, 1990, 5(3): 289-295.
    [10]Zhang Bo, Zhang Ling. Why SA Can Beat the Exponential Explosion in Heuristic Search[J]. Journal of Computer Science and Technology, 1990, 5(3): 259-265.
    • Supplements (0)

  • Cited by

    Periodical cited type(1)

    1. Archana Singh, Girish Lakhera, Megha Ojha, et al. Edge of Intelligence. DOI:10.1002/9781394314409.ch13

    Other cited types(0)

Catalog

    Get Citation
    XML
    Article views (22) PDF downloads (3853) Cited by(1)
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return