We study two approximate variants of inclusion atoms and examine the axiomatization and computational complexity of their implication problems. The approximate variants allow for some imperfection in a team (corresponding to a unirelational database), and differ in how this degree is measured. One considers the error relative to the size of the team, while the other applies a fixed threshold independent of size. We obtain complete axiomatizations for both under some arity restrictions. In particular, restricted to unary atoms, the implication problem for each approximate variant is decidable in polynomial time.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Axiomatizing Variants of Approximate Inclusion

  • Matilda Häggblom

摘要

We study two approximate variants of inclusion atoms and examine the axiomatization and computational complexity of their implication problems. The approximate variants allow for some imperfection in a team (corresponding to a unirelational database), and differ in how this degree is measured. One considers the error relative to the size of the team, while the other applies a fixed threshold independent of size. We obtain complete axiomatizations for both under some arity restrictions. In particular, restricted to unary atoms, the implication problem for each approximate variant is decidable in polynomial time.