On the finite and general implication problems of independence atoms and keys

We investigate implication problems for keys and independence atoms in relational databases. For keys and unary independence atoms we show that finite implication is not finitely axiomatizable, and establish a finite axiomatization for general implication. The same axiomatization is also sound and c...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2016-08, Vol.82 (5), p.856-877
Main Authors: Hannula, Miika, Kontinen, Juha, Link, Sebastian
Format: Article
Language:English
Subjects:
Armstrong relation
Axiomatization
Construction
Dependence logic
Finite implication
Implication
Independence
Key
Mathematical analysis
Polynomials
Relational data bases
Sound
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate implication problems for keys and independence atoms in relational databases. For keys and unary independence atoms we show that finite implication is not finitely axiomatizable, and establish a finite axiomatization for general implication. The same axiomatization is also sound and complete for finite and general implication of unary keys and independence atoms, which coincide. We show that the general implication of keys and unary independence atoms and of unary keys and general independence atoms is decidable in polynomial time. For these two classes we also show how to construct Armstrong relations. Finally, we establish tractable conditions that are sufficient for certain classes of keys and independence atoms not to interact. •For unary independence atoms and keys, general implication is finitely axiomatizable but finite implication is not.•Finite and general implication of unary keys and independence atoms coincide and enjoy a finite axiomatization.•General implication of unary independence atoms and keys is decidable in polynomial time.•General implication of unary keys and independence atoms is decidable in polynomial time.•There are tractable conditions that are sufficient for some classes of keys and independence atoms not to interact.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2016.02.007