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.
- Complex event processing. www.complexevents.com.Google Scholar
- R. Adaikkalavan and S. Chakravarthy. SnoopIB: Interval-based event specification and detection for active databases. In Proc. ADBIS, pages 190--204, 2003.Google ScholarCross Ref
- J. Allen and G. Ferguson. Actions and events in interval temporal logic. Technical Report 521, University of Rochester, jul 1994. Google Scholar
- Mark Bickford and Robert Constable. A logic of events. Technical Report 2003-1893, Cornell University, 2003.Google Scholar
- M. H. Bohlen, R. Busatto, and C. S. Jensen. Point-versus interval-based temporal data models. In Proc. ICDE, pages 192--200, 1998. Google ScholarDigital Library
- S. Chakravarthy, V. Krishnaprasad, E. Anwar, and S. -K. Kim. Composite events for active databases: Semantics, contexts and detection. In Proc. VLDB, pages 606--617, 1994. Google ScholarDigital Library
- A. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. White. Towards expressive publish/subscribe systems. In Proc. EDBT, pages 627--644, 2006. Google ScholarDigital Library
- A. Galton and J. C. Augusto. Two approaches to event definition. In Proc. DEXA, pages 547--556, 2002. Google ScholarDigital Library
- N. H. Gehani, H. V. Jagadish, and O. Shmueli. Composite event specification in active databases: Model and implementation. In Proc. VLDB, pages 327--338, 1992. Google ScholarDigital Library
- J. Kraemer and B. Seeger. A temporal foundation for continuous queries over data streams. In Proc. COMAD, pages 72--80, January 6-8, 2005.Google Scholar
- Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, 1978. Google ScholarDigital Library
- C. Liebig, M. Cila, and A. Buchmann. Event composition in time-dependent distributed systems. In Proc. Int. Conf. on Cooperative Information Systems (CoopIS), pages 70--78. IEEE Computer Society, 1999. Google ScholarDigital Library
- Ben Moszkowski. Executing Temporal Logic Programs. Cambridge University Press, 1986. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. van Benthem. The Logic of Time. Kluwer Academic Publishers, 2nd edition edition, 1991.Google ScholarCross Ref
- W. White, M. Riedewald, J. Gehrke, and A. Demers. What's "next"? Technical Report TR2006-2033, Cornell University, 2006. http://techreports.library.cornell.edu.Google Scholar
- E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In Proc. SIGMOD, pages 407--418, 2006. Google ScholarDigital Library
Index Terms
- What is "next" in event processing?
Recommendations
Probabilistic Event Calculus for Event Recognition
Symbolic event recognition systems have been successfully applied to a variety of application domains, extracting useful information in the form of events, allowing experts or other systems to monitor and respond when significant events are recognised. ...
A complete proof system for propositional projection temporal logic
The paper presents a proof system for Propositional Projection Temporal Logic (PPTL) with projection-plus. The syntax, semantics, and logical laws of PPTL are introduced together with an axiom system consisting of axioms and inference rules. To ...
Parallel First-Order Dynamic Logic and Its Expressiveness and Axiomatization
Advanced Parallel Processing TechnologiesAbstractFor modeling the parallel actions, the quantified dynamic logic (QDL) is extended to Parallel First-order Dynamic Logic (PaFDL) with parallel action compositions. The composition is introduced as an operator ( on actions in the same syntax as in ...
Comments