Search Results

Documents authored by Vansummeren, Stijn

Document
DOI: 10.4230/OASIcs.Tannen.4
Annotation and More Annotation: Some Problems Posed by (and to) Val Tannen

Authors: Peter Buneman and Stijn Vansummeren

Published in: OASIcs, Volume 119, The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (2024)

Abstract
Among the many research accomplishments of Val Tannen, his work on provenance and semirings is probably the most widely known. In this paper, we discuss questions that arise when applying this general framework to the setting of curated databases, and in particular the setting where we can have multiple annotations on the same data, as well as annotations on annotations.
Cite as

Peter Buneman and Stijn Vansummeren. Annotation and More Annotation: Some Problems Posed by (and to) Val Tannen. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 4:1-4:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buneman_et_al:OASIcs.Tannen.4,
  author =	{Buneman, Peter and Vansummeren, Stijn},
  title =	{{Annotation and More Annotation: Some Problems Posed by (and to) Val Tannen}},
  booktitle =	{The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen},
  pages =	{4:1--4:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-320-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{119},
  editor =	{Amarilli, Antoine and Deutsch, Alin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.4},
  URN =		{urn:nbn:de:0030-drops-201007},
  doi =		{10.4230/OASIcs.Tannen.4},
  annote =	{Keywords: Annotation, provenance, semiring, curated data}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2024.12
Enumeration and Updates for Conjunctive Linear Algebra Queries Through Expressibility

Authors: Thomas Muñoz Serrano, Cristian Riveros, and Stijn Vansummeren

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)

Abstract
Due to the importance of linear algebra and matrix operations in data analytics, there is significant interest in using relational query optimization and processing techniques for evaluating (sparse) linear algebra programs. In particular, in recent years close connections have been established between linear algebra programs and relational algebra that allow transferring optimization techniques of the latter to the former. In this paper, we ask ourselves which linear algebra programs in MATLANG correspond to the free-connex and q-hierarchical fragments of conjunctive first-order logic. Both fragments have desirable query processing properties: free-connex conjunctive queries support constant-delay enumeration after a linear-time preprocessing phase, and q-hierarchical conjunctive queries further allow constant-time updates. By characterizing the corresponding fragments of MATLANG, we hence identify the fragments of linear algebra programs that one can evaluate with constant-delay enumeration after linear-time preprocessing and with constant-time updates. To derive our results, we improve and generalize previous correspondences between MATLANG and relational algebra evaluated over semiring-annotated relations. In addition, we identify properties on semirings that allow to generalize the complexity bounds for free-connex and q-hierarchical conjunctive queries from Boolean annotations to general semirings.
Cite as

Thomas Muñoz Serrano, Cristian Riveros, and Stijn Vansummeren. Enumeration and Updates for Conjunctive Linear Algebra Queries Through Expressibility. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{munozserrano_et_al:LIPIcs.ICDT.2024.12,
  author =	{Mu\~{n}oz Serrano, Thomas and Riveros, Cristian and Vansummeren, Stijn},
  title =	{{Enumeration and Updates for Conjunctive Linear Algebra Queries Through Expressibility}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.12},
  URN =		{urn:nbn:de:0030-drops-197946},
  doi =		{10.4230/LIPIcs.ICDT.2024.12},
  annote =	{Keywords: Query evaluation, conjunctive queries, linear algebra, enumeration algorithms}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.TIME.2022.3
Getting to the CORE of Complex Event Recognition (Invited Talk)

Authors: Stijn Vansummeren

Published in: LIPIcs, Volume 247, 29th International Symposium on Temporal Representation and Reasoning (TIME 2022)

Abstract
In this talk, I will give an overview of our recent work on complex event recognition.
Cite as

Stijn Vansummeren. Getting to the CORE of Complex Event Recognition (Invited Talk). In 29th International Symposium on Temporal Representation and Reasoning (TIME 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 247, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vansummeren:LIPIcs.TIME.2022.3,
  author =	{Vansummeren, Stijn},
  title =	{{Getting to the CORE of Complex Event Recognition}},
  booktitle =	{29th International Symposium on Temporal Representation and Reasoning (TIME 2022)},
  pages =	{3:1--3:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-262-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{247},
  editor =	{Artikis, Alexander and Posenato, Roberto and Tonetta, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2022.3},
  URN =		{urn:nbn:de:0030-drops-172503},
  doi =		{10.4230/LIPIcs.TIME.2022.3},
  annote =	{Keywords: Complex Event Recognition, automata, enumeration-based query processing}
}
Document
DOI: 10.4230/DagRep.10.2.19
Foundations of Composite Event Recognition (Dagstuhl Seminar 20071)

Authors: Alexander Artikis, Thomas Eiter, Alessandro Margara, and Stijn Vansummeren

Published in: Dagstuhl Reports, Volume 10, Issue 2 (2020)

Abstract
Composite Event Recognition (CER) refers to the activity of detecting patterns in streams of continuously arriving "event" data over, possibly geographically, distributed sources. CER is key in Big Data applications that require the processing of such event streams to obtain timely insights and to implement reactive and proactive measures. Examples include the recognition of emerging stories and trends on the Social Web, traffic and transport incidents in smart cities, and epidemic spread. Numerous CER languages have been proposed in the literature. While these systems have a common goal, they differ in their data models, pattern languages and processing mechanisms, resulting in heterogeneous implementations with fundamentally different capabilities. Moreover, we lack a common understanding of the trade-offs between expressiveness and complexity, and a theory for comparing the fundamental capabilities of CER systems. As such, CER frameworks are difficult to understand, extend and generalise. It is unclear which of the proposed approaches better meets the requirements of a given application. Furthermore, the lack of foundations makes it hard to leverage established results - from automata theory, temporal logics, etc - thus hindering scientific and technological progress in CER. The objective of the seminar was to bring together researchers and practitioners working in Databases, Distributed Systems, Automata Theory, Logic and Stream Reasoning; disseminate the recent foundational results across these fields; establish new research collaborations among these fields; thereby start making progress towards formulating such foundations.
Cite as

Alexander Artikis, Thomas Eiter, Alessandro Margara, and Stijn Vansummeren. Foundations of Composite Event Recognition (Dagstuhl Seminar 20071). In Dagstuhl Reports, Volume 10, Issue 2, pp. 19-49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{artikis_et_al:DagRep.10.2.19,
  author =	{Artikis, Alexander and Eiter, Thomas and Margara, Alessandro and Vansummeren, Stijn},
  title =	{{Foundations of Composite Event Recognition (Dagstuhl Seminar 20071)}},
  pages =	{19--49},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{10},
  number =	{2},
  editor =	{Artikis, Alexander and Eiter, Thomas and Margara, Alessandro and Vansummeren, Stijn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.10.2.19},
  URN =		{urn:nbn:de:0030-drops-130587},
  doi =		{10.4230/DagRep.10.2.19},
  annote =	{Keywords: complex event processing, event algebra, pattern matching, stream reasoning, temporal reasoning}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2020.15
On the Expressiveness of Languages for Complex Event Recognition

Authors: Alejandro Grez, Cristian Riveros, Martín Ugarte, and Stijn Vansummeren

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
Complex Event Recognition (CER for short) has recently gained attention as a mechanism for detecting patterns in streams of continuously arriving event data. Numerous CER systems and languages have been proposed in the literature, commonly based on combining operations from regular expressions (sequencing, iteration, and disjunction) and relational algebra (e.g., joins and filters). While these languages are naturally first-order, meaning that variables can only bind single elements, they also provide capabilities for filtering sets of events that occur inside iterative patterns; for example requiring sequences of numbers to be increasing. Unfortunately, these type of filters usually present ad-hoc syntax and under-defined semantics, precisely because variables cannot bind sets of events. As a result, CER languages that provide filtering of sequences commonly lack rigorous semantics and their expressive power is not understood. In this paper we embark on two tasks: First, to define a denotational semantics for CER that naturally allows to bind and filter sets of events; and second, to compare the expressive power of this semantics with that of CER languages that only allow for binding single events. Concretely, we introduce Set-Oriented Complex Event Logic (SO-CEL for short), a variation of the CER language introduced in [Grez et al., 2019] in which all variables bind to sets of matched events. We then compare SO-CEL with CEL, the CER language of [Grez et al., 2019] where variables bind single events. We show that they are equivalent in expressive power when restricted to unary predicates but, surprisingly, incomparable in general. Nevertheless, we show that if we restrict to sets of binary predicates, then SO-CEL is strictly more expressive than CEL. To get a better understanding of the expressive power, computational capabilities, and limitations of SO-CEL, we also investigate the relationship between SO-CEL and Complex Event Automata (CEA), a natural computational model for CER languages. We define a property on CEA called the *-property and show that, under unary predicates, SO-CEL captures precisely the subclass of CEA that satisfy this property. Finally, we identify the operations that SO-CEL is lacking to characterize CEA and introduce a natural extension of the language that captures the complete class of CEA under unary predicates.
Cite as

Alejandro Grez, Cristian Riveros, Martín Ugarte, and Stijn Vansummeren. On the Expressiveness of Languages for Complex Event Recognition. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{grez_et_al:LIPIcs.ICDT.2020.15,
  author =	{Grez, Alejandro and Riveros, Cristian and Ugarte, Mart{\'\i}n and Vansummeren, Stijn},
  title =	{{On the Expressiveness of Languages for Complex Event Recognition}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.15},
  URN =		{urn:nbn:de:0030-drops-119390},
  doi =		{10.4230/LIPIcs.ICDT.2020.15},
  annote =	{Keywords: Query languages, Complex Event Recognition, Logics, Automata theory}
}
Document
DOI: 10.4230/DagRep.2.2.84
Principles of Provenance (Dagstuhl Seminar 12091)

Authors: James Cheney, Anthony Finkelstein, Bertram Ludaescher, and Stijn Vansummeren

Published in: Dagstuhl Reports, Volume 2, Issue 2 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12091 ``Principles of Provenance''. The term ``provenance'' refers to information about the origin, context, derivation, ownership or history of some artifact. In both art and science, provenance information is crucial for establishing the value of a real-world artifact, guaranteeing for example that the artifact is an original work produced by an important artist, or that a stated scientific conclusion is reproducible. Since it is much easier to copy or alter digital information than it is to copy or alter real-world artifacts, the need for tracking and management of provenance information to testify the value and correctness of digital information has been firmly established in the last few years. As a result, provenance tracking and management has been studied in many settings, ranging from databases, scientific workflows, business process modeling, and security to social networking and the Semantic Web, but with relatively few interaction between these areas. This Dagstuhl seminar has focused on bringing together researchers from the above and other areas to identify the commonalities and differences of dealing with provenance; improve the mutual understanding of these communities; and identify main areas for further foundational provenance research.
Cite as

James Cheney, Anthony Finkelstein, Bertram Ludaescher, and Stijn Vansummeren. Principles of Provenance (Dagstuhl Seminar 12091). In Dagstuhl Reports, Volume 2, Issue 2, pp. 84-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{cheney_et_al:DagRep.2.2.84,
  author =	{Cheney, James and Finkelstein, Anthony and Ludaescher, Bertram and Vansummeren, Stijn},
  title =	{{Principles of Provenance (Dagstuhl Seminar 12091)}},
  pages =	{84--113},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{2},
  editor =	{Cheney, James and Finkelstein, Anthony and Ludaescher, Bertram and Vansummeren, Stijn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.2.84},
  URN =		{urn:nbn:de:0030-drops-35073},
  doi =		{10.4230/DagRep.2.2.84},
  annote =	{Keywords: Provenance, Lineage, Metadata, Trust, Repeatability, Accountability}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact