What is "next" in event processing?

ABSTRACT

Event processing systems have wide applications ranging from managing events from RFID readers to monitoring RSS feeds. Consequently, there exists much work on them in the literature. The prevalent use of these systems is on-line recognition of patterns that are sequences of correlated events in event streams. Query semantics and implementation efficiency are inherently determined by the underlying temporal model: how events are sequenced (what is the "next" event), and how the time stamp of an event is represented. Many competing temporal models for event systems have been proposed, with no consensus on which approach is best.

We take a foundational approach to this problem. We create a formal framework and present event system design choices as axioms. The axioms are grouped into standard axioms and desirable axioms. Standard axioms are common to the design of all event systems. Desirable axioms are not always satisfied, but are useful for achieving high performance. Given these axioms, we prove several important results. First, we show that there is a unique model up to isomorphism that satisfies the standard axioms and supports associativity, so our axioms are a sound and complete axiomatization of associative time stamps in eventsystems. This model requires time stamps with unbounded representations. We present a slightly weakened version of associativity that permits a temporal model with bounded representations. We show that adding the boundedness condition also results in a unique model, so again our axiomatization is sound and complete. We believe this model is ideally suited to be the standard temporal model for complex event processing.

REFERENCES

• 1: Complex event processing. www.complexevents.com.
• 2: R. Adaikkalavan and S. Chakravarthy. SnoopIB: Interval-based event specification and detection for active databases. In Proc. ADBIS, pages 190--204, 2003.
• 3: James F. Allen , George Ferguson, Actions and Events in Interval Temporal Logic, University of Rochester, Rochester, NY, 1994
• 4: Mark Bickford and Robert Constable. A logic of events. Technical Report 2003-1893, Cornell University, 2003.
• 5: Michael H. Böhlen , R. Busatto , Christian S. Jensen, Point-Versus Interval-Based Temporal Data Models, Proceedings of the Fourteenth International Conference on Data Engineering, p.192-200, February 23-27, 1998
• 6: Sharma Chakravarthy , V. Krishnaprasad , Eman Anwar , S.-K. Kim, Composite Events for Active Databases: Semantics, Contexts and Detection, Proceedings of the 20th International Conference on Very Large Data Bases, p.606-617, September 12-15, 1994
• 7: A. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. White. Towards expressive publish/subscribe systems. In Proc. EDBT, pages 627--644, 2006.
• 8: Antony Galton , Juan Carlos Augusto, Two Approaches to Event Definition, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.547-556, September 02-06, 2002
• 9: Narain H. Gehani , H. V. Jagadish , Oded Shmueli, Composite Event Specification in Active Databases: Model & Implementation, Proceedings of the 18th International Conference on Very Large Data Bases, p.327-338, August 23-27, 1992
• 10: J. Kraemer and B. Seeger. A temporal foundation for continuous queries over data streams. In Proc. COMAD, pages 72--80, January 6-8, 2005.
• 11: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 12: C. Liebig , M. Cilia , A. Buchmann, Event Composition in Time-Dependent Distributed Systems, Proceedings of the Fourth IECIS International Conference on Cooperative Information Systems, p.70, September 02-04, 1999
• 13: Ben Moszkowski, Executing temporal logic programs, Cambridge University Press, New York, NY, 1986
• 14: I. Motakis and C. Zaniolo. Formal semantics for composite temporal events in active database rules. Journal of Systems Integration, 7(3-4):291--325, 1997.
• 15: P. R. Pietzuch, B. Shand, and J. Bacon. A framework for event composition in distributed systems. In Proc. ACM/IFIP/USENIX International Middleware Conference, pages 62--82, 2003.
• 16: J. van Benthem. The Logic of Time. Kluwer Academic Publishers, 2nd edition edition, 1991.
• 17: W. White, M. Riedewald, J. Gehrke, and A. Demers. What's "next"? Technical Report TR2006-2033, Cornell University, 2006. http://techreports.library.cornell.edu.
• 18: Eugene Wu , Yanlei Diao , Shariq Rizvi, High-performance complex event processing over streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142520]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Theory

Keywords:
axiomatization, events, temporal models