Discovery and Ranking of Embedded Uniqueness Constraints

Summary: First study of embedded uniqueness constraints (eUCs): unique column combinations embedded in complete fragments of incomplete data, realized as filtered indexes for integrity and query optimization. Shows NP-complete decision variant, W[2]-complete, max-size bounds, scalable column/row algorithms with a hybrid approach, and ranking to identify relevant eUCs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11956
Venue: VLDB
Year: 2019
Pagerank: 4.5858215e-05
Overall Rank: 8,087 | 43.80%
DOI: 10.14778/3358701.3358703

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,911	Normalizing Property Graphs	2023	VLDB	5.2718035e-05
7,361	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7469673e-05
8,851	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	4.4322123e-05
9,748	Efficient Differential Dependency Discovery	2024	VLDB	4.2856385e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
890	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015542177
1,047	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014442219
2,082	Efficient Discovery of Approximate Dependencies	2018	VLDB	9.5875364e-05
2,551	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.5553153e-05
3,824	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	6.7233576e-05
4,502	Possible and Certain SQL Keys	2015	VLDB	6.1322784e-05
4,680	Scalable Discovery of Unique Column Combinations	2014	VLDB	5.9964535e-05
8,472	DataProf: Semantic Profiling for Iterative Data Cleansing and Business Rule Acquisition	2018	SIGMOD	4.4985733e-05
11,862	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,502	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011614522
6,691	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	4.9573939e-05
10,549	Discovering Approximate Inclusion Dependencies	2025	VLDB	4.1905499e-05
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
4,740	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	5.9515736e-05
12,199	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1905499e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
8,851	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	4.4322123e-05
4,680	Scalable Discovery of Unique Column Combinations	2014	VLDB	5.9964535e-05
7,361	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7469673e-05