Journal of KIISE:Databases (한국정보과학회논문지:데이타베이스)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

XML Query Optimization based on Signature

시그니처를 이용한 XML 질의 최적화

  • 박상원 (서울대학교 컴퓨터공학부) ;
  • 김형주 (서울대학교 컴퓨터공학부)
  • Published : 2001.03.01
Download PDF
⟨ Previous Next ⟩

Abstract

XML은 웹에서 데이터를 주고받는 표준으로 새로이 등장하고 있다. 이러한 데이터를 잘 처리하기 위하여 데이터베이스의 도움은 필연적이다. XML을 처리하는 데이터베이스에서 데이터는 트리 형태로 저장되며 질의어는 정규 경로식(regular path expression)의 특징을 가지고 있다. 이때 질의 처리는 트리의 각 노드 탐색을 통하여 수행된다. 본 논문에서는 시그니처를 이용한 저장 방법 및 질의 처리를 통하여 질의 수행 시 각 노드의 탐색 횟수를 줄여 질의 수행을 빠르게 할 수 있게 한다. 뿐만 아니라 반 구조적 데이터에 대한 인덱스도 데이터베이스 내에서 반구조적 데이터로 표현된다. 그러므로 본 논문에서 제안한 방법을 인덱스 노드에도 적용할 수 있다. 이와 같이 본 논문에서 제안한 방법은 데이터 객체와 인덱스 객체의 탐색을 줄임으로서 XML 질의를 빠르게 처리할 수 있게 한다.

Keywords

References

  1. Serge Abiteboul.. Querying Semistructured Data. International Conference on Database Theory, January 1997
  2. P. Buneman. Semistructured Data. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 1997 https://doi.org/10.1145/263661.263675
  3. Jason McHugh and Jennifer Widom. Query Optimization for XML. VLDB, 1999
  4. Jason McHugh, Serge Abiteboul, Roy Goldman, Dalian Quass, and Jennifer Widom. Lore: A Database Management System for Semistructured Data. SIGMOD Record, 26(3), 9 1997 https://doi.org/10.1145/262762.262770
  5. eXcelon. An XML Data Server For Building Enterprise Web Applications, http://www.odi.com/products/white_papers.html, 1999
  6. Alin Deutsch, Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. XML-QL: A Query Language for XML. http://www.w3.org/TR/ NOTE-xml-ql, August 1998
  7. S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel Query Language for Semistructured Data. International Journal on Digital Library, 1(1), 4 1997 https://doi.org/10.1007/s007990050005
  8. Peter Buneman, Susan Davidson, Gerd Hillebrand, and Dan Suciu. A Query Language and Optimization Techniques for Unstructured Data. SIGMOD, 1996 https://doi.org/10.1145/235968.233368
  9. V. Christophides, S. Abiteboul, S. Cluet, and M. Scholl. From Structured Documents to Novel Query Facilities. SIGMOD, 1994 https://doi.org/10.1145/191843.191901
  10. Walter W. Chang and Hans J. Schek. A Signature Access Method for the Starburst Database System. VLDB, 1989
  11. Chris Faloutsos. Signature files: Design and Performance Comparison of Some Signature Extraction Methods. SIGMOD, 1985 https://doi.org/10.1145/971699.318903
  12. Hwan-Seung Yong, Sukho Lee, and Hyoung-Joo Kim. Applying Signatures for Forward Traversal Query Processing in Object-Oriented Databases. ICDE, 1994 https://doi.org/10.1109/ICDE.1994.283076
  13. Roy Goldman and Jennifer Widom. DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB, 1997
  14. Tova Milo and Dan Suciu. Index Structures Lor Path Expressions. ICDT, 1999
  15. Yannis Papakonstantinou, Hector Garcia-Molina, and Jennifer Widom. Object Exchange Across Heterogeneous Information Sources. ICDE, 1995 https://doi.org/10.1109/ICDE.1995.380386
  16. Jae-Mok Jeong, Sangwon Park, Tae-Sun Chung, and Hyoung-Joo Kim. XWEET: XML DBMS for Web Environment. The First Workshop on Computer Science and Engineering 2000, Seoul, Korea, pages 16-17, June 2000, http://oopsla.snu.ac.kr/xweet/xweet-eng.ps
  17. R. Sacks-Davis, A. Kent, and K. Ramamohanarao. Multikey Access Methods Based on Superimposed Coding Techniques. TODS, 12(4), 1984 https://doi.org/10.1145/32204.32222
  18. Alin Deutsch, Mary Fernandez, and Dan Suciu. Storing Semistructured Data with STORED. SIGMOD, 1999 https://doi.org/10.1145/304182.304220
  19. Daniela Florescu and Donald Kossmann. Storing and Querying XML Data using an RDBMS. Data Engineering Bulletin, 22(3), September 1999
  20. Jayavel Shanmugasundaram, Kristin Tufte, Gang He, Chun Zhang, David DeWitt, and Jeffrey Naughton. Relational Databases for Querying XML Documents: Limitations and Opportunities. VLDB, 1999
  21. Takeyuki Shimura, Masatoshi Yoshikawa, and Shunsuke Uemura. Storage and Retrieval of XML Documents Using Object-Relational Databases. DEXA, 1999
  22. GMD-IPSI. GMD-ISPI XQL Engine. http://xml.darmstadt.gmd.de/xql, 2000
  23. W3C. Document Object Model (DOM). http://www.w3.org/DOM, 2 2000
  24. Peter Linz. An Introduction to Formal Languages and Automata. Houghton Mifflin Company, 1990
  25. Chris Ruemmler and John Wilkes. An Introduction to Disk Drive Modeling. IEEE Computer, 27(3), March 1994 https://doi.org/10.1109/2.268881
  26. IEEE Computer v.27 no.3 An Introduction to Disk Drive Modeling Chris Ruemmler;John Wilkes