Abstract
Traditional content based publish/subscribe (pub/sub) systems allow users to express stateless subscriptions evaluated on individual events. However, many applications such as monitoring RSS streams, stock tickers, or management of RFID data streams require the ability to handle stateful subscriptions. In this paper, we introduce Cayuga, a stateful pub/sub system based on nondeterministic finite state automata (NFA). Cayuga allows users to express subscriptions that span multiple events, and it supports powerful language features such as parameterization and aggregation, which significantly extend the expressive power of standard pub/sub systems. Based on a set of formally defined language operators, the subscription language of Cayuga provides non-ambiguous subscription semantics as well as unique opportunities for optimizations. We experimentally demonstrate that common optimization techniques used in NFA-based systems such as state merging have only limited effectiveness, and we propose novel efficient indexing methods to speed up subscription processing. In a thorough experimental evaluation we show the efficacy of our approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Traderbot financial search engine, http://www.traderbot.com/
Abadi, D.J., Ahmad, Y., Balazinska, M., Çetintemel, U., Cherniack, M., Hwang, J.-H., Lindner, W., Maskey, A., Rasin, A., Ryvkina, E., Tatbul, N., Xing, Y., Zdonik, S.B.: The design of the borealis stream processing engine. In: Proc. CIDR, pp. 277–289 (2005)
Adaikkalavan, R., Chakravarthy, S.: SnoopIB: Interval-based event specification and detection for active databases. In: Kalinichenko, L.A., Manthey, R., Thalheim, B., Wloka, U. (eds.) ADBIS 2003. LNCS, vol. 2798, pp. 190–204. Springer, Heidelberg (2003)
Aguilera, M.K., Strom, R.E., Sturman, D.C., Astley, M., Chandra, T.D.: Matching events in a content-based subscription system. In: Proc. PODC, pp. 53–61 (1999)
Arasu, A., Babcock, B., Babu, S., McAlister, J., Widom, J.: Characterizing memory requirements for queries over continuous data streams. In: Proc. PODS, pp. 221–232 (2002)
Arasu, A., Babu, S., Widom, J.: The CQL continuous query language: Semantic foundations and query execution. Technical report, Stanford University (2003)
Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. In: Proc. PODS, pp. 1–16 (2002)
Carney, D., Çetintemel, U., Cherniack, M., Convey, C., Lee, S., Seidman, G., Stonebraker, M., Tatbul, N., Zdonik, S.: Monitoring streams — a new class of data management applications. In: Proc. VLDB (2002)
Chakravarthy, S., Krishnaprasad, V., Anwar, E., Kim, S.-K.: Composite events for databases: Semantics, contexts and detection. In: Proc. VLDB, pp. 606–617 (1994)
Chan, C.Y., Felber, P., Garofalakis, M.N., Rastogi, R.: Efficient filtering of XML documents with XPath expressions. In: Proc. ICDE, pp. 235–244 (2002)
Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M.J., Hellerstein, J.M., Krishnamurthy, W.S., Madden, S.R., Raman, V., Reiss, F., Shah, M.A.: TelegraphCQ: Continuous dataflow processing for an uncertain world. In: Proc. CIDR (2003)
Demers, A., Gehrke, J., Hong, M., Riedewald, M., White, W.: A general algebra implementation for monitoring event streams. Technical report, Cornell University, http://techreports.library.cornell.edu
Diao, Y., Altinel, M., Franklin, M.J., Zhang, H., Fischer, P.M.: Path sharing and predicate evaluation for high-performance XML filtering. ACM TODS 28(4), 467–516 (2003)
Fabret, F., Jacobsen, H.-A., Llirbat, F., Pereira, J., Ross, K.A., Shasha, D.: Filtering algorithms and implementation for very fast publish/subscribe. In: Proc. SIGMOD, p. 126 (2001)
Galton, A., Augusto, J.C.: Two approaches to event definition. In: Hameurlain, A., Cicchetti, R., Traunmüller, R. (eds.) DEXA 2002. LNCS, vol. 2453, pp. 547–556. Springer, Heidelberg (2002)
Gehani, N.H., Jagadish, H.V., Shmueli, O.: Composite event specification in databases: Model and implementation. In: Proc. VLDB, pp. 327–338 (1992)
Green, T.J., Miklau, G., Onizuka, M., Suciu, D.: Processing XML streams with deterministic automata. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 173–189. Springer, Heidelberg (2003)
Gupta, A.K., Suciu, D.: Stream processing of XPath queries with predicates. In: SIGMOD, pp. 419–430 (2003)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison Wesley, Reading (2000)
Krishnamurthy, S., Franklin, M.J., Hellerstein, J.M., Jacobson, G.: The case for precision sharing. In: Proc. VLDB, pp. 972–986 (2004)
Leung, H., Jacobsen, H.: Efficient matching for state-persistent publish/subscribe systems. In: CASCON 2003: Proceedings of the 2003 conference of the Centre for Advanced Studies Collaborative research, pp. 182–196. IBM Press (2003)
Li, G., Jacobsen, H.: Composite subscriptions in content-based publish/subscribe systems. In: Proc. ACM/IFIP/USENIX International Middleware Conference (2005)
Motakis, I., Zaniolo, C.: Formal semantics for composite temporal events in database rules. Journal of Systems Integration 7(3-4), 291–325 (1997)
Motakis, I., Zaniolo, C.: Temporal aggregation in active database rules. In: Proc. SIGMOD, pp. 440–451 (1997)
Motwani, R., Widom, J., Arasu, A., Babcock, B., Babu, S., Datar, M., Manku, G.S., Olston, C., Rosenstein, J., Varma, R.: Query processing, approximation, and resource management in a data stream management system. In: Proc. CIDR (2003)
Sellis, T.K.: Multiple-query optimization. ACM TODS 13(1), 23–52 (1988)
Sistla, A.P., Wolfson, O.: Temporal conditions and integrity constraints in active database systems. In: Proc. SIGMOD, pp. 269–280 (1995)
Srivastava, U., Widom, J.: Memory-limited execution of windowed stream joins. In: VLDB, pp. 324–335 (2004)
Widom, J., Ceri, S.: Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann Publishers, San Francisco (1996)
Yalamanchi, A., Srinivasan, J., Gawlick, D.: Managing expressions as data in relational database systems. In: Proc. CIDR (2003)
Zimmer, D., Unland, R.: On the semantics of complex events in active database management systems. In: Proc. ICDE, pp. 392–399 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Demers, A., Gehrke, J., Hong, M., Riedewald, M., White, W. (2006). Towards Expressive Publish/Subscribe Systems. In: Ioannidis, Y., et al. Advances in Database Technology - EDBT 2006. EDBT 2006. Lecture Notes in Computer Science, vol 3896. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11687238_38
Download citation
DOI: https://doi.org/10.1007/11687238_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32960-2
Online ISBN: 978-3-540-32961-9
eBook Packages: Computer ScienceComputer Science (R0)