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: 6160
Venue: SIGMOD
Year: 2021
Pagerank: 5.4364073e-05
Overall Rank: 8,388 | 42.46%
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,793	Apache IoTDB: A Time Series Database for IoT Applications	2023	SIGMOD	7.1217835e-05
8,110	Erebus: Explaining the Outputs of Data Streaming Queries	2023	VLDB	5.484341e-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
229	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023927582
385	Why Not?	2009	SIGMOD	0.00019455743
565	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016445548
628	On the Provenance of Non-Answers to Queries over Extracted Data	2008	VLDB	0.00015630285
629	Composite Events for Active Databases: Semantics, Contexts and Detection	1994	VLDB	0.00015625304
856	How to ConQueR Why-Not Questions	2010	SIGMOD	0.00013573466
899	Consistent Streaming Through Time: A Vision for Event Stream Processing	2007	CIDR	0.00013337792
955	Truth Finding on the Deep Web: Is the Problem Solved?	2013	VLDB	0.00012996675
1,547	On Complexity and Optimization of Expensive Queries in Complex Event Processing	2014	SIGMOD	0.00010394989
2,032	Explaining Missing Answers to SPJUA Queries	2010	VLDB	9.2828822e-05
2,142	Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms	2016	VLDB	9.0975882e-05
2,520	Plan-based Complex Event Detection across Distributed Sources	2008	VLDB	8.4741249e-05
2,895	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.9829449e-05
2,995	Time Series Data Cleaning: From Anomaly Detection to Anomaly Repairing	2017	VLDB	7.8750141e-05
5,776	Recognizing Patterns in Streams with Imprecise Timestamps	2010	VLDB	6.0920784e-05
6,360	Approximate Summaries for Why and Why-not Provenance	2020	VLDB	5.9009081e-05
6,560	IL-Miner: Instance-Level Discovery of Complex Event Patterns	2017	VLDB	5.8393764e-05

Semantically Similar Papers

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