Improving query performance on XML documents: a workload-driven design approach

ABSTRACT

As XML has emerged as a data representation format and as great quantities of data have been stored in the XML format, XML document design has become an important and evident issue in several application contexts. Methodologies based on conceptual modeling are being tightly applied for designing XML documents. However, the conversion of a conceptual schema to an XML schema is a complex process. In many cases, conceptual relationships cannot be represented in a hierarchy so that they have to be represented by reference relationships in the XML schema. The problem is that reference relationships generate a disconnected XML structure and, consequently, produce an overhead cost for query processing on XML documents.

This paper presents a design approach for generating XML schemas from conceptual schemas considering the expected workload of the XML applications. Query workload is used to produce XML schemas which minimize the impact of the reference relationships on query performance. We evaluate our approach through a case study where a set of XML documents are redesigned by our methodology. The results demonstrate that query performance is improved in terms of the number of accesses generated by the queries on the XML documents designed by our approach.

REFERENCES

• 1: Carlo Batini , Stefano Ceri , Shamkant B. Navathe, Conceptual database design: an Entity-relationship approach, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 2: S. Bechhofer, F. Harmelen, and J. Hendler. Owl web ontology language reference. 2002.
• 3: L. Bird, A. Goodchild, and T. A. Halpin. Object role modeling and xml-schema. In International Conference on Conceptual Modeling, pages 661--705. Springer Heidelberg, 2000.
• 4: T. Bray and J. P. et. al. Extensible markup language (xml) 1.0 w3c recommendation, 2000.
• 5: M. Choi, J. Lim, and K. Joo. Developing a unified design methodology based on extended entity-relationship model for xml. In International Conference on Computational Science, pages 920--929. Springer Heidelberg, 2003.
• 6: R. Conrad, D. Scheffner, and J. C. Freytag. Xml conceptual modeling using xml. In International Conference on Conceptual Modeling, pages 558--571. Springer, 2000.
• 7: R. Elmasri , J. Weeldreyer , A. Hevner, The category concept: an extension to the entity-relationship model, Data & Knowledge Engineering, v.1 n.1, p.75-116, April 1985 [doi>10.1016/0169-023X(85)90027-8]
• 8: J. Fong and A. F. et. al. Translating relational schema with constraints into xml schema. In International Journal of Software Engineering and Knowledge Engineering, number 16, pages 201--244, 2006.
• 9: H. V. Jagadish , S. Al-Khalifa , A. Chapman , L. V. S. Lakshmanan , A. Nierman , S. Paparizos , J. M. Patel , D. Srivastava , N. Wiwatwattana , Y. Wu , C. Yu, TIMBER: A native XML database, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.274-291, December 2002 [doi>10.1007/s00778-002-0081-x]
• 10: C. Liu and J. Li. Designing quality xml schemas from e-r diagrams. In Advances in Web-Age Information Management, pages 508--519. Springer Heidelberg, 2006.
• 11: R. S. Mello and C. A. Heuser. Binxs: A process for integration of xml schemata. In International Conference on Advanced Information Systems Engineering, pages 151--166. Springer Heidelberg, 2005.
• 12: Wai Yin Mok , David W. Embley, Generating Compact Redundancy-Free XML Documents from Conceptual-Model Hypergraphs, IEEE Transactions on Knowledge and Data Engineering, v.18 n.8, p.1082-1096, August 2006 [doi>10.1109/TKDE.2006.125]
• 13: P. Pigozzo and E. Quintarelli. An algorithm for generating xml schemas from er schemas. In Italian Symposium on Advanced Database Systems, pages 192--199, 2005.
• 14: Nicholas Routledge , Linda Bird , Andrew Goodchild, UML and XML schema, Proceedings of the 13th Australasian database conference, p.157-166, January 01, 2002, Melbourne, Victoria, Australia
• 15: Harald Schöning, Tamino - A DBMS designed for XML, Proceedings of the 17th International Conference on Data Engineering, p.149-154, April 02-06, 2001
• 16: Rebeca Schroeder , Ronaldo dos Santos Mello, Conversion of generalization hierarchies and union types from extended entity-relationship model to an XML logical model, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1363926]
• 17: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 18: H. Thompson and D. B. et. al. Xml schema part 1: Structures w3c recommendation, 2004.
• 19: Nuwee Wiwatwattana , H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava, Making Designer Schemas with Colors, Proceedings of the 22nd International Conference on Data Engineering, p.15, April 03-07, 2006 [doi>10.1109/ICDE.2006.88]
• 20: Z. Xu and Z. G. et. al. Dynamic tuning of xml storage schema in vxmlr. In International Database Engineering and Applications Symposium, pages 76--86. IEEE, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Algorithms, Design, Performance

Keywords:
XML schemas, conceptual schemas, query performance