Article ID Journal Published Year Pages File Type
419394 Discrete Applied Mathematics 2013 8 Pages PDF
Abstract

The problem of recognizing whether a subset of attributes is a premise of a minimal cover of functional dependencies of a relation is shown to be coNP-complete. The complexity of some related decision, enumerating, and sampling problems on functional dependencies, FCA implications, and closed sets of attributes is discussed.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Computing premises of a minimal cover of functional dependencies is intractable
Authors
, ,