Efficient maintenance techniques for views over active documents

ABSTRACT

Many Web applications are based on dynamic interactions between Web components exchanging flows of information. Such a situation arises for instance in mashup systems or when monitoring distributed autonomous systems. Our work is in this challenging context that has generated recently a lot of attention; see Web 2.0. We introduce the axlog formal model for capturing such interactions and show how this model can be supported efficiently. The central component is the axlog widget defined by one tree-pattern query or more, over an active document (in the Active XML style) that includes some input streams of updates. A widget generates a stream of updates for each query, the updates that are needed to maintain the view corresponding to the query. We exploit an array of known technologies: datalog optimization techniques such as Differential or MagicSet, constraint query languages, and efficient XML filtering (YFilter). The novel optimization technique we propose is based on fundamental new notions: a relevance (different than that of MagicSet), satisfiability and provenance for active documents. We briefly discuss an implementation of an axlog engine, an application that we used to test the approach, and results of experiments.

References

1. D. J. Abadi, Y. Ahmad, M. Balazinska, U. Çetintemel, M. Cherniack, J.-H. Hwang, W. Lindner, A. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. B. Zdonik. The design of the Borealis stream processing engine. In CIDR, 2005.
2. D. J. Abadi, D. Carney, U. Çetintemel, M. Cherniack, C. Convey, S. Lee, M. Stonebraker, N. Tatbul, and S. B. Zdonik. Aurora: a new model and architecture for data stream management. VLDB J., 12(2), 2003.
3. Serge Abiteboul, Zoë Abrams, Stefan Haar, and Tova Milo. Diagnosis of asynchronous discrete event systems: datalog to the rescue! In PODS, 2005.
4. Serge Abiteboul, Omar Benjelloun, Bogdan Cautis, Ioana Manolescu, Tova Milo, and Nicoleta Preda. Lazy query evaluation for Active XML. In SIGMOD Conference, pages 227--238, 2004.
5. Serge Abiteboul, Omar Benjelloun, and Tova Milo. The Active XML project: an overview. VLDB J., accepted for publication, 2008.
6. Serge Abiteboul, Pierre Bourhis, and Bogdan Marinoiu. Satisfiability and Relevance for Queries over Active Documents. http://www-rocq.inria.fr/~marinoiu/satisfiability.pdf.
7. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.
8. Serge Abiteboul, Haim Kaplan, and Tova Milo. Compact labeling schemes for ancestor queries. In SODA, pages 547--556, 2001.
9. Serge Abiteboul, Ioana Manolescu, and Emanuel Taropa. A framework for distributed XML data management. In EDBT, pages 1049--1058, 2006.
10. Serge Abiteboul, Ioana Manolescu, and Spyros Zoupanos. Optimax: efficient support for data-intensive mash-ups. In ICDE, pages 1564--1567, 2008.
11. Serge Abiteboul and Bogdan Marinoiu. Distributed Monitoring of Peer to Peer Systems. In Workshop On Web Information And Data Management, pages 41--48, 2007.
12. Serge Abiteboul, Bogdan Marinoiu, and Pierre Bourhis. Distributed Monitoring of Peer to Peer Systems (demo). In ICDE, 2008.
13. Serge Abiteboul, Jason McHugh, Michael Rys, Vasilis Vassalos, and Janet L. Wiener. Incremental maintenance for materialized views over semistructured data. In VLDB, pages 38--49, 1998.
14. Active XML, http://activexml.net.
15. Isaac Balbin and Kotagiri Ramamohanarao. A generalization of the differential approach to recursive query evaluation. J. Log. Program., 4(3):259--262, 1987.
16. Catriel Beeri and Raghu Ramakrishnan. On the Power of Magic. In PODS, pages 269--284, 1987.
17. Peter Buneman, Adriane Chapman, and James Cheney. Provenance management in curated databases. In ACM SIGMOD Conference on Management of data, 2006.
18. Stefano Ceri and Jennifer Widom. Deriving incremental production rules for deductive data. Inf. Syst., 19(6):467--490, 1994.
19. Yanlei Diao, Peter M. Fischer, Michael J. Franklin, and Raymond To. Yfilter: Efficient and scalable filtering of XML documents. In ICDE, pages 341--, 2002.
20. Robert Ennals and David Gay. User-friendly functional programming for Web mashups. In ICFP, pages 223--234, 2007.
21. eXist, http://exist.sourceforge.net/.
22. Mary F. Fernández, Philippe Michiels, Jérôme Siméon, and Michael Stark. XQuery streaming 'a la carte. In ICDE, pages 256--265, 2007.
23. Daniela Florescu, Chris Hillery, Donald Kossmann, Paul Lucas, Fabio Riccardi, Till Westmann, Michael J. Carey, Arvind Sundararajan, and Geetika Agrawal. The BEA/XQRL Streaming XQuery Processor. In VLDB, pages 997--1008, 2003.
24. J. Nathan Foster, Ravi Konuru, Jérôme Siméon, and Lionel Villard. An algebraic approach to view maintenance for XQuery. In PLAN-X, 2008.
25. Georg Gottlob and Christoph Koch. Monadic queries over tree-structured data. In LICS, pages 189--202, 2002.
26. Todd J. Green, Gerome Miklau, Makoto Onizuka, and Dan Suciu. Processing XML streams with deterministic automata. In ICDT, 2003.
27. Ashish Gupta and Inderpal Singh Mumick. Maintenance of materialized views: Problems, techniques, and applications. IEEE Data Eng. Bull., 18(2):3--18, 1995.
28. Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In SIGMOD Conference, pages 157--166, 1993.
29. Paris C. Kanellakis, Gabriel M. Kuper, and Peter Z. Revesz. Constraint query languages. In PODS, pages 299--313, 1990.
30. Roman Kapuscinski, Rachel Q. Zhang, Paul Carbonneau, Robert Moore, and Bill Reeves. Inventory decisions in Dell's supply chain. Interfaces, 34(3):191--205, 2004.
31. Christoph Koch, Stefanie Scherzinger, Nicole Schweikardt, and Bernhard Stegmaier. FluXQuery: An Optimizing XQuery Processor for Streaming XML Data. In VLDB, pages 1309--1312, 2004.
32. Richard Kuntschke, Bernhard Stegmaier, Alfons Kemper, and Angelika Reiser. Streamglobe: Processing and sharing Data Streams in Grid-Based P2P infrastructures. In VLDB, 2005.
33. Gerome Miklau and Dan Suciu. Containment and equivalence for a fragment of XPath. J. ACM, 51(1):2--45, 2004.
34. R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Singh Manku, C. Olston, J. Rosenstein, and R. Varma. Query processing, approximation, and resource management in a data stream management system. In CIDR, 2003.
35. Wolfgang Nejdl, Stefano Ceri, and Gio Wiederhold. Evaluating recursive queries in distributed databases. IEEE Trans. Knowl. Data Eng., 5(1):104--121, 1993.
36. Patrick E. O'Neil, Elizabeth J. O'Neil, Shankar Pal, Istvan Cseri, Gideon Schaller, and Nigel Westbury. ORDPATHs: Insert-Friendly XML Node Labels. In SIGMOD Conference, pages 903--908, 2004.
37. Makoto Onizuka, Fong Yee Chan, Ryusuke Michigami, and Takashi Honishi. Incremental maintenance for materialized XPath/XSLT views. In WWW, pages 671--681, 2005.
38. Royi Ronen and Oded Shmueli. Evaluation of datalog extended with an XPath predicate. In WIDM, pages 9--16, 2007.
39. Arsany Sawires, Jun'ichi Tatemura, Oliver Po, Divyakant Agrawal, and K. Selçuk Candan. Incremental maintenance of path expression views. In SIGMOD Conference, pages 443--454, 2005.
40. Bernhard Stegmaier, Richard Kuntscke, and Alfons Kemper. Streamglobe: adaptive query processing and optimization in streaming P2P environments. In ACM International Conference Proceeding Series; Vol. 72, 2004.
41. L. Vieille. Recursive query processing: the power of logic. Theor. Comput. Sci., 69(1):1--53, 1989.
42. What Is Web 2.0, http://www.oreilly.com/.
43. WSDL, http://www.w3.org/tr/wsdl.