Implementing a scalable XML publish/subscribe system using relational database systems

ABSTRACT

An XML publish/subscribe system needs to match many XPath queries (subscriptions) over published XML documents. The performance and scalability of the matching algorithm is essential for the system when the number of XPath subscriptions is large. Earlier solutions to this problem usually built large finite state automata for all the XPath subscriptions in memory. The scalability of this approach is limited by the amount of available physical memory. In this paper, we propose an implementation that uses a relational database as the matching engine. The heavy lifting part of evaluating a large number of subscriptions is done inside a relational database using indices and joins. We described several different implementation strategies and presented a performance evaluation. The system shows very good performance and scalability in our experiments, handling millions of subscriptions with moderate amount of physical memory.

REFERENCES

• 1: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 2: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 3: Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993 [doi>10.1145/163298.163303]
• 4: Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
• 5: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 6: Design and Evaluation of Alternative Selection Placement Strategies in Optimizing Continuous Queries, Proceedings of the 18th International Conference on Data Engineering, p.345, February 26-March 01, 2002
• 7: YFilter: Efficient and Scalable Filtering of XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.341, February 26-March 01, 2002
• 8: 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
• 9: Ashish Kumar Gupta , Dan Suciu, Stream processing of XPath queries with predicates, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872809]
• 10: Chris Carnes , J. B. Park , Albert Vernon, Scalable Trigger Processing, Proceedings of the 15th International Conference on Data Engineering, p.266, March 23-26, 1999
• 11: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, ACM SIGOPS Operating Systems Review, v.27 n.5, p.58-68, Dec. 1993
• 12: Feng Peng , Sudarshan S. Chawathe, XPath queries on streaming data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872810]
• 13: David Powell, Group communication, Communications of the ACM, v.39 n.4, p.50-53, April 1996 [doi>10.1145/227210.227225]
• 14: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 15: P. Seshadri, Building Notification Services with Microsoft SQL Server. In Proceedings of SIGMOD 2003
• 16: Sun Microsystem Inc. Java Message Service (JMS) specification. http://java.sun.com/products/jms
• 17: Sun Microsystem Inc. Java 2 Enterprise Edition (J2EE) specification. http://java.sun.com/j2ee/1.4/docs/
• 18: Yu-Wang Wang , Eric N. Hanson, A Performance Comparison of the Rete and TREAT Algorithms for Testing Database Rule Conditions, Proceedings of the Eighth International Conference on Data Engineering, p.88-97, February 03-07, 1992
• 19: A. Yalamanchi, J. Srinivasan, D. Gawlick. Managing Expressions as Data in Relational Database Systems. In Proceedings of CIDR 2003.
• 20: XML Path Language (XPath) 1.0. http://www.w3.org/TR/xpath
• 21: XQuery 1.0: An XML Query Language. http://www.w3.org/XML/XQuery
• 22: H. Zeller. Non-Stop SQL/MX Publish/Subscribe: Continuous Data Streams in Transaction Processing. In Proceedings of SIGMOD 2003.