II.5. Функционални зависимости

II. Специализирана част · Тема 5 · Подготовка по конспекта на СУ / ФМИ № 19, 2026/2027

Обхват от конспекта

Функционални зависимости. Определение за функционална зависимост. Ключове на релациите. Суперключове. Откриване на ключовете в релациите. Правила за функционалните зависимости. Правило за разделяне/ комбиниране. Тривиални функционални зависимости. Правила на транзитивността. Покриващи множества на функционалните зависимости. Проекция на функционалните зависимости.

Цел на подготовката

Да можеш самостоятелно да обясниш понятията и връзките между тях, да дадеш собствен пример и да приложиш изброените подходи в задача.

Примерна писмена разработка

Авторски образец за подготовка по тази тема. Не е официален отговор, утвърден от СУ, и не задава задължителен обем или схема за оценяване. Чети го за разбиране; упражнявай възпроизвеждане със собствени примери и сверявай с пълния обхват на конспекта.

Функционални зависимости и ключове

Функционална зависимост X→Y върху схема R е ограничение: във всеки допустим екземпляр два кортежа, съвпадащи по X, трябва да съвпадат и по Y. X и Y са множества от атрибути. Зависимостта изразява семантично правило, а не причинност или физически ред. Наличието ѝ в малка извадка не доказва, че тя е закон на предметната област.

Множество K е суперключ, ако K определя всички атрибути на R; то е кандидат-ключ, ако никое негово собствено подмножество не е суперключ. Възможни са няколко кандидат-ключа. Например при R(A,B,C,D) и зависимости A→B, B→C, AC→D затварянето на A включва A, после B, C и D, затова A е ключ. Не бива да се бърка първичният ключ, избран при реализацията, с множеството на всички кандидат-ключове.

Правила и алгоритми

Основни правила за извеждане са аксиомите на Армстронг: рефлексивност — ако Y⊆X, тогава X→Y; допълване — от X→Y следва XZ→YZ; транзитивност — от X→Y и Y→Z следва X→Z. Те са коректни и пълни за функционалните зависимости. Производни правила са обединяване, разделяне и псевдотранзитивност. Например X→AB е еквивалентно на X→A и X→B. Подобно разделяне на лявата страна по принцип не е допустимо.

Зависимостта е тривиална, когато Y⊆X. За нетривиалните зависимости се изследва дали добавят ограничения. Затварянето X⁺ спрямо F се намира чрез първоначално X⁺=X и многократно добавяне на десните страни на зависимостите, чиито леви страни вече са включени. Процесът спира, когато няма промяна. Така X→Y следва от F точно когато Y⊆X⁺. За откриване на ключове се търсят минимални множества, чието затваряне е цялата схема; атрибутите, които никога не се срещат вдясно, трябва да участват във всеки ключ.

Покрития и проекции

Две множества зависимости са еквивалентни, ако извеждат едни и същи зависимости. Покритието заменя дадено множество с еквивалентно. Минималното покритие обичайно има единични десни страни, няма излишни атрибути в левите и няма излишни зависимости. То не е непременно единствено. Премахване на атрибут или зависимост се допуска само след проверка за запазване на еквивалентността.

Проекцията на F върху подмножество атрибути S включва всички зависимости върху S, които следват от F, а не само записаните в първоначалния списък. Ако A→B и B→C, проекцията върху AC включва A→C, въпреки че B отсъства. Точното извеждане на зависимости и ключове е необходима основа за доказване на нормални форми и коректни декомпозиции.

Литературна опора

Основен източник за сверяване: Garcia-Molina, Ullman, Widom, Database Systems: The Complete Book, второ издание, раздели 3.1–3.2. Учебник, официални материали и библиография. Примерите и изложението тук са авторски, а не превод на учебника.

Уроци за четене

  1. 41. Функционална зависимост: един атрибут определя друг
  2. 42. Няколко атрибута заедно определят стойност
  3. 43. Ключ на релация: определя целия ред и е минимален
  4. 44. Суперключ и ключ: достатъчност и минималност
  5. 45. Кандидатни ключове и избор на първичен ключ
  6. 46. Разделяне и обединяване на функционални зависимости
  7. 47. Тривиални зависимости и разширяване
  8. 48. Транзитивност: зависимости по верига
  9. 49. Затваряне на множество атрибути
  10. 50. Намиране на всички кандидатни ключове
  11. 51. Защо затварянето е надеждна проверка
  12. 52. Еквивалентни множества зависимости и покритие
  13. 53. Минимално покритие на зависимости
  14. 54. Проектиране на функционални зависимости
  15. 55. Функционални зависимости: свързана задача

Примерната писмена разработка по-горе обобщава темата. Уроците развиват подточките на малки стъпки: понятия, пример, чертеж, точно четене и самостоятелна задача.

Литература

Библиографски сведения и източници · Официален конспект. Конкретните раздели и печатни/PDF страници са посочени във всеки урок; основният източник е СУ 11, второ издание.

Примери и упражнения

Уроци 41–55 съдържат самостоятелни задачи. Всяко условие повтаря необходимите данни, правила и означения. Решавай ги последователно; при преговор можеш да отвориш отделна задача без да търсиш нейни данни другаде.

Проверка на знанията

Към всеки от уроци 41–55 има четири въпроса и авторски отговори в затворени карти. Първо реши задачата, после сравни разсъждението си с отговора. Учебният речник разграничава термините според контекста.

Писмена разработка и устни въпроси

Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:

  1. Въведение: предмет, предназначение и място на темата.
  2. Точни определения, означения и основни понятия.
  3. Последователно изложение на подточките от конспекта и връзките между тях.
  4. Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
  5. Важни свойства, ограничения, сравнения и типични грешки.
  6. Кратко обобщение.

Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.