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 20 Issue 3
May  2005
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Dun-Ren Che. Accomplishing Deterministic XML Query Optimization[J]. Journal of Computer Science and Technology, 2005, 20(3): 357-366.
Citation: Dun-Ren Che. Accomplishing Deterministic XML Query Optimization[J]. Journal of Computer Science and Technology, 2005, 20(3): 357-366.
shu

Accomplishing Deterministic XML Query Optimization

  • Department of Computer Science, Southern Illinois University, Carbondale, IL 62901, U.S.A.

More Information
  • Received Date: April 06, 2004
  • Revised Date: October 12, 2004
  • Published Date: May 14, 2005
    Abstract
  • As the popularity of XML (eXtensible Markup Language) keeps growingrapidly, the management of XML compliant structured-document databaseshas become a very interesting and compelling research area. Queryoptimization for XML structured-documents stands out as one of the mostchallenging research issues in this area because of the much enlargedoptimization (search) space, which is a consequence of the intrinsiccomplexity of the underlying data model of XML data. We thereforepropose to apply deterministic transformations on query expressions tomost aggressively prune the search space and fast achieve a sufficientlyimproved alternative (if not the optimal) for each incoming queryexpression. This idea is not just exciting but practically attainable.This paper first provides an overview of our optimization strategy, andthen focuses on the key implementation issues of our rule-basedtransformation system for XML query optimization in a databaseenvironment. The performance results we obtained from experimentationshow that our approach is a valid and effective one.
    • FullText(HTML)
    • References (21)
  • [1]
    Fernandez M F et al. SilkRoute: Trading betweenrelations and XML. Computer Networks 2000, 33(1-6): 723--745.
    [2]
    Florescu D, Kossmann D. Storing and querying XML datausing an RDMBS. IEEE Data Engineering Bulletin 1999, 22(3): 27--34.
    [3]
    Shanmugasundaram J, Tufte K, He G et al. Relational databases for querying XML documents: Limitationsand opportunities. In Proc. VLDB 1999, pp.302--314.
    [4]
    Bohannon P, Freire J, Roy P, Simeon J. From XML schema torelations: A cost-based approach to XML storage. In Proc.18th Int. Conf. Data Engineering (ICDE) 2002, pp.64--75.
    [5]
    Klettke M, Meyer H. XML and object-relational database systems--Enhancing structural mappings based on statistics. In Proc.Int. Workshop on the Web and Databases (WebDB) Dallas, May 2000,pp.63--68.
    [6]
    Surjanto B, Ritter N, Loeser H. XML content management basedon object-relational database technology. In Proc. The 1st Int.Conf. Web Information Systems Engineering (WISE) Hong Kong, June2000, pp.70--79.
    [7]
    McHugh J, Abiteboul S, Goldman R et al. Lore:A database management system for semistructured data. SIGMODRecord Sep. 1997, 26(3): pp.54--66.
    [8]
    Che D, Aberer K. A heuristics-based approach to queryoptimization in structured document databases. In Proc. 1999Int. Database Engineering & Application Symposium Montreal, Canada,Aug. 2--4, 1999, pp.24--33.
    [9]
    Salminen A et al. PAT expressions: An algebra for textsearch. Acta Linguistica Hungarica 1994, 41(1): 277--306.
    [10]
    Bǒhm K, Aberer K, Neuhold E J, Yang X. Structureddocument storage and refined declarative and navigational access mechanisms inHyperStorM. The VLDB Journal Nov. 1997, 6(4): 296--311.
    [11]
    Clark J, DeRose S. XML path language (Xpath) version 1.0.http://www.w3.org/TR/1999/REC-xpath-19991116
    [12]
    Boag S, Chamberlin D, Fernandez M F et al. Xquery 1.0: An XML query language.http://www.w3.org/ TR/2004/WD-xquery-20040723/
    [13]
    Che D, Aberer K, ǒzsu M T. Query Optimization in XMLStructured-Document Database Systems (Manuscript in preparation for -The VLDBJournal ).
    [14]
    Che D. Implementation issues of a deterministic transformationsystem for structured document query optimization. In Proc. 2003Int. Database Engineering & Application Symposium Hong Kong, July16-18-4, 2003, pp.268--277.
    [15]
    McHugh J, Widom J. Query optimization for XML. In Proc.VLDB Edinburgh, Scotland, Sep. 1999, pp.315--326.
    [16]
    Fernandez M F, Suciu D. Optimizing regular pathexpressions using graph schemas. In Proc. 14th Int. Conf. DataEngineering Orlando, USA, Feb. 23--27, 1998, pp.14--23.
    [17]
    Flesca S, Furfaro F, Masciari E. On the minimization ofXpath queries. In Proc. VLDB 2003, pp.153--164.
    [18]
    Amer-Yahia S, Cho S, Lakshmanan L, Srivastava D.Minimization of tree pattern queries. In Proc. ACM Conf. Managementof Data (SIGMOD) 2001, pp.497--508.
    [19]
    Wood P T. Containment for Xpath fragments under DTDconstraints. In Proc. 9th Int. Conf. Database Theory Jan. 2003,pp.300--314.
    [20]
    Kwong A, Gertz M. Schema-based optimization of Xpathexpressions. Technical Report, Univ. Dept. ComputerScience, 2001.
    [21]
    Bǒhm K, Aberer K, ǒzsu M T, Gayer K. Queryoptimization for structured documents based on knowledge on the documenttype definition. In Proc. IEEE Int. Forum on Research and TechnologyAdvances in Digital Libraries (ADL'98) Santa Barbara,April 22--24, 1998, pp.196--205.
    • Relative Articles

  • Related Articles

    [1]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.
    [2]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.
    [3]Xiao-Qing Zheng, Hua-Jun Chen, Zhao-Hui Wu, Yu-Xin Mao. Dynamic Query Optimization Approach for Semantic Database Grid[J]. Journal of Computer Science and Technology, 2006, 21(4): 597-608.
    [4]Guo-Ren Wang, Bing Sun, Jian-Hua Lv, Ge Yu. RPE Query Processing and Optimization Techniques for XML Databases[J]. Journal of Computer Science and Technology, 2004, 19(2).
    [5]WANG Wei, WaNG Yujun, SHI Baile. Dynamic Interval Index Structure in Constraint Database Systems[J]. Journal of Computer Science and Technology, 2000, 15(6): 542-551.
    [6]Shen Yidong. Extracting Schema from an OEM Database[J]. Journal of Computer Science and Technology, 1998, 13(4): 289-299.
    [7]Li Tianzhu. Object Identity in Database Systems[J]. Journal of Computer Science and Technology, 1995, 10(4): 380-384.
    [8]Zhou Aoying, Shi Baile. Query Optimization for Deductive Databases[J]. Journal of Computer Science and Technology, 1995, 10(2): 134-148.
    [9]Zhang Yan, He Jichao. Data Dependencies in Database with Incomplete Information[J]. Journal of Computer Science and Technology, 1988, 3(2): 131-138.
    [10]Meng Liming, Xu Xiaofei, Chang Huiyou, Chen Guangxi, Hu Mingzeng, Li Sheng. A Tree-Structured Database Machine for Large Relational Database Systems[J]. Journal of Computer Science and Technology, 1987, 2(4): 265-275.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (18) PDF downloads (1251) Cited by()
    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