More Web Proxy on the site http://driver.im/

article

Free access

TIMBER: A native XML database

Authors:

H. V. Jagadish,

L. V. S. Lakshmanan,

N. Wiwatwattana,

C. YuAuthors Info & Claims

The VLDB Journal — The International Journal on Very Large Data Bases, Volume 11, Issue 4

Pages 274 - 291

https://doi.org/10.1007/s00778-002-0081-x

Published: 12 December 2002 Publication History

Abstract

This paper describes the overall design and architecture of the Timber XML database system currently being implemented at the University of Michigan. The system is based upon a bulk algebra for manipulating trees, and natively stores XML. New access methods have been developed to evaluate queries in the XML context, and new cost estimation and query optimization techniques have also been developed. We present performance numbers to support some of our design decisions. We believe that the key intellectual contribution of this system is a comprehensive set-at-a-time query processing ability in a native XML store, with all the standard components of relational query processing, including algebraic rewriting and a cost-based optimizer.

References

[1]

1. A. Aboulnaga, A.R. Alameldeen, J.F. Naughton (2001) Estimating the selectivity of XML path expressions for Internet scale applications. In: Proc. VLDB Conf., Rome, Italy.

[2]

2. S. Al-Khalifa, H.V. Jagadish, N. Koudas, J.M. Patel, D. Srivastava, Y. Wu (2002) Structural joins: a primitive for efficient XML query pattern matching. In: Proc. ICDE Conf., March.

[3]

3. S. Al-Khalifa, H.V. Jagadish (2002) Multi-level operator combination in XML query processing. In: Proc. CIKM Conf., Nov.

[4]

4. ApacheWeb Site (2002) Item 10 on Xindice FAQ. http://xml.apache.org/xindice/FAQ

[5]

5. D. Barbosa, A. Barta, A. Mendelzon, G. Mihaila, F. Rizzolo, P. Rodriguez-Gianolli (2001) ToX - The Toronto XML engine. Proc. Int. Workshop on Information Integration on the Web, Rio de Janeiro.

[6]

6. C. Baru, A. Gupta, B. Ludaescher, R. Marciano, Y. Papakonstantinou, P. Velikhov (1999) XML-Based information mediation with MIX. In: Exhibitions Program of SIGMOD Conf.

[7]

7. R.S. Boyer, J.S. Moore (1997) A fast string searching algorithm. Communications of the ACM 20(10):762-772.

[8]

8. M.J. Carey, D.J. DeWitt, M.J. Franklin, N.E. Hall, M.L. McAuliffe, J.F. Naughton, D.T. Schuh, M.H. Solomon, C.K. Tan, O.G. Tsatalos, S.J. White, M.J. Zwilling (1994) Shoring up persistent applications. In: Proc SIGMOD Conf., pp 383-394.

[9]

9. D. Chamberlin, D. Florescu, J. Robie, J. Simeon, M. Stefanescu (2002) XQuery: A query language for XML. W3C Working Draft. Available at: http://www.w3.org/TR/xquery

[10]

10. D. Chamberlin, J. Robie, D. Florescu (2000) Quilt: An XML query language for heterogeneous data sources. In: Informal Proc. WebDB Workshop, pp 53-62, May.

[11]

11. Z. Chen, H.V. Jagadish, F. Korn, N. Koudas, S. Muthukrishnan, RT. Ng, D. Srivastava (2001) Counting twig matches in a tree. In: Proc. ICDE, Heidelberg, Germany, pp 595-604.

[12]

12. S.Y. Chien, V.J. Tsotras, C. Zaniolo, D. Zhang (2002) Efficient complex query support for multiversion XML documents. In: Proc. EDBT, Prague, Czech Republic, pp 161-178 pp 21-29.

[13]

13. J. Claussen, A. Kemper, G. Moerkotte, K. Peithner, M. Steinbrunn (2000) Optimization and evaluation of disjunctive queries. IEEE Trans Knowl Data Eng 12(2):238-260.

[14]

14. J. Claussen, A. Kemper, G. Moerkotte, K. Peithner (1997) Optimizing queries with universal quantification in object-oriented and object-relational databases. In: Proc.VLDB Conf., pp 286- 295.

[15]

15. V. Christophides, S. Cluet, G. Moerkotte (1996) Evaluating queries with generalized path expressions. In: Proc. SIGMOD Conf., pp 413-422, June.

[16]

16. E. Cohen, H. Kaplan, T. Milo (2002) Labeling dynamic XML trees. In: Proc. PODS Conf., pp 271-281, June.

[17]

17. M.P. Consens, T. Milo (1995) Algebras for querying text regions. In: Proc. PODS Conf.

[18]

18. B. Cooper, N. Sample, M.J. Franklin, G.R. Hjaltason, M. Shadmon (2001) A fast index for semistructured data. Proc. VLDB Conf., pp 341-350, Sept.

[19]

19. A. Deutsch, M. Fernandez, D. Florescu, A. Levy, D. Suciu (1998) XML-QL: A query language for XML. Submission to the World Wide Web Consortium 19 August 1998. Available at: http://www.w3.org/TR/NOTE-xml-ql. Morgan Kaufmann, San Francisco.

[20]

20. D. DeWitt, J. Naughton, D. Schneider (1991) An evaluation of non-equijoin algorithms. Proc. SIGMOD Conf., pp 443-452, Denver, Colo., USA.

[21]

21. L. Fegaras, R. Elmasri (2001) Query engines for web-accessible XML data. In: Proc. VLDB Conf., Rome, Italy, Sept.

[22]

22. M.F. Fernandez, J. Simeon, P. Wadler (2000) An algebra for XML query. Proc. FSTTCS Conf., pp 11-45.

[23]

23. T. Fiebig, G. Moerkotte (2000) Evaluating queries on structure with eXtended access support relations. Informal Proc. WebDB Workshop, pp 125-136.

[24]

24. D. Florescu, G. Graefe, G. Moerkotte, H. Pirahesh, H. Schning (2001) Panel: XML Data management: go native or spruce up relational systems? In: Proc. SIGMOD Conf., Santa Barbara, Calif., USA, May.

[25]

25. D. Florescu, D. Kossman (1999) Storing and querying XML data using an RDBMS. IEEE Data Eng Bull 22(3):27-34.

[26]

26. L. Galanis, E. Viglas, D.J. DeWitt, J.F. Naughton, D. Maier (2002) Following the paths of XML data: an algebraic framework for XML query evaluation. Tech. Report, University of Wisconsin.

[27]

27. R. Goldman, J.Widom (1997) DataGuides enabling query formulation and optimization in semistructured databases. In: Proc. VLDB Conf., pp 436-445, Athens, Greece, August.

[28]

28. R. Goldman, J. Widom (2000) Summarizing and searching sequential semistructured sources. Technical Report, March.

[29]

29. H.V. Jagadish, L.V.S. Lakshmanan, D. Srivastava, K. Thompson (2001) TAX: A Tree algebra for XML. In: Proc. DBPL Conf., Rome, Italy, Sept.

[30]

30. C.C. Kanne, G. Moerkotte (2000) Efficient storage of XML data. In: Proc. ICDE Conf., poster abstract, p 198, San Diego, Calif., USA, March.

[31]

31. C.C. Kanne, G. Moerkotte (1999) Efficient relational storage and retrieval of XML documents. Technical Report 8/99, University of Mannheim.

[32]

32. D.D. Kha, M. Yoshikawa, S. Uemura (2001) An XML indexing structure with relative region coordinate. In: Proc. ICDE Conf., pp 313-320.

[33]

33. C. Kilger, G. Moerkotte (1994) Indexing multiple sets. Proc. VLDB Conf., pp 180-191, Sept.

[34]

34. M. Klettke, H. Meyer (2000) XML and object-relational database systems - enhancing structural mappings based on statistics. In: Informal Proc. WebDB Workshop, pp 151-170.

[35]

35. D.E. Knuth, J.H. Morris Jr, V.R. Pratt (1977) Fast pattern matching in strings. SIAM J Comput 6(1):323-350.

[36]

36. S.A.T. Lahiri, J. Widom (1999) Ozone: integrating structured and semistructured data. In: Proc. DBPL Conf., Kinloch Rannoch, Scotland, UK, Sept.

[37]

37. A. Laux, L. Martin (2002) XUpdate Working Draft, Sep. 2000. Available at: http://www.xmldb.org/xupdate/xupdate-wd.html

[38]

38. P.J. Marrón, G. Lausen (2001) On processing XML in LDAP. 27th Conf. VLDB, pp 601-610.

[39]

39. J. McHugh, S. Abiteboul, R. Goldman, D. Quass, J. Widom (1997) Lore: A database management systems for semistructured data. SIGMOD Rec 26(3):54-66.

[40]

40. J. McHugh, J. Widom (1999) Query optimization for XML. In: Proc. VLDB Conf., pp 315-326.

[41]

41. J. McHugh, J. Widom, S. Abiteboul, Q. Luo, A. Rajaraman (1988) Indexing semistructured data. Technical Report, January. Available at: http://www-db.stanford.edu/lore/pubs

[42]

42. Microsoft XQuery Language Demo (2002) Available at: http://131.107.228.20/xquerydemo/

[43]

43. J. Naughton, D. DeWitt, D. Maier, et al (2002) The Niagara internet query system. Available at: http://www.cs.wisc.edu/niagara/papers/ NIAGARAVLDB00.v4.pdf.

[44]

44. University of Wisconsin (2002) The Niagara system. Available at: http://www.cs.wisc.edu/niagara/

[45]

45. S. Paparizos, S. Al-Khalifa, H.V. Jagadish, L. Lakshmanan, A. Nierman, D. Srivastava, Y. Wu (2002) Grouping in XML. In: EDBT 2002 Workshop on XML-Based Data Management (XMLDM'02).

[46]

46. D. Quass, J. Widom, R. Goldman, H.K, Q. Luo, J. Mchugh, A. Rajaraman, H. Rivero, S. Abiteboul, J. Ullman, J. Wiener (1996) Lore: A lightweight object repository for semistructured data. Proc. SIGMOD Conf., p 549.

[47]

47. J. Robie, J. Lapp, D. Schach () XML Query language (XQL). Available at: http://www.w3.org/TandS/QL/QL98/pp/xql.html

[48]

48. K. Runapongsa, J.M. Patel (2002) Storing and querying XML data in ORDBMSs. EDBT XML-Based Data Management (XMLDB) Workshop, March 24, Prague, Czech Republic.

[49]

49. A. Sahuguet (2001) Kweelt: More than just "Yet another framework to query XML!". Proc. SIGMOD Conf., Santa Barbara, Calif., USA. Software available at: http://db.cis.upenn.edu/Kweelt/. McGraw-Hill, NewYork.

[50]

50. A. Schmidt, M.L. Kersten, M. Windhouwer (2001) Querying XML documents made easy: nearest concept queries. In: Proc. ICDE Conf., pp 321-329.

[51]

51. H. Schoning (2001) Tamino - A DBMS designed for XML. In: Proc. ICDE Conf., pp 149-154.

[52]

52. H. Schoning, J. Wasch (2000) Tamino - An internet database system. In: Proc. EDBT Conf., pp 383-387.

[53]

53. J. Shanmugasundaram, K. Tufte, G. He, C. Zhang, D. DeWitt, J. Naughton (1999) Relational databases for querying XML documents: limitations and opportunities. In: Proc. VLDB Conf. pp 302-314, Edinburgh, Scotland, UK, Sept.

[54]

54. T. Shimura, M. Yoshikawa, S. Uemura (1999) Storage and retrieval of XML documents using object-relational databases. In: Proc. DEXA Conf., pp 206-217, Florence, Italy, Sept.

[55]

55. I. Tatarinov, Z.G. Ives, A.Y. Halevy, D.S. Weld (2001) Updating XML. In: Proc. SIGMOD Conf.

[56]

56. F. Tian, D.J. DeWitt, J. Chen, C. Zhang (2000) The design and performance evaluation of various XML storage strategies. Technical Report, University of Wisconsin.

[57]

57. University of Washington (2002) The Tukwila system. Available at: http://data.cs.washington.edu/integration/tukwila/

[58]

58. B. Vance, D. Maier (1996) Rapid bushy join-order optimization with Cartesian products. In: Proc. SIGMOD Conf., pp 35-46, Montreal, Quebec.

[59]

59. Y. Wu, J.M. Patel, H.V. Jagadish (2002) Estimating answer sizes for XML queries. In: Proc. EDBT Conf., Prague, Czech Republic, March.

[60]

60. Y. Wu, J.M. Patel, H.V. Jagadish (2002) Using histograms to estimate answer sizes for XML queries. Inf Syst (to appear).

[61]

61. Y. Wu, H.V. Jagadish (2003) Structural join order selection for XML query optimization In: Proc. ICDE Conf., Bangalore, India, March (to appear).

[62]

62. W3C DOM Working Group (2002) Document object model. Available at: http://www.w3.org/DOM/

[63]

63. W3C (2002) Extensible Markup Language (XML) 1.0. W3C Recommendation. Available at: http://www.w3.org/XML

[64]

64. C. Zhang, J. Naughton, D. Dewitt, Q. Luo, G. Lohman (2001) On supporting containment queries in relational database management systems. In: Proc. SIGMOD Conf., Santa Barbara, Calif., USA.

[65]

65. Tamino Developer Community (2002) QuiP, a W3C XQuery prototype. Available at: http://www.softwareag.com/developer/quip

[66]

66. eXcelon Corp (2002) eXcelon XML platform. Available at: http://www.exceloncorp.com/platform/extinfserver.shtml

[67]

67. X-Hive Corp (2002) X-Hive/DB. Available at: http://www.x-hive.com

[68]

68. dbXML Group (2002) dbXML Core. Available at: http://www.dbxml.org

[69]

69. W3C (2002) XML Schema. W3C Recommendation. Available at: http://www.w3.org/XML/Schema

[70]

70. OASIS Technical Committee (2002) Relax NG. Available at: http://www.oasis-open.org/committees/relax-ng/

[71]

71. The Michigan Benchmark Team (202) The University of Michigan, Available at: http://www.eecs.umich.edu/db/mbench

[72]

72. The Timber Team (2002) The University of Michigan, Available at: http://www.eecs.umich.edu/db/timber

Cited By

Jamkhedkar PJohnson TKanza YShaikh AShankaranarayanan NShkapenyuk VDas GJermaine CBernstein P(2018)A Graph Database for a Virtualized Network InfrastructureProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3190653(1393-1405)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3190653
Bača RKrátký MHolubová INečaský MSkopal TSvoboda MSakr S(2017)Structural XML Query ProcessingACM Computing Surveys10.1145/309579850:5(1-41)Online publication date: 26-Sep-2017
https://dl.acm.org/doi/10.1145/3095798
Jamkhedkar PJohnson TKanza YShaikh AShankarnarayanan NShkapenyuk VWoodhull GChirkova RYang JSuciu D(2017)Virtualized Network Service Topology Exploration Using NepalProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3058733(1611-1614)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3035918.3058733
Show More Cited By

Index Terms

TIMBER: A native XML database

Recommendations

Native XML support in DB2 universal database
VLDB '05: Proceedings of the 31st international conference on Very large data bases

The major relational database systems have been providing XML support for several years, predominantly by mapping XML to existing concepts such as LOBs or (object-)relational tables. The limitations of these approaches are well known in research and ...
XLight, An Efficient Relational Schema to Store and Query XML Data
DSDE '10: Proceedings of the 2010 International Conference on Data Storage and Data Engineering

Because of increasing use of XML data on the internet, the need for an efficient method of storing and querying XML data is vital. So far, two major types of system for XML data management have been introduced: XML Enabled systems and XML native ...
Filtering XPath expressions for XML access control

XPath is a standard for specifying parts of XML documents and a suitable language for both query processing and access control of XML. In this paper, we use the XPath expression for representing user queries and access control for XML. And we propose an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The VLDB Journal — The International Journal on Very Large Data Bases

The VLDB Journal — The International Journal on Very Large Data Bases Volume 11, Issue 4

December 2002

130 pages

ISSN:1066-8888

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 December 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

127
Total Citations
View Citations
2,827
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)8

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jamkhedkar PJohnson TKanza YShaikh AShankaranarayanan NShkapenyuk VDas GJermaine CBernstein P(2018)A Graph Database for a Virtualized Network InfrastructureProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3190653(1393-1405)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3190653
Bača RKrátký MHolubová INečaský MSkopal TSvoboda MSakr S(2017)Structural XML Query ProcessingACM Computing Surveys10.1145/309579850:5(1-41)Online publication date: 26-Sep-2017
https://dl.acm.org/doi/10.1145/3095798
Jamkhedkar PJohnson TKanza YShaikh AShankarnarayanan NShkapenyuk VWoodhull GChirkova RYang JSuciu D(2017)Virtualized Network Service Topology Exploration Using NepalProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3058733(1611-1614)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3035918.3058733
Finis JBrunel RKemper ANeumann TMay NFaerber F(2017)Order IndexesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-016-0436-326:1(55-80)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s00778-016-0436-3
Johnson TKanza YLakshmanan LShkapenyuk VArora ARoy SMehta S(2016)NepalProceedings of the 1st ACM SIGMOD Workshop on Network Data Analytics10.1145/2980523.2980530(1-8)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1145/2980523.2980530
Papakonstantinou YÖzcan FKoutrika GMadden S(2016)Semistructured Models, Queries and Algebras in the Big Data EraProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2912573(2229-2233)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2912573
Finis JBrunel RKemper ANeumann TMay NFaerber F(2015)Indexing highly dynamic hierarchical dataProceedings of the VLDB Endowment10.14778/2794367.27943698:10(986-997)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.14778/2794367.2794369
Mcminn PWright CKapfhammer G(2015)The Effectiveness of Test Coverage Criteria for Relational Database Schema Integrity ConstraintsACM Transactions on Software Engineering and Methodology10.1145/281863925:1(1-49)Online publication date: 2-Dec-2015
https://dl.acm.org/doi/10.1145/2818639
Landberg ARahayu JPardede E(2014)XTriggerComputer Science - Research and Development10.1007/s00450-010-0132-229:1(1-19)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s00450-010-0132-2
Andrikopoulos PBelsis PKetikidis PMargaritis KVlahavas IChatzigeorgiou AEleftherakis GStamelos I(2013)Towards effective organization of medical dataProceedings of the 17th Panhellenic Conference on Informatics10.1145/2491845.2491890(305-310)Online publication date: 19-Sep-2013
https://dl.acm.org/doi/10.1145/2491845.2491890
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents