KleestMeißner, Sarah ;
Sattler, Rebecca ;
Schmid, Markus L. ;
Schweikardt, Nicole ;
Weidlich, Matthias
Discovering Event Queries from Traces: Laying Foundations for SubsequenceQueries with Wildcards and GapSize Constraints
Abstract
We introduce subsequencequeries with wildcards and gapsize constraints (swgqueries, for short) as a tool for querying event traces. An swgquery q is given by a string s over an alphabet of variables and types, a global window size w, and a tuple c = ((c^_1, c^+_1), (c^_2, c^+_2), …, (c^_{s1}, c^+_{s1})) of local gapsize constraints over ℕ × (ℕ ∪ {∞}). The query q matches in a trace t (i. e., a sequence of types) if the variables can uniformly be substituted by types such that the resulting string occurs in t as a subsequence that spans an area of length at most w, and the i^{th} gap of the subsequence (i. e., the distance between the i^{th} and (i+1)^{th} position of the subsequence) has length at least c^_i and at most c^+_i. We formalise and investigate the task of discovering an swgquery that describes best the traces from a given sample S of traces, and we present an algorithm solving this task. As a central component, our algorithm repeatedly solves the matching problem (i. e., deciding whether a given query q matches in a given trace t), which is an NPcomplete problem (in combined complexity). Hence, the matching problem is of special interest in the context of query discovery, and we therefore subject it to a detailed (parameterised) complexity analysis to identify tractable subclasses, which lead to tractable subclasses of the discovery problem as well. We complement this by a reduction proving that any query discovery algorithm also yields an algorithm for the matching problem. Hence, lower bounds on the complexity of the matching problem directly translate into according lower bounds of the query discovery problem. As a proof of concept, we also implemented a prototype of our algorithm and tested it on realworld data.
BibTeX  Entry
@InProceedings{kleestmeiner_et_al:LIPIcs.ICDT.2022.18,
author = {KleestMei{\ss}ner, Sarah and Sattler, Rebecca and Schmid, Markus L. and Schweikardt, Nicole and Weidlich, Matthias},
title = {{Discovering Event Queries from Traces: Laying Foundations for SubsequenceQueries with Wildcards and GapSize Constraints}},
booktitle = {25th International Conference on Database Theory (ICDT 2022)},
pages = {18:118:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772235},
ISSN = {18688969},
year = {2022},
volume = {220},
editor = {Olteanu, Dan and Vortmeier, Nils},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15892},
URN = {urn:nbn:de:0030drops158922},
doi = {10.4230/LIPIcs.ICDT.2022.18},
annote = {Keywords: event queries on traces, pattern queries on strings, learning descriptive queries, complexity of query evaluation and query learning}
}
19.03.2022
Keywords: 

event queries on traces, pattern queries on strings, learning descriptive queries, complexity of query evaluation and query learning 
Seminar: 

25th International Conference on Database Theory (ICDT 2022)

Issue date: 

2022 
Date of publication: 

19.03.2022 
Supplementary Material: 

Audiovisual (Video of the Presentation): https://doi.org/10.5446/57490 