License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2020.14
URN: urn:nbn:de:0030-drops-119389
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11938/
Go to the corresponding LIPIcs Volume Portal

Grez, Alejandro ; Riveros, Cristian

Towards Streaming Evaluation of Queries with Correlation in Complex Event Processing

pdf-format:
LIPIcs-ICDT-2020-14.pdf (0.6 MB)

Abstract

Complex event processing (CEP) has gained a lot of attention for evaluating complex patterns over high-throughput data streams. Recently, new algorithms for the evaluation of CEP patterns have emerged with strong guarantees of efficiency, i.e. constant update-time per tuple and constant-delay enumeration. Unfortunately, these techniques are restricted for patterns with local filters, limiting the possibility of using joins for correlating the data of events that are far apart.
In this paper, we embark on the search for efficient evaluation algorithms of CEP patterns with joins. We start by formalizing the so-called partition-by operator, a standard operator in data stream management systems to correlate contiguous events on streams. Although this operator is a restricted version of a join query, we show that partition-by (without iteration) is equally expressive as hierarchical queries, the biggest class of full conjunctive queries that can be evaluated with constant update-time and constant-delay enumeration over streams. To evaluate queries with partition-by we introduce an automata model, called chain complex event automata (chain-CEA), an extension of complex event automata that can compare data values by using equalities and disequalities. We show that this model admits determinization and is expressive enough to capture queries with partition-by. More importantly, we provide an algorithm with constant update time and constant delay enumeration for evaluating any query definable by chain-CEA, showing that all CEP queries with partition-by can be evaluated with these strong guarantees of efficiency.

BibTeX - Entry

@InProceedings{grez_et_al:LIPIcs:2020:11938,
  author =	{Alejandro Grez and Cristian Riveros},
  title =	{{Towards Streaming Evaluation of Queries with Correlation in Complex Event Processing}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Carsten Lutz and Jean Christoph Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11938},
  URN =		{urn:nbn:de:0030-drops-119389},
  doi =		{10.4230/LIPIcs.ICDT.2020.14},
  annote =	{Keywords: Complex event processing, Query languages, Correlation, Constant delay enumeration.}
}

Keywords: Complex event processing, Query languages, Correlation, Constant delay enumeration.
Collection: 23rd International Conference on Database Theory (ICDT 2020)
Issue Date: 2020
Date of publication: 11.03.2020
Supplementary Material: Video of the Presentation: https://doi.org/10.5446/46836

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI