Welcome to TDBSoverflow, Our class's own StackOverflow. Our rules:
  1. Use only meaningful and self-explanatory titles
  2. Tag your questions with meaningful keywords
  3. Use upvotes and downvotes to rate the answers
  4. When you receive a satisfying answer - Click the "V" button
Remember: you may get up to 5 bonus points to your final grade!

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

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

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

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

יש שיטה מומלצת ?
asked Feb 2, 2018 by tikitak (2,970 points)

1 Answer

+2 votes
 
Best answer

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)

Hoping that was helpful; feel free to ask follow up questions if you still have any.

answered Feb 2, 2018 by Assaf (31,090 points)
selected Feb 2, 2018 by tikitak
...