<p>It seems like this problem may be known as the <em>dependency inference problem</em>, as described in <a href="http://www.vldb.org/conf/1987/P155.PDF" rel="nofollow">this extended abstract</a> of the paper <a href="http://portal.acm.org/citation.cfm?id=671482" rel="nofollow">"Dependency Inference"</a> by Mannila and Raiha in VLDB '87:</p>

<blockquote>
  <p>Given a relation $r$, find a set of functional dependencies that logically determines all the functional dependencies holding in $r$.</p>
</blockquote>

<p>Unfortunately, it seems that this problem is intractably super-polynomial. According to the same extended abstract:</p>

<blockquote>
  <p>Theorem 1. For each $n$ there exists a relation over $R$ such that
  $n = |R|$, $|r| = O(n)$, and each cover of $dep(r)$ has $\Omega(2^{n/2})$ dependencies.</p>
</blockquote>

<p>In other words, you cannot guarantee that the minimal cover is sub-exponential in the size of the input.</p>

<p>EDIT: However, the asker is asking whether or not an <em>output</em>-polynomial algorithm exists (i.e.: an algorithm that runs in time polynomial in the size of the input and output). The nearest reference I can find is in the paper <a href="http://reference.kfupm.edu.sa/content/i/d/identifying_the_minimal_transversals_of__179494.pdf" rel="nofollow">"Identifying the Minimal Transversals of a Hypergraph and Related Problems"</a>, SIAM J. Computing, 1995 (24) by Eiter and Gottlob. 
They first define problems AP1 and AP2 where AP2 is the dependency inference problem. Then, they state the following:</p>

<blockquote>
  <p>Note that problems AP1 and AP2, which are search problems in terms of complexity theory, are solvable by algorithms in output-polynomial time only if the following decision problem, which we call FD-RELATION EQUIVALENCE, is in P:</p>
  
  <ul>
  <li><em>Problem</em>: FD-RELATION EQUIVALENCE</li>
  <li><em>Instance</em>: A relation $R$ and a set $F$ of FD.</li>
  <li><em>Question</em>: Does $F_R = F^+$ hold ?</li>
  </ul>
  
  <p>FD-RELATION EQUIVALENCE is in co-NP, but there is neither a polynomial time algorithm known for this problem nor is it proved co-NP-complete.</p>
</blockquote>

CC BY-SA 2.5
2011-01-18T03:57:17.713Z
The way around this I suspect is to determine a minimal cover directly (in the sense described in my answer below). While the above theorem shows that the number of dependencies may be large, it may  be the case that the size of a minimal cover is small.
Suresh Venkat
CC BY-SA 2.5
2011-01-18T06:24:34.190Z
I don't have access to the underlying paper (just the linked extended abstract), but it seems that the theorem as stated implies that there exist instances where all covers -- including minimal covers -- are large.
mhum
CC BY-SA 2.5
2011-01-18T09:33:17.267Z
this is correct. Later work refers to this paper as claiming the same thing. So this is an answer to the OP's question then.
Suresh Venkat
CC BY-SA 2.5
2011-01-18T12:12:13.727Z
The problem is to generate minimal FD cover in OUTPUT polynomial time. If there are exponential minimal FD cover it does not mean that there are no output polynomial algorithm. (output polynomial means that complexity is polynomial in ouput and input size)
MikleB
CC BY-SA 2.5
2011-01-18T15:09:52.607Z
Ah, sorry about that. I missed the part about output polynomial.
mhum
CC BY-SA 2.5
2011-01-19T17:20:25.973Z
Thanks for the link! But it is still not an answer that I am looking for (I know about simple hsat-hardness).
MikleB
CC BY-SA 2.5
2011-01-19T22:43:40.203Z
Indeed. In further inconclusive investigations, it appears that this problem and several related problems (e.g.: Intersecting Monotone UNSAT) are still of undetermined complexity. Namely, it looks to me like the state of the art is that no polynomial algorithms are known nor any reductions to NP- or co-NP-completeness.
mhum
CC BY-SA 2.5
2011-01-18T02:59:17.350Z
2011-01-18T15:28:30.173Z
2011-01-18T15:28:30.173Z
mhum
<p>I would recommend investigating the field of <a href="http://en.wikipedia.org/wiki/Finite_model_theory" rel="nofollow">Finite Model Theory</a> and more particularly its sub-field <a href="http://en.wikipedia.org/wiki/Descriptive_complexity" rel="nofollow">Descriptive Complexity</a>.  It can be used to model such sorts of problems.</p>

CC BY-SA 2.5
2011-01-13T16:28:23.907Z
2011-01-13T16:28:23.907Z
Marc Hamann
<p>David Maier has a <a href="http://web.cecs.pdx.edu/~maier/TheoryBook/MAIER/C05.pdf" rel="nofollow">chapter on optimal covers</a> (under various notions of optimal) in his book on the theory of relational databases. He shows in there that given a set of FDs, finding a minimum cardinality cover is in P (but finding a cover of minimum description length is NP-hard)</p>

CC BY-SA 2.5
2011-01-13T21:35:49.293Z
I know it. But finding minimal FDs cover by given relational database is at least hard as simple-transversal hypergraph problem (or monotone self-duality). Unlikly there are known some polynomial algorithms for it.
MikleB
CC BY-SA 2.5
2011-01-13T22:13:26.523Z
so you're saying that the difference is because of FDs NOT being given as part of the input ?
Suresh Venkat
CC BY-SA 2.5
2011-01-13T23:08:28.630Z
Yes. Input is only relational database, which is given by table (some matrix)
MikleB
CC BY-SA 2.5
2011-01-13T19:51:41.847Z
2011-01-13T21:02:07.627Z
2011-01-13T21:02:07.627Z
Suresh Venkat
<p>Given a relational database and the problem is to generate some minimal cover (i.e. the minimal (by cardinality) set of functional dependencies that all other FD follows from them by Armstrong rules) in output polynomial time. </p>

<p>It's look like that this problem can not be solved in output polynomial time unless $P=NP$, but I couldn't find any papers about it.</p>

CC BY-SA 2.5
2011-01-10T17:10:50.933Z
1. it would help to have a more informative title, along the lines of 'Comlexity of finding minimal cover of FDs' or something like that. 2. If you merely google 'minimal cover for a set of FDs' you find a number of links: this is very basic material in the theory of FDs, and your best bet is to look at a database theory book like 'Foundations of Databases'.
Suresh Venkat
CC BY-SA 2.5
2011-01-10T17:18:51.657Z
I have seen many papers about FDs, but I have never seen papers about complexity of this problem, only trivial propostions about exponential size of output in input size and some heuristic algorithms (exponential in worst case).
MikleB
CC BY-SA 2.5
2011-01-10T17:28:02.517Z
See Section 5.6 of this document (http://www.dbis.informatik.hu-berlin.de/~freytag/Maier/C05.pdf). Is this what you're looking for?
Gautam Kamath
CC BY-SA 2.5
2011-01-10T17:33:07.707Z
No because we don't have set of FDs, we have only relational DB.
MikleB
CC BY-SA 2.5
2011-01-14T06:14:04.667Z
@Kaveh this isn't complexity theory: it's mainstream db theor
Suresh Venkat
CC BY-SA 2.5
2011-01-14T06:46:59.097Z
@Suresh: the [np-hardness] tag and "It's look like that this problem can not be solved in output polynomial time unless P=NP" seemed complexity theory to me. ps: I haven't said it is not mainstream db theory.
Kaveh
CC BY-SA 2.5
2011-01-14T06:51:48.977Z
it's an NP-hardness question, so the np-hardness label is appropriate. But the main arxiv area for this is databases, so it gets that tag. that's my reasoning.
Suresh Venkat
CC BY-SA 2.5
2011-01-14T06:55:54.247Z
@Suresh: I don't view them as exclusive, but I don't have a strong opinion on it.
Kaveh
CC BY-SA 2.5
2011-01-14T06:58:08.537Z
one test is that a paper on this topic is likely to be classified under cs.DB in the arxiv.
Suresh Venkat
<np-hardness><db.databases>
Complexity of finding minimal cover of FDs
MikleB
# Complexity of finding minimal cover of FDs

(Asked by: username_0 on 2011-01-10)

Given a relational database and the problem is to generate some minimal cover (i.e. the minimal (by cardinality) set of functional dependencies that all other FD follows from them by Armstrong rules) in output polynomial time.

It's look like that this problem can not be solved in output polynomial time unless $P=NP$, but I couldn't find any papers about it.

**Tags:** np-hardness, db.databases

> **Comments:**
> **username_1**: 1. it would help to have a more informative title, along the lines of 'Comlexity of finding minimal cover of FDs' or something like that. 2. If you merely google 'minimal cover for a set of FDs' you find a number of links: this is very basic material in the theory of FDs, and your best bet is to look at a database theory book like 'Foundations of Databases'.  
> **username_0**: I have seen many papers about FDs, but I have never seen papers about complexity of this problem, only trivial propostions about exponential size of output in input size and some heuristic algorithms (exponential in worst case).  
> **username_2**: See Section 5.6 of this document (http://www.dbis.informatik.hu-berlin.de/~freytag/Maier/C05.pdf). Is this what you're looking for?  
> **username_0**: No because we don't have set of FDs, we have only relational DB.  
> **username_1**: @username_3 this isn't complexity theory: it's mainstream db theor  
> **username_3**: @Suresh: the [np-hardness] tag and "It's look like that this problem can not be solved in output polynomial time unless P=NP" seemed complexity theory to me. ps: I haven't said it is not mainstream db theory.  
> **username_1**: it's an NP-hardness question, so the np-hardness label is appropriate. But the main arxiv area for this is databases, so it gets that tag. that's my reasoning.  
> **username_3**: @Suresh: I don't view them as exclusive, but I don't have a strong opinion on it.  
> **username_1**: one test is that a paper on this topic is likely to be classified under cs.DB in the arxiv.  

---

## 3 answers

### Answer by username_4 on 2011-01-18. Score: 2

It seems like this problem may be known as the *dependency inference problem*, as described in [this extended abstract](http://www.vldb.org/conf/1987/P155.PDF) of the paper ["Dependency Inference"](http://portal.acm.org/citation.cfm?id=671482) by Mannila and Raiha in VLDB '87:

> Given a relation $r$, find a set of functional dependencies that logically determines all the functional dependencies holding in $r$.

Unfortunately, it seems that this problem is intractably super-polynomial. According to the same extended abstract:

> Theorem 1. For each $n$ there exists a relation over $R$ such that
> $n = |R|$, $|r| = O(n)$, and each cover of $dep(r)$ has $\Omega(2^{n/2})$ dependencies.

In other words, you cannot guarantee that the minimal cover is sub-exponential in the size of the input.

EDIT: However, the asker is asking whether or not an *output*-polynomial algorithm exists (i.e.: an algorithm that runs in time polynomial in the size of the input and output). The nearest reference I can find is in the paper ["Identifying the Minimal Transversals of a Hypergraph and Related Problems"](http://reference.kfupm.edu.sa/content/i/d/identifying_the_minimal_transversals_of__179494.pdf), SIAM J. Computing, 1995 (24) by Eiter and Gottlob.
They first define problems AP1 and AP2 where AP2 is the dependency inference problem. Then, they state the following:

> Note that problems AP1 and AP2, which are search problems in terms of complexity theory, are solvable by algorithms in output-polynomial time only if the following decision problem, which we call FD-RELATION EQUIVALENCE, is in P:
>
> * *Problem*: FD-RELATION EQUIVALENCE
> * *Instance*: A relation $R$ and a set $F$ of FD.
> * *Question*: Does $F\_R = F^+$ hold ?
>
> FD-RELATION EQUIVALENCE is in co-NP, but there is neither a polynomial time algorithm known for this problem nor is it proved co-NP-complete.

> **Comments:**
> **username_1**: The way around this I suspect is to determine a minimal cover directly (in the sense described in my answer below). While the above theorem shows that the number of dependencies may be large, it may  be the case that the size of a minimal cover is small.  
> **username_4**: I don't have access to the underlying paper (just the linked extended abstract), but it seems that the theorem as stated implies that there exist instances where all covers -- including minimal covers -- are large.  
> **username_1**: this is correct. Later work refers to this paper as claiming the same thing. So this is an answer to the OP's question then.  
> **username_0**: The problem is to generate minimal FD cover in OUTPUT polynomial time. If there are exponential minimal FD cover it does not mean that there are no output polynomial algorithm. (output polynomial means that complexity is polynomial in ouput and input size)  
> **username_4**: Ah, sorry about that. I missed the part about output polynomial.  
> **username_0**: Thanks for the link! But it is still not an answer that I am looking for (I know about simple hsat-hardness).  
> **username_4**: Indeed. In further inconclusive investigations, it appears that this problem and several related problems (e.g.: Intersecting Monotone UNSAT) are still of undetermined complexity. Namely, it looks to me like the state of the art is that no polynomial algorithms are known nor any reductions to NP- or co-NP-completeness.  

---

### Answer by username_5 on 2011-01-13. Score: 0

I would recommend investigating the field of [Finite Model Theory](http://en.wikipedia.org/wiki/Finite_model_theory) and more particularly its sub-field [Descriptive Complexity](http://en.wikipedia.org/wiki/Descriptive_complexity). It can be used to model such sorts of problems.


---

### Answer by username_1 on 2011-01-13. Score: 0

David Maier has a [chapter on optimal covers](http://web.cecs.pdx.edu/~maier/TheoryBook/MAIER/C05.pdf) (under various notions of optimal) in his book on the theory of relational databases. He shows in there that given a set of FDs, finding a minimum cardinality cover is in P (but finding a cover of minimum description length is NP-hard)

> **Comments:**
> **username_0**: I know it. But finding minimal FDs cover by given relational database is at least hard as simple-transversal hypergraph problem (or monotone self-duality). Unlikly there are known some polynomial algorithms for it.  
> **username_1**: so you're saying that the difference is because of FDs NOT being given as part of the input ?  
> **username_0**: Yes. Input is only relational database, which is given by table (some matrix)  

---

