Satisfiability and relevance for queries over active documents

ABSTRACT

ManyWeb applications are based on dynamic interactions between Web components exchanging flows of information. Such a situation arises for instance in mashup systems [22] or when monitoring distributed autonomous systems [6]. This is a challenging problem that has generated recently a lot of attention; see Web 2.0 [38]. For capturing interactions between Web components, we use active documents interacting with the rest of the world via streams of updates. Their input streams specify updates to the document (in the spirit of RSS feeds), whereas their output streams are defined by queries on the document. In most of the paper, the focus is on input streams where the updates are only insertions, although we do consider also deletions.

We introduce and study two fundamental concepts in this setting, namely, satisfiability and relevance. Some fact is satisfiable for an active document and a query if it has a chance to be in the result of the query in some future state. Given an active document and a query, a call in the document is relevant if the data brought by this call has a chance to impact the answer to the query. We analyze the complexity of computing satisfiability in our core model (insertions only) and for extensions (e.g., with deletions). We also analyze the complexity of computing relevance in the core model.

REFERENCES

• 1: 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]
• 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 , 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]
• 4: S. Abiteboul, P. Bourhis, and B. Marinoiu. Satifiability and relevance for queries over active documents (full version). ftp://ftp.inria.fr/INRIA/Projects/gemo/gemo/GemoReport-10019.pdf.
• 5: Serge Abiteboul , Pierre Bourhis , Bogdan Marinoiu, Efficient maintenance techniques for views over active documents, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516483]
• 6: 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]
• 7: Serge Abiteboul , Bogdan Marinoiu , Pierre Bourhis, Distributed Monitoring of Peer-to-Peer Systems, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1572-1575, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497624]
• 8: Serge Abiteboul , Luc Segoufin , Victor Vianu, Representing and querying XML with incomplete information, ACM Transactions on Database Systems (TODS), v.31 n.1, p.208-254, March 2006 [doi>10.1145/1132863.1132869]
• 9: Serge Abiteboul , Luc Segoufin , Victor Vianu, Static analysis of active XML systems, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376948]
• 10: Active XML. http://activexml.net.
• 11: Catriel Beeri , Raghu Ramakrishnan, On the power of magic, Journal of Logic Programming, v.10 n.3-4, p.255-299, April/May 1991 [doi>10.1016/0743-1066(91)90038-Q]
• 12: Michael Benedikt , Wenfei Fan , Floris Geerts, XPath satisfiability in the presence of DTDs, 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.1065172]
• 13: H. Björklund, W. Martens, and T. Schwentick. Conjunctive query containment over trees. In DBPL, pages 66--80, 2007.
• 14: Henrik Björklund , Wim Martens , Thomas Schwentick, Optimizing Conjunctive Queries over Trees Using Schema Information, Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, August 25-29, 2008, Toruń, Poland [doi>10.1007/978-3-540-85238-4_10]
• 15: José A. Blakeley , Neil Coburn , Per-Åke Larson, Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates, Proceedings of the 12th International Conference on Very Large Data Bases, p.457-466, August 25-28, 1986
• 16: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, ACM SIGMOD Record, v.15 n.2, p.61-71, June 1986
• 17: Andrea Cali , Davide Martinenghi, Querying Data under Access Limitations, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.50-59, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497413]
• 18: H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, 1997. release October, 1rst 2002.
• 19: Claire David, Complexity of Data Tree Patterns over XML Documents, Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, August 25-29, 2008, Toruń, Poland [doi>10.1007/978-3-540-85238-4_22]
• 20: Y. Diao, P. M. Fischer, M. J. Franklin, and R. To. Yfilter: Efficient and scalable filtering of XML documents. In ICDE, pages 341--, 2002.
• 21: DTD. http://www.w3.org/tr/rec-xml/#dt-doctype.
• 22: 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
• 23: A. Finkel , Ph. Schnoebelen, Well-structured transition systems everywhere!, Theoretical Computer Science, v.256 n.1-2, p.63-92, April 6, 2001 [doi>10.1016/S0304-3975(00)00102-X]
• 24: Blaise Genest , Anca Muscholl , Olivier Serre , Marc Zeitoun, Tree Pattern Rewriting Systems, Proceedings of the 6th International Symposium on Automated Technology for Verification and Analysis, October 20-23, 2008, Seoul, Korea [doi>10.1007/978-3-540-88387-6_29]
• 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: Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems (TODS), v.30 n.2, p.444-491, June 2005 [doi>10.1145/1071610.1071614]
• 27: G. Grahne, Problem of Incomplete Information in Relational Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 28: Tomasz Imielinski , W. Lipski, Jr., The relational model of data and cylindrical algebras, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588139]
• 29: C. A. K. and V. M. Y. The implication problem for functional and inclusion dependencies is undecidable. SIAM journal on computing, 14(3):pp. 671--677, 1985.
• 30: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• 31: 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]
• 32: Alon Y. Levy, Obtaining Complete Answers from Incomplete Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.402-412, September 03-06, 1996
• 33: Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
• 34: A.-T. Ma, Z.-X. Hao, and Y. Zhu. Checking satisfiability of tree pattern queries for active xml documents. In INFOCOMP, pages 11--18, 2008.
• 35: 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]
• 36: A. Muscholl, T. Schwentick, and L. Segoufin. Active context-free games. In STACS, pages 452--464, 2004.
• 37: Helmut Seidl , Thomas Schwentick , Anca Muscholl, Numerical document queries, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773169]
• 38: What Is Web 2.0. http://www.oreilly.com/.
• 39: WSDL. http://www.w3.org/tr/wsdl.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

General Terms:
Algorithms, Languages

Keywords:
active XML, query satisfiability, relevance