Fast Incremental Discovery of Pointwise Order Dependencies

Summary: Incremental discovery of pointwise order dependencies (PODs) under insertions. Uses novel indexing for Sigma and D to detect violations with log(|D|) cost, and a DeltaSigma refinement to update Sigma; experiments show up to orders-of-magnitude speedups over full recomputation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12072
Venue: VLDB
Year: 2020
Pagerank: 4.933198e-05
Overall Rank: 6,759 | 53.03%
DOI: 10.14778/3401960.3401965

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,698	Workload-driven, Lazy Discovery of Data Dependencies for Query Optimization	2022	CIDR	4.4604438e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4350633e-05
9,748	Efficient Differential Dependency Discovery	2024	VLDB	4.2856385e-05
10,499	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.1905499e-05
11,004	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
556	Discovering Denial Constraints	2013	VLDB	0.00020214701
904	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00015425636
1,187	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00013432048
2,082	Efficient Discovery of Approximate Dependencies	2018	VLDB	9.5875364e-05
2,163	Sequential Dependencies	2009	VLDB	9.3956956e-05
2,258	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1804145e-05
2,484	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6737275e-05
3,473	Data Profiling – A Tutorial	2017	SIGMOD	7.0623537e-05
3,575	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9509846e-05
4,403	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	6.2054188e-05
4,680	Scalable Discovery of Unique Column Combinations	2014	VLDB	5.9964535e-05
4,740	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.9515736e-05
5,622	Distributed implementations of dependency discovery algorithms	2019	VLDB	5.4050344e-05
6,431	Fundamentals of Order Dependencies	2012	VLDB	5.058289e-05
7,120	Discovering Graph Functional Dependencies	2018	SIGMOD	4.8200122e-05
7,259	Expressiveness and Complexity of Order Dependencies	2013	VLDB	4.7815192e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,277	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB	4.1905499e-05
2,163	Sequential Dependencies	2009	VLDB	9.3956956e-05
9,748	Efficient Differential Dependency Discovery	2024	VLDB	4.2856385e-05
1,187	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00013432048
10,595	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.1905499e-05
6,431	Fundamentals of Order Dependencies	2012	VLDB	5.058289e-05
10,499	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.1905499e-05
10,549	Discovering Approximate Inclusion Dependencies	2025	VLDB	4.1905499e-05
7,259	Expressiveness and Complexity of Order Dependencies	2013	VLDB	4.7815192e-05
4,740	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.9515736e-05