Possible and Certain SQL Keys

Summary: Defines possible keys (aligned with SQL UNIQUE) and certain keys (a NULL-tolerant extension of PKs) for identity across NULL-containing relations. Proposes axioms, Armstrong tables, and an indexing scheme to enforce certain keys; experiments show NULLs in real keys and efficient enforcement. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11179
Venue: VLDB
Year: 2015
Pagerank: 6.7711902e-05
Overall Rank: 4,303 | 70.48%
DOI: 10.14778/2809974.2809975

Incoming Non-self Citations Over Time

Authors

1. Henning Köhler (Massey University)
2. Sebastian Link (University of Auckland)
3. Xiaofang Zhou (Soochow University; University of Queensland)

BibTeX Citation

@article{kohler_vldb15,
        title = {{Possible and Certain SQL Keys}},
        author = {Köhler, Henning and Link, Sebastian and Zhou, Xiaofang},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {11},
        doi = {10.14778/2809974.2809975},
        url = {https://doi.org/10.14778/2809974.2809975},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,500	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010561098
2,123	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	9.1372798e-05
3,441	A Statistical Perspective on Discovering Functional Dependencies in Noisy Data	2020	SIGMOD	7.4138323e-05
7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.6776392e-05
8,137	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.4809275e-05
8,399	DataProf: Semantic Profiling for Iterative Data Cleansing and Business Rule Acquisition	2018	SIGMOD	5.4333402e-05
8,844	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3588479e-05
12,055	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
613	Database Relations with Null Values (Extended Abstract)	1982	PODS	0.00015723523
736	Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time	1996	SIGMOD	0.00014508563
1,273	Fusing Data with Correlations	2014	SIGMOD	0.00011384191
1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.9625097e-05
1,850	Bolt-on Causal Consistency	2013	SIGMOD	9.6167827e-05
2,269	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.8328424e-05
2,365	A Revival of Integrity Constraints for Data Cleaning	2008	VLDB	8.6867205e-05
3,392	Complete Yet Practical Search for Minimal Query Reformulations Under Constraints	2014	SIGMOD	7.4515019e-05
4,183	Scalable Discovery of Unique Column Combinations	2014	VLDB	6.8467773e-05
4,962	Transactions And Integrity Constraints	1985	PODS	6.4273819e-05
9,122	ConsAD: A Real-Time Consistency Anomalies Detector	2012	SIGMOD	5.3193423e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,950	SQL Nulls and Two-Valued Logic	2023	PODS
2	6,627	Schema-free SQL	2014	SIGMOD
3	7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS
4	12,414	When Data Dependencies over SQL Tables Meet the Logics of Paradox and S-3	2010	PODS
5	4,032	On Relational Algebra With Marked Nulls	1984	PODS
6	5,643	Conjunctive Query Equivalence of Keyed Relational Schemas (Extended Abstract)	1997	PODS
7	5,378	Troubles with Nulls, Views from the Users	2022	VLDB
8	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
9	5,773	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS
10	3,925	A Formal Semantics of SQL Queries, Its Validation, and Applications	2018	VLDB