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: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 3: Serge Abiteboul , Zoë Abrams , Stefan Haar , Tova Milo, Diagnosis of asynchronous discrete event systems: datalog to the rescue!, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065214]
• 4: Serge Abiteboul , Omar Benjelloun , Bogdan Cautis , Ioana Manolescu , Tova Milo , Nicoleta Preda, Lazy query evaluation for Active XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007596]
• 5: Serge Abiteboul , Omar Benjelloun , Tova Milo, The Active XML project: an overview, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1019-1040, August 2008 [doi>10.1007/s00778-007-0049-y]
• 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 , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 8: Serge Abiteboul , Haim Kaplan , Tova Milo, Compact labeling schemes for ancestor queries, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 07-09, 2001, Washington, D.C., United States
• 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 , Bogdan Marinoiu, Distributed monitoring of peer to peer systems, Proceedings of the 9th annual ACM international workshop on Web information and data management, November 09-09, 2007, Lisbon, Portugal [doi>10.1145/1316902.1316910]
• 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 , Janet L. Wiener, Incremental Maintenance for Materialized Views over Semistructured Data, Proceedings of the 24rd International Conference on Very Large Data Bases, p.38-49, August 24-27, 1998
• 14: Active XML, http://activexml.net.
• 15: I. Balbin , K. Ramamohanarao, A generalization of the differential approach to recursive query evaluation, Journal of Logic Programming, v.4 n.3, p.259-262, Sept. 1987 [doi>10.1016/0743-1066(87)90004-5]
• 16: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• 17: Peter Buneman , Adriane Chapman , James Cheney, Provenance management in curated databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142534]
• 18: Stefano Ceri , Jennifer Widom, Deriving incremental production rules for deductive data, Information Systems, v.19 n.6, p.467-490, Sept. 1994 [doi>10.1016/0306-4379(94)90002-7]
• 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: Rob Ennals , David Gay, User-friendly functional programming for web mashups, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
• 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 , Geetika Agrawal, The BEA/XQRL streaming XQuery processor, Proceedings of the 29th international conference on Very large data bases, p.997-1008, September 09-12, 2003, Berlin, Germany
• 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 , Christoph Koch, Monadic Queries over Tree-Structured Data, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.189-202, July 22-25, 2002
• 26: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 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 , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 29: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• 30: Roman Kapuscinski , Rachel Q. Zhang , Paul Carbonneau , Robert Moore , Bill Reeves, Inventory Decisions in Dell's Supply Chain, Interfaces, v.34 n.3, p.191-205, June 2004 [doi>10.1287/inte.1030.0068]
• 31: Christoph Koch , Stefanie Scherzinger , Nicole Schweikardt , Bernhard Stegmaier, FluXQuery: an optimizing XQuery processor for streaming XML data, Proceedings of the Thirtieth international conference on Very large data bases, p.1309-1312, August 31-September 03, 2004, Toronto, Canada
• 32: Richard Kuntschke , Bernhard Stegmaier , Alfons Kemper , Angelika Reiser, StreamGlobe: processing and sharing data streams in grid-based P2P infrastructures, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 33: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 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: W. Nejdl , S. Ceri , Gio Wiederhold, Evaluating Recursive Queries in Distributed Databases, IEEE Transactions on Knowledge and Data Engineering, v.5 n.1, p.104-121, February 1993 [doi>10.1109/69.204095]
• 36: Patrick O'Neil , Elizabeth O'Neil , Shankar Pal , Istvan Cseri , Gideon Schaller , Nigel Westbury, ORDPATHs: insert-friendly XML node labels, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007686]
• 37: Makoto Onizuka , Fong Yee Chan , Ryusuke Michigami , Takashi Honishi, Incremental maintenance for materialized XPath/XSLT views, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060843]
• 38: Royi Ronen , Oded Shmueli, Evaluation of datalog extended with an XPath predicate, Proceedings of the 9th annual ACM international workshop on Web information and data management, November 09-09, 2007, Lisbon, Portugal [doi>10.1145/1316902.1316905]
• 39: Arsany Sawires , Junichi Tatemura , Oliver Po , Divyakant Agrawal , K. SelÇuk Candan, Incremental maintenance of path-expression views, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066208]
• 40: Bernhard Stegmaier , Richard Kuntschke , Alfons Kemper, StreamGlobe: adaptive query processing and optimization in streaming P2P environments, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052214]
• 41: L. Vielle, Recursive query processing: the power of logic, Theoretical Computer Science, v.69 n.1, p.1-53, Dec. 5, 1989 [doi>10.1016/0304-3975(89)90088-1]
• 42: What Is Web 2.0, http://www.oreilly.com/.
• 43: WSDL, http://www.w3.org/tr/wsdl.