skip to main content
10.1145/1265530.1265567acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

What is "next" in event processing?

Published:11 June 2007Publication History

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.Google ScholarGoogle Scholar
  2. R. Adaikkalavan and S. Chakravarthy. SnoopIB: Interval-based event specification and detection for active databases. In Proc. ADBIS, pages 190--204, 2003.Google ScholarGoogle ScholarCross RefCross Ref
  3. J. Allen and G. Ferguson. Actions and events in interval temporal logic. Technical Report 521, University of Rochester, jul 1994. Google ScholarGoogle Scholar
  4. Mark Bickford and Robert Constable. A logic of events. Technical Report 2003-1893, Cornell University, 2003.Google ScholarGoogle Scholar
  5. M. H. Bohlen, R. Busatto, and C. S. Jensen. Point-versus interval-based temporal data models. In Proc. ICDE, pages 192--200, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  7. A. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. White. Towards expressive publish/subscribe systems. In Proc. EDBT, pages 627--644, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. A. Galton and J. C. Augusto. Two approaches to event definition. In Proc. DEXA, pages 547--556, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle Scholar
  11. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, 1978. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. Ben Moszkowski. Executing Temporal Logic Programs. Cambridge University Press, 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. J. van Benthem. The Logic of Time. Kluwer Academic Publishers, 2nd edition edition, 1991.Google ScholarGoogle ScholarCross RefCross Ref
  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.Google ScholarGoogle Scholar
  18. E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In Proc. SIGMOD, pages 407--418, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. What is "next" in event processing?

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      PODS '07: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
      June 2007
      328 pages
      ISBN:9781595936851
      DOI:10.1145/1265530

      Copyright © 2007 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 11 June 2007

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • Article

      Acceptance Rates

      PODS '07 Paper Acceptance Rate28of187submissions,15%Overall Acceptance Rate642of2,707submissions,24%

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader