# אלגוריתם למציאת מפתח מינימלי

41 views
בשיעורי בית 2 התבקשו למצוא את כל המפתחות המינימליים.

לפי התשובות שפורסמו זה נראה כאילו אין שיטה מסודרת לזה.

ראיתי שבמצגות יש אלגוריתם למציאת סגירות, אבל לא למציאת מפתח מינימלי.

יש שיטה מומלצת ?

AFAIK, we didn't learn an algorithm for doing it.

First, a couple of insights:

* Every column which is not in the right side of any FD, must be in every key (otherwise we can't get it)

* If A --> B and B --> A, they can't be both in a minimal key.

Generally, what I recommend doing is:

First, write down all the FDs, including ones that can be deduced from the initial ones you're given.

Then, start with the columns that must be in any key, and then try to add one more column at a time, and see what you get, until you get all. Then, make sure none of the columns in the key can be deduced from the other ones, and if they do, remove them, until you're left with a minimal key.

Then, rewind the process and try to pick different column to get different keys.

The relations in the test, though, would probably be much smaller than the one we were given in HW2 (probably 5 or 6 columns tops), If you'll try one or two from the past exams you'll see that finding them comes intuitively.

The process I wrote here can be formalized into an algorithm, but it would probably take a lot of time to run, so I wouldn't recommend following it blindly (Pruning it in the right spots is also a part of it)