Controlling entity integrity with key sets

Codd's rule of entity integrity stipulates that every table has a primary key. Key sets can control entity integrity when primary keys do not exist. While key set validation is quadratic, update maintenance for unary key sets is efficient when incomplete values only occur in few key columns. We...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2023-09, Vol.136, p.195-219
Main Authors: Hannula, Miika, Li, Xinyi, Link, Sebastian
Format: Article
Language:English
Subjects:
Axioms
Complexity
Discovery
Entity integrity
Implication
Key set
Missing data
Reasoning
Relational database
Validation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Codd's rule of entity integrity stipulates that every table has a primary key. Key sets can control entity integrity when primary keys do not exist. While key set validation is quadratic, update maintenance for unary key sets is efficient when incomplete values only occur in few key columns. We establish a binary axiomatization for the implication problem, and prove its coNP-completeness. However, the implication of unary by arbitrary key sets has better properties. The fragment enjoys a unary axiomatization and is decidable in quadratic time. Hence, we can minimize overheads before validating key sets. While Armstrong relations do not always exist, we show how to compute them for any instance of our fragment. Similarly, we show how unary keys sets can be mined from relations using hypergraph transversals. Finally, we establish an axiomatization and computational complexity for the implication problem of key sets combined with NOT NULL constraints.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2023.04.004