On the finite and general implication problems of independence atoms and keys
作者：
Highlights：
• 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.
摘要
•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.
论文关键词：Armstrong relation,Axiomatization,Dependence logic,Finite implication,Implication,Independence,Key
论文评审过程：Received 3 June 2015, Revised 18 November 2015, Accepted 15 February 2016, Available online 9 March 2016, Version of Record 1 April 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.02.007
