Relational-style XML query

ABSTRACT

We study the problem of querying relational data embedded in XML. Relational data can be represented by various tree structures in XML. However, current XML query methods, such as XPath and XQuery, demand explicit path expressions, and thus it is quite difficult for users to produce correct XML queries in the presence of structural variations.

To solve this problem, we introduce a novel query method that automatically discovers various XML structures derived from relational data. A challenge in implementing our method is to reduce the cost of enumerating all possible tree structures that match the query. We show that the notion of functional dependencies has an important role in generating efficient query schedules that avoid irrelevant tree structures.

Our proposed method, the relational-style XML query, has several advantages over traditional XML data management. These include removing the burden of designing strict tree-pattern schemas, enhancing the descriptions of relational data with XML's rich semantics, and taking advantage of schema evolution capability of XML. In addition, the independence of query statements from the underlying XML structure is advantageous for integrating XML data from several sources. We present extensive experimental results that confirm the scalability and tolerance of our query method for various sizes of XML data containing structural variations.

REFERENCES

• 1: S. Al-Khalifa, H. V. Jagadish, N. Koudas, and J. M. Patel. Structural joins: A primitive for efficient XML query pattern matching. In ICDE, 2002.
• 2: Sihem Amer-Yahia , Laks V. S. Lakshmanan , Shashank Pandit, FleXPath: flexible structure and full-text querying for XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007581]
• 3: M. Arenas and L. Libkin. A normal form for XML documents. In ACM TODS, 2004.
• 4: S. Bergamaschi , S. Castano , M. Vincini, Semantic integration of semistructured and structured data sources, ACM SIGMOD Record, v.28 n.1, p.54-59, March 1999 [doi>10.1145/309844.309897]
• 5: S. Boag, D. Chamberlin, M. F. Fernandez, D. Floresch, J. Robie, and J. Simeon. XQuery 1.0: An XML query language - W3C working draft, November 2003. http://www.w3.org/TR/xquery.
• 6: T. Bray, J. Paoli, C. M. Sperberg-McQueen, and E. Maler. Extensible markup language (XML) 1.0 (second edition), October 2000. http://www.w3.org/TR/REC-xml.
• 7: Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Keys for XML, Proceedings of the 10th international conference on World Wide Web, p.201-210, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371984]
• 8: J. Clark and S. DeRose. XML path language (XPath) version 1.0, November 1999. http://www.w3.org/TR/xpath.
• 9: Extensible HyperText markup language (XHTML) 1.0 (second edition), January 2000. http://www.w3.org/TR/xhtml.
• 10: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 11: H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava , Keith Thompson, TAX: A Tree Algebra for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.149-164, September 08-10, 2001
• 12: H. V. Jagadish , Laks V. S. Lakshmanan , Monica Scannapieco , Divesh Srivastava , Nuwee Wiwatwattana, Colorful XML: one hierarchy isn't enough, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007598]
• 13: Mong-Li Lee , Tok Wang Ling , Wai Lup Low, Designing Functional Dependencies for XML, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.124-141, March 25-27, 2002
• 14: 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
• 15: Yunyao Li , Cong Yu , H. V. Jagadish, Schema-free XQuery, Proceedings of the Thirtieth international conference on Very large data bases, p.72-83, August 31-September 03, 2004, Toronto, Canada
• 16: T. H. Merrett, Aldat: A retrospective on a work in progress, Information Systems, v.32 n.4, p.505-544, June, 2007 [doi>10.1016/j.is.2006.07.002]
• 17: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Higher Education, 2000
• 18: RelaxNG. http://relaxng.org.
• 19: T. L. Saito and S. Morishita. Amoeba join: Overcoming structural fluctuations of XML data. In WebDB, 2006.
• 20: SAX: The simple API for XML. http://www.megginson.com/sax/.
• 21: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 22: Sleepycat Software. BerkeleyDB. http://www.sleepycat.com/.
• 23: Z. Vagena, L. S. Colby, F. O¨ zcan, A. Balmin, and Q. Li. On the effectiveness of flexible querying heuristics for XML data. In XSym, 2007.
• 24: Millist W. Vincent , Jixue Liu , Chengfei Liu, Strong functional dependencies and their application to normal forms in XML, ACM Transactions on Database Systems (TODS), v.29 n.3, p.445-462, September 2004 [doi>10.1145/1016028.1016029]
• 25: XML schema. http://www.w3.org/XML/Schema.
• 26: Melanie Weis , Felix Naumann, DogmatiX tracks down duplicates in XML, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066207]
• 27: Yu Xu , Yannis Papakonstantinou, Efficient keyword search for smallest LCAs in XML databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066217]
• 28: Cong Yu , H. V. Jagadish, Efficient discovery of XML data redundancies, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Management

Keywords:
amoeba join, functional dependency, relational query, xml