Fast Incremental Discovery of Pointwise Order Dependencies

Summary: Introduces incremental discovery of minimal pointwise order dependencies under tuple insertions. Novel indexes identify affected violations in logarithmic-in-data-size cost, enabling efficient invalidation and refinement of PODs and outperforming batch recomputation by orders of magnitude. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h2b740ab96fc43a3a
Venue: VLDB
Year: 2020
Pagerank: 5.6615714e-05
Overall Rank: 6,860 | 53.90%
DOI: 10.14778/3401960.3401965
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Zijing Tan (Fudan University; Shanghai Key Laboratory of Data Science)
2. Ai Ran (Fudan University; Shanghai Key Laboratory of Data Science)
3. Shuai Ma (Beihang University; Beijing Academy of Artificial Intelligence)
4. Sheng Qin (Fudan University; Shanghai Key Laboratory of Data Science)

BibTeX Citation

@article{tan_vldb20,
        title = {{Fast Incremental Discovery of Pointwise Order Dependencies}},
        author = {Tan, Zijing and Ran, Ai and Ma, Shuai and Qin, Sheng},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {10},
        pages = {1669--1681},
        doi = {10.14778/3401960.3401965},
        url = {https://doi.org/10.14778/3401960.3401965},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,283	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1963542e-05
8,861	Workload-driven, Lazy Discovery of Data Dependencies for Query Optimization	2022	CIDR	5.2619979e-05
10,110	Efficient Differential Dependency Discovery	2024	VLDB	5.0765311e-05
11,197	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.9769913e-05
11,556	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.9769913e-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
350	Discovering Denial Constraints	2013	VLDB	0.00020244085
725	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00014471289
1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012399252
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010513265
1,620	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	0.00010050865
1,888	Sequential Dependencies	2009	VLDB	9.4276992e-05
1,972	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2829634e-05
3,296	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	7.444648e-05
3,419	Data Profiling – A Tutorial	2017	SIGMOD	7.3175997e-05
3,958	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	6.8960375e-05
4,226	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.7151469e-05
4,467	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.5842379e-05
5,133	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.2573449e-05
6,173	Fundamentals of Order Dependencies	2012	VLDB	5.8595496e-05
6,427	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7867997e-05
7,245	Discovering Graph Functional Dependencies	2018	SIGMOD	5.5741839e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,964	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD
2	1,888	Sequential Dependencies	2009	VLDB
3	10,110	Efficient Differential Dependency Discovery	2024	VLDB
4	1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB
5	11,262	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
6	6,173	Fundamentals of Order Dependencies	2012	VLDB
7	11,197	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD
8	10,063	Discovering Approximate Inclusion Dependencies	2025	VLDB
9	6,427	Expressiveness and Complexity of Order Dependencies	2013	VLDB
10	4,467	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB