Translating XSLT programs to Efficient SQL queries

ABSTRACT

We present an algorithm for translating XSLT programs into SQL. Our context is that of virtual XML publishing, in which a single XML view is defined from a relational database, and subsequently queried with XSLT programs. Each XSLT program is translated into a single SQL query and run entirely in the database engine. Our translation works for a large fragment of XSLT, which we define, that includes descendant/ancestor axis, recursive templates, modes, parameters, and aggregates. We put considerable effort in generating correct and efficient SQL queries and describe several optimization techniques to achieve this efficiency. We have tested our system on all 22 SQL queries of the TPC-H database benchmark which we represented in XSLT and then translated back to SQL using our translator.

REFERENCES

• 1: Peter Buneman , Mary Fernandez , Dan Suciu, UnQL: a query language and algebra for semistructured data based on structural recursion, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.76-110, March 2000 [doi>10.1007/s007780050084]
• 2: M. Carey, D. Florescu, Z. Ives, Y. Lu, J. Shanmugasundaram, E. Shekita, and S. subramanian. XPERANTO: publishing object-relational data as XML. In Proceedings of WebDB, Dallas, TX, May 2000.
• 3: D. Chamberlin, J. Clark, D. Florescu, J. Robie, J. Siméon, and M. Stefanescu. XQuery 1.0: An XML Query LanguageXML Path Language (XPath). Technical report, W3C, June 2001.
• 4: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 5: J. Clark and S. DeRose. XML Path Language (XPath). Technical report, W3C, November 1999.
• 6: T. P. Council. TPC Benchmark H (Decision Support). Technical report, June 1999.
• 7: 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
• 8: Mary Fernandez , Atsuyuki Morishima , Dan Suciu, Efficient evaluation of XML middle-ware queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.103-114, May 21-24, 2001, Santa Barbara, California, United States
• 9: Mary F. Fernandez , Dan Suciu, Optimizing Regular Path Expressions Using Graph Schemas, Proceedings of the Fourteenth International Conference on Data Engineering, p.14-23, February 23-27, 1998
• 10: Mary Fernández , Wang-Chiew Tan , Dan Suciu, SilkRoute: trading between relations and XML, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.723-745, June 2000, Amsterdam, The Netherlands
• 11: Java Compiler Compiler (JavaCC) - The Java Parser Generator. http://www.webgain.com/products/java_cc/, 2002.
• 12: S. Muench and M. Scardina. XSLT Requirements. Technical report, W3C, February 2001.
• 13: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, ACM SIGMOD Record, v.21 n.2, p.39-48, June 1, 1992
• 14: Jayavel Shanmugasundaram , Jerry Kiernan , Eugene J. Shekita , Catalina Fan , John Funderburk, Querying XML Views of Relational Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.261-270, September 11-14, 2001
• 15: Jayavel Shanmugasundaram , Eugene J. Shekita , Rimon Barr , Michael J. Carey , Bruce G. Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently Publishing Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.65-76, September 10-14, 2000
• 16: Dan Suciu, On database theory and XML, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603874]
• 17: Jeffrey D. Ullman , Jennifer Widom, A first course in database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

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

General Terms:
Algorithms, Design, Languages

Keywords:
SQL, XML, XSLT, query optimization, translation, virtual view