6
$\begingroup$

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.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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'. $\endgroup$ – Suresh Venkat Jan 10 '11 at 17:10
  • $\begingroup$ 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). $\endgroup$ – MikleB Jan 10 '11 at 17:18
  • $\begingroup$ See Section 5.6 of this document (dbis.informatik.hu-berlin.de/~freytag/Maier/C05.pdf). Is this what you're looking for? $\endgroup$ – Gautam Kamath Jan 10 '11 at 17:28
  • $\begingroup$ No because we don't have set of FDs, we have only relational DB. $\endgroup$ – MikleB Jan 10 '11 at 17:33
  • $\begingroup$ @Kaveh this isn't complexity theory: it's mainstream db theor $\endgroup$ – Suresh Venkat Jan 14 '11 at 6:14
2
+50
$\begingroup$

It seems like this problem may be known as the dependency inference problem, as described in this extended abstract of the paper "Dependency Inference" 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", 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.

Improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Jan 18 '11 at 3:57
  • $\begingroup$ 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. $\endgroup$ – mhum Jan 18 '11 at 6:24
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Jan 18 '11 at 9:33
  • $\begingroup$ 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) $\endgroup$ – MikleB Jan 18 '11 at 12:12
  • $\begingroup$ Ah, sorry about that. I missed the part about output polynomial. $\endgroup$ – mhum Jan 18 '11 at 15:09
0
$\begingroup$

I would recommend investigating the field of Finite Model Theory and more particularly its sub-field Descriptive Complexity. It can be used to model such sorts of problems.

Improve this answer
$\endgroup$
0
$\begingroup$

David Maier has a chapter on optimal covers (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)

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – MikleB Jan 13 '11 at 21:35
  • $\begingroup$ so you're saying that the difference is because of FDs NOT being given as part of the input ? $\endgroup$ – Suresh Venkat Jan 13 '11 at 22:13
  • $\begingroup$ Yes. Input is only relational database, which is given by table (some matrix) $\endgroup$ – MikleB Jan 13 '11 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.