Why Not Match: On Explanations of Event Pattern Queries

Summary: Explanations for non-answers in event-pattern queries; two classes: pattern-consistency (no match) and timestamp-modification. NP-complete for both; notation isolates tractable/approximate cases; experiments on real/synthetic data show practicality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h86d6b73475f7c664
Venue: SIGMOD
Year: 2021
Pagerank: 5.3200136e-05
Overall Rank: 8,539 | 42.59%
DOI: 10.1145/3448016.3452818

Incoming Non-self Citations Over Time

Authors

1. Shaoxu Song (Tsinghua University)
2. Ruihong Huang (Tsinghua University)
3. Yu Gao (Tsinghua University)
4. Jianmin Wang (Tsinghua University)

BibTeX Citation

@inproceedings{song_sigmod21,
        title = {{Why Not Match: On Explanations of Event Pattern Queries}},
        author = {Song, Shaoxu and Huang, Ruihong and Gao, Yu and Wang, Jianmin},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452818},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452818},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,622	Apache IoTDB: A Time Series Database for IoT Applications	2023	SIGMOD	7.1536644e-05
7,802	Erebus: Explaining the Outputs of Data Streaming Queries	2023	VLDB	5.4506419e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
241	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023419748
391	Why Not?	2009	SIGMOD	0.00019238698
580	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016085679
622	On the Provenance of Non-Answers to Queries over Extracted Data	2008	VLDB	0.00015484312
639	Composite Events for Active Databases: Semantics, Contexts and Detection	1994	VLDB	0.00015297525
791	How to ConQueR Why-Not Questions	2010	SIGMOD	0.00013976192
895	Consistent Streaming Through Time: A Vision for Event Stream Processing	2007	CIDR	0.00013211204
938	Truth Finding on the Deep Web: Is the Problem Solved?	2013	VLDB	0.00012973266
1,584	On Complexity and Optimization of Expensive Queries in Complex Event Processing	2014	SIGMOD	0.00010163707
2,051	Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms	2016	VLDB	9.1199511e-05
2,067	Explaining Missing Answers to SPJUA Queries	2010	VLDB	9.0924963e-05
2,570	Plan-based Complex Event Detection across Distributed Sources	2008	VLDB	8.2851059e-05
2,955	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.8102237e-05
2,971	Time Series Data Cleaning: From Anomaly Detection to Anomaly Repairing	2017	VLDB	7.7971821e-05
5,895	Recognizing Patterns in Streams with Imprecise Timestamps	2010	VLDB	5.9557639e-05
6,486	Approximate Summaries for Why and Why-not Provenance	2020	VLDB	5.7686627e-05
6,677	IL-Miner: Instance-Level Discovery of Complex Event Patterns	2017	VLDB	5.711278e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,410	Scalable Pattern Sharing on Event Streams	2016	SIGMOD
2	4,621	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB
3	301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS
4	580	Efficient Pattern Matching over Event Streams	2008	SIGMOD
5	5,096	Querying Graph Patterns	2011	PODS
6	8,169	Efficient Recovery of Missing Events	2013	VLDB
7	4,840	High-Level Why-Not Explanations using Ontologies	2015	PODS
8	5,895	Recognizing Patterns in Streams with Imprecise Timestamps	2010	VLDB
9	1,584	On Complexity and Optimization of Expensive Queries in Complex Event Processing	2014	SIGMOD
10	4,583	Event Pattern Matching over Graph Streams	2015	VLDB