D(k)-index: an adaptive structural summary for graph-structured data

ABSTRACT

To facilitate queries over semi-structured data, various structural summaries have been proposed. Structural summaries are derived directly from the data and serve as indices for evaluating path expressions on semi-structured or XML data. We introduce the D(k) index, an adaptive structural summary for general graph structured documents. Building on previous work, 1-index and A(k) index, the D(k)-index is also based on the concept of bisimilarity. However, as a generalization of the 1-index and A(k)-index, the D(k) index possesses the adaptive ability to adjust its structure according to the current query load. This dynamism also facilitates efficient update algorithms, which are crucial to practical applications of structural indices, but have not been adequately addressed in previous index proposals. Our experiments show that the D(k) index is a more effective structural summary than previous static ones, as a result of its query load sensitivity. In addition, update operations on the D(k) index can be performed more efficiently than on its predecessors.

REFERENCES

• 1: D. CHAMBERLIN, D. FLORESCU, J. ROBIE, J.SIMEON, and M. STEFANESCU. XQuery: A Query Language for XML. World Wide Web Consortium, http://www.w3.org/TR/xquery.
• 2: Alin Deutsch , Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for XML, Proceeding of the eighth international conference on World Wide Web, p.1155-1169, May 1999, Toronto, Canada
• 3: Donald D. Chamberlin , Jonathan Robie , Daniela Florescu, Quilt: An XML Query Language for Heterogeneous Data Sources, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.1-25, May 18-19, 2000
• 4: S. ABITEBOUL, D. QUASS, J. MCHUGH, J. WIDOM, and J. WIENER, The Lorel Query Language for Semistructured Data, International Journal on Digital Libraries, 1(1):68--88, April 1997.
• 5: S. ABITEBOUL, Query Semi-structured Data, ICDT, 1997.
• 6: J. CLARK and S. DEROSE, XML Path Language(XPath) Version 1.0, World Wide Web Consortium, http://www.w3.org/TR/xpath.
• 7: T. BRAY, J. PAOLI, C. M. SPERBERG-MCQUEEN, and E. MALER, Extensible Markup Language(XML) 1.0(Second Edition), W3C Recommendation, http://www.w3.org/TR/REC-xml.
• 8: S. DEROSE, E. MALER, and D. ORCHARD, XML Linking Language(XLink), version 1.0, W3C Recommendatio, http://www.w3.org/TR/xlink.
• 9: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 10: J. MCHUGH, J. WIDOM, S. ABITEBOUL, Q. LUO AND A. RAJAMARAN, Indexing Semistructured Data, Technical Report, Stanford University, January 1998.
• 11: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 12: R. KAUSHIK, P. SHENOY, P. BOHANNON AND EHUD GUDES, Exploiting Local Similarity for Efficient Indexing of Paths in Graph Structured Data, ICDE, 2002.
• 13: Neoklis Polyzotis , Minos Garofalakis, Statistical synopses for graph-structured XML databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564733]
• 14: N. POLYZOTIS, M. GAROFALAKIS, Structure and Value Synopses for XML Data Graphs, VLDB, 2002.
• 15: M. R. Henzinger , T. A. Henzinger , P. W. Kopke, Computing simulations on finite and infinite graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.453, October 23-25, 1995
• 16: Robert Paige , Robert E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, v.16 n.6, p.973-989, December 1, 1987 [doi>10.1137/0216062]
• 17: R. KAUSHIK, P. BOHANNON, J. F. NAUGHTON, AND P. SHENOY, Updates for Structure Indexes, VLDB, 2002.
• 18: Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu, Adding Structure to Unstructured Data, Proceedings of the 6th International Conference on Database Theory, p.336-350, January 08-10, 1997
• 19: T. MILO AND D. SUCIU, Optimizing Regular Path Expressions Using Graph Schemas, ICDE, 1998.
• 20: Markus Roggenbach , Mila Majster-Cederbaum, Towards a unified view of bisimulation: a comparative study, Theoretical Computer Science, v.238 n.1-2, p.81-130, May 6, 2000 [doi>10.1016/S0304-3975(99)00303-5]
• 21: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States
• 22: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 23: Brian Cooper , Neal Sample , Michael J. Franklin , Gisli R. Hjaltason , Moshe Shadmon, A Fast Index for Semistructured Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.341-350, September 11-14, 2001
• 24: Raghav Kaushik , Philip Bohannon , Jeffrey F Naughton , Henry F Korth, Covering indexes for branching path queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564707]
• 25: Chin-Wan Chung , Jun-Ki Min , Kyuseok Shim, APEX: an adaptive path index for XML data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564706]
• 26: R. BUSSE, M. CAREY, D. FLORESCU, M. KERSTEN, A. SCHMIDT, I. MAUOLESCU, AND F. WAAS, The XML Benchmark Project, Available at http://monetdb.cwi.nl/xml/index.html.
• 27: NASA is available at http://xml.gsfc.nasa.gov/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Experimentation, Performance, Theory