Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization

Summary: Introduces a polynomial mapping of order dependencies (ODs) to a canonical form with sound, complete axioms. The resulting discovery algorithm is complete and minimal, exponential only in attributes and linear in tuples, achieving orders-of-magnitude gains over prior methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11754
Venue: VLDB
Year: 2017
Pagerank: 6.6929626e-05
Overall Rank: 4,454 | 69.45%
DOI: 10.14778/3067421.3067426

Incoming Non-self Citations Over Time

Authors

1. Jaroslaw Szlichta (University of Ontario Institute of Technology)
2. Parke Godfrey (York University)
3. Lukasz Golab (University of Waterloo)
4. Mehdi Kargar (University of Windsor)
5. Divesh Srivastava (AT&T)

BibTeX Citation

@article{szlichta_vldb17,
        title = {{Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization}},
        author = {Szlichta, Jaroslaw and Godfrey, Parke and Golab, Lukasz and Kargar, Mehdi and Srivastava, Divesh},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {7},
        pages = {721--732},
        doi = {10.14778/3067421.3067426},
        url = {https://doi.org/10.14778/3067421.3067426},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,741	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.8755846e-05
3,387	Data Profiling – A Tutorial	2017	SIGMOD	7.4534663e-05
4,757	Pattern Functional Dependencies for Data Cleaning	2020	VLDB	6.5220005e-05
5,052	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.3846183e-05
6,720	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.794237e-05
6,938	Guided automated learning for query workload re-optimization	2019	VLDB	5.733869e-05
7,982	Fast Approximate Denial Constraint Discovery	2023	VLDB	5.5138609e-05
9,923	Efficient Differential Dependency Discovery	2024	VLDB	5.1955087e-05
10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	5.093636e-05
11,221	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
376	Discovering Denial Constraints	2013	VLDB	0.00019677674
533	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.0001705859
729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014539421
744	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00014411295
1,842	Sequential Dependencies	2009	VLDB	9.6345922e-05
3,763	Applying Approximate Order Dependency to Reduce Indexing Space	1982	SIGMOD	7.144792e-05
3,816	Optimizing Nested Queries with Parameter Sort Orders	2005	VLDB	7.1002641e-05
6,114	Fundamentals of Order Dependencies	2012	VLDB	5.9713126e-05
6,930	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7367175e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB
2	3,763	Applying Approximate Order Dependency to Reduce Indexing Space	1982	SIGMOD
3	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
4	4,659	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS
5	203	Dependency Inference	1987	VLDB
6	376	Discovering Denial Constraints	2013	VLDB
7	10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
8	6,720	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB
9	6,114	Fundamentals of Order Dependencies	2012	VLDB
10	6,930	Expressiveness and Complexity of Order Dependencies	2013	VLDB