Controlling entity integrity with key sets

DOI10.1016/J.JCSS.2023.04.004MaRDI QIDQ6098153zbMATH OpenOpenAlexFDO

Authors Miika Hannula, Xinyi Li, Sebastian Link

Publication date 12 June 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.02472

zbMATH Keywords

axiomscomplexitydiscoveryentity integrityimplicationkey setmissing datareasoningrelational databasevalidation

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: Codd's rule of entity integrity stipulates that every table has a primary key. Hence, the attributes of the primary key carry unique and complete value combinations. In practice, data cannot always meet such requirements. Previous work proposed the superior notion of key sets for controlling entity integrity. We establish a linear-time algorithm for validating whether a given key set holds on a given data set, and demonstrate its efficiency on real-world data. We establish a binary axiomatization for the associated 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 perfect models do not always exist in general, we show how to compute them for any instance of our fragment. This provides computational support towards the acquisition of key sets.

Cites work

• A generalisation of entity and referential integrity in relational databases
• A relational model of data for large shared data banks
• Analytical approach to parallel repetition
• Automated reasoning about key sets
• Candidate keys for relations
• Complexity of automaton identification from given data
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• Horn clauses and database dependencies
• scientific article; zbMATH DE number 41085 (Why is no real title available?)
• scientific article; zbMATH DE number 108405 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2241913 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Inclusion dependencies and their interaction with functional dependencies
• Inclusion dependencies and their interaction with functional dependencies in SQL
• Minimum matrix representation of closure operations
• On keys and functional dependencies as first-class citizens in description logics
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the finite and general implication problems of independence atoms and keys
• On the Notion of an XML Key
• On XML integrity constraints in the presence of DTDs
• Possibilistic keys
• Propositional and predicate logics of incomplete information
• Reducibility among combinatorial problems
• The complexity of dependency detection and discovery in relational databases
• The logic of paradox
• The number of keys in relational and nested relational databases
• The parameterized complexity of dependency detection in relational databases
• Tractable reasoning via approximation

This page was built for publication: Controlling entity integrity with key sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098153)