Lazy query evaluation for Active XML

ABSTRACT

In this paper, we study query evaluation on Active XML documents (AXML for short), a new generation of XML documents that has recently gained popularity. AXML documents are XML documents whose content is given partly extensionally, by explicit data elements, and partly intensionally, by embedded calls to Web services, which can be invoked to generate data.A major challenge in the efficient evaluation of queries over such documents is to detect which calls may bring data that is relevant for the query execution, and to avoid the materialization of irrelevant information. The problem is intricate, as service calls may be embedded anywhere in the document, and service invocations possibly return data containing calls to new services. Hence, the detection of relevant calls becomes a continuous process. Also, a good analysis must take the service signatures into consideration.We formalize the problem, and provide algorithms to solve it. We also present an implementation that is compliant with XML and Web services standards, and is used as part of the ActiveXML system. Finally, we experimentally measure the performance gains obtained by a careful filtering of the service calls to be triggered.

REFERENCES

• 1: S. Abiteboul, O. Benjelloun, I. Manolescu, T. Milo, and R. Weber. Active XML: Peer-to-peer data and web services integration (demo). In Proc. of VLDB, 2002.
• 2: Serge Abiteboul , Omar Benjelloun , Tova Milo, Positive active XML, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055564]
• 3: Serge Abiteboul , Angela Bonifati , Grégory Cobéna , Ioana Manolescu , Tova Milo, Dynamic XML documents with distribution and replication, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872821]
• 4: S. Abiteboul and T. Milo. Web Services meet Datalog. Technical report, INRIA, 2004.
• 5: Denilson Barbosa , Alberto Mendelzon , John Keenleyside , Kelly Lyons, ToXgene: a template-based data generator for XML, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564769]
• 6: H. P. Barendregt, Functional programming and lambda calculus, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 7: N. Bruno, L. Gravano, N. Koudas, and D. Srivastava. Navigation- vs. index-based XML multi-query processing. In Proc. of ICDE, 2003.
• 8: 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
• 9: 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]
• 10: 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]
• 11: 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
• 12: G. Gottlob and C. Koch. Efficient algorithms for processing XPath queries. In Proc. of VLDB, 2002.
• 13: Himanshu Gupta, Selection of Views to Materialize in a Data Warehouse, Proceedings of the 6th International Conference on Database Theory, p.98-112, January 08-10, 1997
• 14: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 15: Alon Y. Halevy , Zachary G. Ives , Peter Mork , Igor Tatarinov, Piazza: data management infrastructure for semantic web applications, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775231]
• 16: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 17: Jelly: Executable XML. http://jakarta.apache.org/commons/sandbox/jelly.
• 18: Macromedia Coldfusion MX. http://www.macromedia.com/software/coldfusion/.
• 19: Ioana Manolescu , Daniela Florescu , Donald Kossmann, Answering XML Queries on Heterogeneous Data Sources, Proceedings of the 27th International Conference on Very Large Data Bases, p.241-250, September 11-14, 2001
• 20: Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543623]
• 21: Tova Milo , Serge Abiteboul , Bernd Amann , Omar Benjelloun , Fred Dang Ngoc, Exchanging intensional XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872793]
• 22: Tova Milo , Dan Suciu, Type inference for queries on semistructured data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.215-226, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303998]
• 23: Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.455-466, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 24: M. Petropoulos, A. Deutsch, and Y. Papakonstantinou. Query set specification language (QSSL). In Proc. of WebDB, 2003.
• 25: J. Powell and T. Maxwell. Integrating Office XP Smart Tags with the Microsoft. NET Platform. http://msdn.microsoft.com.
• 26: Universal Description, Discovery, and Integration of Business for the Web (UDDI). http://www.uddi.org.
• 27: L. Vieille. Recursive axioms in deductive databases: The query-subquery approach. In Proc. 1st Int. Conf. on Expert Database Systems, 1986.
• 28: The World Wide Web Consortium. http://www.w3.org/.