Курс «Базы данных»

КУРС «Базы данных» *** Тема «Концепция функциональной зависимости»

Логиче­ский проект БД совершенно независим от СУБД, и для его реализации должны использоваться строгие теоретические принципы.

Цель логического проектирования: выбрать подходящую логическую структуру для заданного массива данных, которые требуется поместить в базу данных. Нужно решить вопрос: какие необходимы базовые переменные отношения и какой набор атрибутов они должны включать.

В идеале система должна быть способна формировать физический проект автоматиче­ски, вообще не требуя вмешательства человека в этот процесс.

Функциональная зависимость является связью типа "многие к одному" между множествами атрибутов внутри данной переменной отношения. Функциональные зависимости представляют собой основу для применения научного подхода к решению целого ряда практических задач.

Для переменной отношения поставок SP существует функциональная зависимость между множествами атрибутов {S#,P#} и {QTY}.

■ Для любой заданной пары значений атрибутов S# и P# существует только одно со­ответствующее им значение атрибута QTY. ■ Но одно и то же соответствующее им значение атрибута QTY мо­гут иметь многие разные пары значений атрибутов S# и P#.

Существуют такие функциональные зависимости, которые выполняются применительно к данной переменной отношения лишь в некоторых част­ных случаях, и такие, которые выполняются применительно к ней всегда.

Пример значения переменной отношения SCP

Зна­чение переменной отношения в определенный момент (вариант а) Пусть r является отношением, а X и Y — произвольными подмножествами множества атрибутов данного отношения r. Тогда Y функционально зависимо от X (X → Y или X функционально определяет Y) тогда и только тогда, когда каждое значение множества X отношения r связано точно с одним значением множества Y отношения r.

Множество всех возможных значении, которые переменная отношения может принимать в различные моменты (вариант b) Пусть R является переменной отноше­ния, а X и Y — произвольными подмножествами множества атрибутов переменной отношения R. Тогда Y функционально зависимо от X (X → Y; X функционально определяет Y) тогда и только тогда, когда для любого допустимого значения переменной отношения R каждое значение множества X отношения R связано точно с одним значением множества Y отношения R.

Если два кортежа от­ношения r совпадают по значению X, они совпадают и по значению Y. Отношение SCP удовлетворяет требованиям сразу нескольких функ­циональных зависимостей:

Левую и правую части символической записи функциональной зависимости иногда называют, соответственно, детерминантом и зависимой частью. Когда множество содержит только один атрибут, оно называется одноэлементным множеством. В таком случае скобки м. б. исключены. (S# → CITY)

При рассмотрении самих пере­менных отношения интерес представляют не столько функциональные зависимости в их существующих на некоторый момент кон­кретных значениях, сколько функциональные зависимости, выполняющиеся для всех возможных значений данной переменной отношения. В случае переменной отношения SCP функциональная зависимость S# → CITY выполняется для всех возможных значений переменной отношения SCP, поскольку в любой момент одному поставщику соответствует в точности один город.

Практи­чески утверждение, что данная функциональная зависимость выполняется "всегда" (т. е. для всех возможных значений SCP), является ограничением целостности для переменной отношения SCP, поскольку при этом накладываются определенные ограничения на все ее допустимые значения.

Здесь SCPX и SCPY — переменные области значений, принимающие свои значения в области определения переменной отношения SCP. Выражение S# → CITY может рас­цениваться как сокращенный способ представления этой более длинной формулировки.

Пусть R (A1, A2,…, An) – схема отношения, а X и Y – подмножества {A1, A2,…, An}. Функциональная зависимость на отношении R – это утверждение вида «Если два кортежа R совпадают по атрибутам множества X⊂{ A1, A2,…, An} (т. е. эти кортежи имеют в соответствующих друг другу компонентах одни и те же значения для каждого атрибута множества X), то они должны совпадать и по атрибутам множества Y⊂{A1, A2,…, An}. Формально эта зависимость записывается выражением X → Y, причем говорится, что X функционально определяет Y.

Функциональные зависимости, которые выполняются для отношения SCP, но не "всегда" выполняются для переменной отношения SCP. S# → QTY QTY → S# Утверждение "количество деталей в каждой по­ставке данного поставщика одинаково", действительно оказалось истинным для кон­кретных значений, присутствующих в отношении SCP, но ложным для всех воз­можных допустимых значений переменной отношения SCP.

Если X является потенциальным ключом переменной отноше­ния R, то все атрибуты Y переменной отношения R должны обязательно быть функцио­нально зависимыми от X. Р# → { Р#, PNAME, COLOR, WEIGHT, CITY }

Если переменная отношения R удовлетворяет функциональной зави­симости А → B и А не является потенциальным ключом, то R обязательно будет харак­теризоваться избыточностью. Для переменной отно­шения SCP наличие в ней функциональной зависимости S# → CITY приведет к тому, что сведения о месте расположения поставщика в определенном городе повторятся много раз

Функциональные зависимости являются ограничениями целостности, поэтому жела­тельно, чтобы СУБД обеспечивала их соблюдение. Следовательно, для каждого задан­ного множества функциональных зависимостей S желательно найти такое множество T, которое (в идеальной ситуации) было бы существенно меньше множества S и при этом каждая функциональная зависимость в множестве S могла бы быть заменена функцио­нальной зависимостью из множества T.

Если бы такое множество T было найдено, то СУБД достаточно было бы контролировать выполнение функциональных зависимостей из множества T, что автоматически обеспечивало бы соблюдение всех функциональных зависимостей из множества S.

Очевидным способом сокращения существующего набора функциональных зависи­мостей является исключение из него тривиальных зависимостей. Зависимость называется тривиальной, если она не может не выполняться.

{ S#, Р# } → S# Функциональная зависимость является тривиальной тогда и только тогда, когда правая часть ее символической записи является подмножеством (не обяза­тельно строгим подмножеством) левой части.

Интуитивно это действие воспринимается как ошибочное, поскольку понятие "город поставщика" очевидным образом связано с поставщиками, а не с поставками.)

Сведения о городе, в котором находится конкретный поставщик, повторяются в отношении столько раз, сколько поставок выполняет данный поставщик. Эта избыточность приводит к другим проблемам. Например, после обновления данных о местонахождении поставщика с номером S1 в одном из кортежей может быть указан Лондон, а в другом — Амстердам.

Предметом нормализации является формализация подобных простых идей, однако это должна быть формализация, которая действительно будет иметь большое практическое значение при проектировании базы данных.

Нормализацию целесообразно понимать следующим образом: она помогает спроектировать базу данных таким образом, чтобы сделать более логически приемлемыми операции обновления отдельных кортежей, что в противном случае (т. е. когда проект базы данных не нормализован) может оказаться затруднительным. Эта цель достигается благодаря тому, что в полностью нормализованном проекте предикаты переменных отношения имеют более простой вид.

Каждый кортеж в каждом отношении содержит точно одно значение для каждого из своих атрибутов. Отношение, которое соответствует этому свойству, называется нормализованным. Следует иметь в виду, что понятие "нормализованная переменная отношения" может также относиться к нормализации более высоких уровней

Процедура нормализации предусматривает разбиение, или декомпозицию, данной переменной отношения на другие переменные отношения, при­чем декомпозиция должна быть обратимой, т. е. выполняться без потерь информации.

Вопрос о том, происходит ли утрата информации при декомпозиции, тесно связан с концепцией функциональной зависимости.

В случае а информация не утрачивается, поскольку переменные отношения SST и SC все еще содержат данные о том, что поставщик с номером S3 имеет статус 30 и находится в Париже (Paris), а поставщик с номером S5 имеет статус 30 и находится в Афинах (Athens). В случае б, напротив, некоторая информация утрачивается, поскольку оба поставщика имеют статус 30. но при этом нельзя сказать, в каком городе находится каждый из них. Иначе говоря, вторая декомпозиция не является декомпозицией без потерь.

Процесс декомпозиции на самом деле является операцией проекции. Каждая из показанных на данном рисунке переменных отношения — SST, SC и STC — в действительности является проекцией исходной переменной отношения S.

Обратимость означает, что исходная переменная отношения равна соедине­нию ее проекций.

Какие условия должны быть соблюдены для того, что­бы при обратном соединении проекций R1 и R2 можно было гарантировать получение исходной переменной отношения R? Именно для получения ответа на этот вопрос необ­ходимо обратиться к функциональным зависимостям.

Теорема Хита Пусть R{А, B, С} является переменной отношения, где А, B и C —множества атрибутов этой переменной отношения. Если R удовлетворяет функциональной зависимости А→ B, то R равна соединению ее проекций по атрибутам {А, В} и {А, С}.

Переменная отношения S может быть разбита с помощью операции декомпозиции на проекции по атрибутам {S#, STATUS} и {S#,CITY} без потери информации. S не может быть разбита без потери информации на проекции по атрибутам {S#, STATUS} и {STATUS,CITY }

Теорема Хита не дает объяснения, почему так происходит. При декомпозиции б утрачивается одна из функциональных зависимостей, т. е. функциональная зависимость S#→STATUS все еще представлена (благодаря проекции по атрибутам {S#, STATUS}), а функцио­нальная зависимость S#→CITY утрачена.

Функциональная зависимость называется: неприводимой слева, если ее левая часть "не слишком велика" (избыточна).

Функциональная засисимость как семантическое понятие. Выявление функциональных зависимостей представ­ляет собой часть процесса выяснения смысла тех или иных данных. Например, тот факт, что переменная отношения S удовлетворяет функциональной зависимости S#→CITY, по сути, означает, что каждый поставщик находится точно в одном городе.

Диаграмма функциональных зависимостей для переменных отношения S, SP и Р