Алгоритмы нахождения первичного ключа

Лекция 16.04 и 17.04 1.1. Алгоритмы нахождения первичного ключа Следует разделять понятия первичного ключа отношения (таблицы) и универсального первичного ключа, который иначе называют суперключом. Поскольку первичный ключ отношения (таблицы) является идентифицирующим в этом отношении (таблице), то по определению функциональной зависимости первичный ключ отношения функционально определяет все атрибуты этого отношения. Первичный ключ, состоящий из минимального количества атрибутов, называется минимальным ключом. Используя минимальные первичные ключи, легче обеспечивать связи между таблицами реляционной базы данных. Аналогично универсальный первичный ключ функционально определяет все атрибуты U всех отношений базы данных. Заметим, что универсальный первичный ключ (суперключ) может совпадать с первичным ключом какого-либо отношения базы данных. Используя понятие замыкания атрибутов, можно дать формальное определение первичного ключа отношения и указать простой способ, с помощью которого можно проверить, является ли заданный набор атрибутов первичным ключом отношения или нет [ссылку см. в пособии]. Для этого нужно вычислить замыкание атрибутов для заданного набора по множеству функциональных зависимостей, справедливых на данном отношении. И, если это замыкание включает все атрибуты отношения, то такой набор может рассматриваться в качестве первичного ключа отношения. Если же замыкание любого его подмножества не дает всех атрибутов отношения, то этот набор является еще и минимальным первичным ключом. Пример. Пусть база данных состоит из четырех отношений (первичные ключи выделены): Post (PN, PIM, GOR) Det (DN, DIM, CENA) PD (PN, DN, KOL) Gorod(GOR, ST). Все множество атрибутов базы данных определяется как U = PN, PIM, ST, GOR, DN, DIM, CENA, KOL. На множестве атрибутов U определены функциональные зависимости: F = {PN  PIM, PN  GOR, PN  ST, GOR  ST, DN  DIM, DN  CENA, (PN,DN)  KOL}. Легко видеть, что для отношения Post справедливо множество зависимостей: FPost = {PN  PIM, PN  GOR}. Атрибут PN действительно является первичным ключом отношения Post, так как PN+ = PN, PIM, GOR (все множество атрибутов отношения Post). Аналогично для отношения Det: FDet = {DN  DIM, DN  CENA} и DN - первичный ключ отношения Det, так как DN+ = DN, DIM, CENA. Для отношения PD: FPD = {(PN, DN)  KOL} и (PN, DN)+ = PN, DN, KOL. Для отношения Gorod: FGorod = {GOR  ST} и GOR+ = GOR, ST. Универсальным первичным ключом в рассматриваемой базе данных является набор атрибутов (PN, DN), так как замыкание этого набора по множеству F равно полному набору атрибутов U: (PN, DN) + = PN, DN, PIM, GOR, ST, DIM, CENA, KOL = U. В рассматриваемом примере универсальный ключ совпадает с первичным ключом отношения PD. В общем случае это необязательно. В настоящее время известны два алгоритма нахождения первичных ключей: 1. Алгоритм, основанный на последовательном исключении атрибутов из полного набора атрибутов отношения и проверке полученного набора на ключ; 2. Алгоритм, основанный на полном переборе претендентов на первичный ключ, начиная с одного, затем пар атрибутов и так далее. Первый алгоритм имеет невысокую вычислительную сложность, решение находится быстро, но при этом не гарантируется нахождение минимального первичного ключа. Так как поиск первичного ключа по второму алгоритму может свестись к полному перебору вариантов, то сложность его будет выше сложности первого алгоритма. Однако данный алгоритм гарантирует нахождение минимального первичного ключа, что всегда лучше, так как упрощает реализацию базы данных за счет упрощения связей между таблицами. Пример. Найдем первичный ключ отношения R = ABCDE, на котором справедливо множество функциональных зависимостей: F = {A  C, B  C, C  D, DE  C, CE  A}. Алгоритм 1. Выбираем первого претендента на первичный ключ, представляющего собой полный набор атрибутов отношения U= ABCDE. Обозначим этот набор X = ABCDE. Удаляем из него один атрибут, например A, и вычисляем замыкание полученного нового набора: (X \ A) = (BCDE) = BCDEA = U. Здесь символ “\” обозначает операцию вычитания атрибута A из набора X. Поскольку замыкание указанного набора атрибутов дает все атрибуты U, то набор BCDE может быть ключом схемы отношения R, если никакое его подмножество, в свою очередь, не может быть ключом. Проверим это. Итак, следующим претендентом на ключ является набор X = BCDE. Удаляем из него, например, атрибут B и вычисляем замыкание атрибутов нового набора: (X \ B) = (CDE) = CDEA ≠ U. Следовательно, набор CDE не может быть первичным ключом. Возвращаем атрибут B и удаляем из набора X атрибут C. Вычисляем замыкание нового набора атрибутов: (X \ C) = (BDE) = BDECA = U. Следовательно, набор BDE может быть первичным ключом. Проверим его на минимальность. Итак, следующим претендентом на ключ является набор BDE, т.е. X = BDE. Удаляем из него атрибут D и вычисляем замыкание полученного набора атрибутов: (X \ D) = (BE) = BECAD = U. Следовательно, набор BE может быть первичным ключом. Проверим его на минимальность. Итак, X = BE. После удаления атрибута E получим (X \ E) = B = BC ≠ U, а после удаления атрибута B получим (X \ B) = E = E ≠ U. Отсюда следует, что атрибуты B и E не могут быть первичными ключами. Поэтому в качестве первичного ключа можно взять последнего претендента - набор атрибутов BE. При этом мы не можем гарантировать минимальность найденного ключа, так как при другой последовательности исключения атрибутов возможно нахождение ключа с меньшим количеством атрибутов. Алгоритм 2. Сначала проверяем на ключ одиночные атрибуты A+ = ACD ≠ U; B+ = BCD ≠ U; C+ = CD ≠ U; D+ = D ≠ U; E+ = E ≠ U. Отсюда следует, что ни один одиночный атрибут отношения R = ABCDE не может выступать в роли первичного ключа этого отношения. Затем проверяем на ключ всевозможные пары атрибутов, затем тройки атрибутов и так далее, пока не найдем набор, удовлетворяющий условиям первичного ключа. Очевидно, что найденный таким образом ключ будет минимальным. AB+ = ABCD ≠ U; AC+ = ACD ≠ U; AD+ = ADC ≠ U; AE+ = AECD ≠ U; BC+ = BCD ≠ U; BD+ = BDC ≠ U; BE+ = BECDA = U; Таким образом, BE – минимальный первичный ключ исходного отношения R. Очевидно, что приведенные выше алгоритмы также могут быть использованы и для нахождения универсального ключа реляционной базы данных, состоящей из нескольких отношений. 1.2. Эквивалентность множеств функциональных зависимостей Понятие эквивалентности множеств функциональных зависимостей атрибутов часто используется при проектировании и анализе баз данных. Укажем хотя бы два случая, когда оно может использоваться. Первый случай. При проектировании базы данных несколькими разработчиками редко удается получить одно и то же множество функциональных зависимостей на одном и том же множестве атрибутов U. Если полученные множества эквивалентны друг другу, то проектирование, скорее всего, выполнено правильно всеми разработчиками. Второй случай. Полученное множество функциональных зависимостей может по каким-то причинам не устраивать разработчика. Тогда следует перейти к другому, но эквивалентному множеству зависимостей, которое отвечало бы требованиям разработчика, иначе будет нарушена семантика базы данных. Именно этот случай мы имеем в алгоритме синтеза, который будет рассмотрен в последующих лекциях. Таким образом, можно считать, что только эквивалентные множества зависимостей, полученные на одном и том же множестве атрибутов, определяют одну и ту же семантику (смысл) данных. Пусть F и G - два множества функциональных зависимостей, заданных на одном и том же множестве атрибутов U. Множества F и G называются эквивалентными (обозначается как F  G), если равны их замыкания, т.е. F = G. Чтобы проверить, являются ли два множества F и G эквивалентными, используют следующую процедуру [ссылку см. в пособии]. 1. Для каждой зависимости (X  Y)  F проверяется ее принадлежность замыканию G. Для этого используется факт выводимости одной зависимости из других (теорема 1 пособия), а именно: вычисляется замыкание атрибутов X левой части зависимости по множеству G, и проверяется условие Y  X. Если оно выполняется, то (X  Y)  G. Если каждая зависимость из F удовлетворяет этому условию, то можно указать следующую цепочку вложений множеств: F  F  G. 2. Аналогично для каждой зависимости (P  Q)  G проверяется ее принадлежность F. Если каждая зависимость из G удовлетворяет условию (PQ)  F, то можно указать следующую цепочку вложений множеств: G  G  F. Очевидно обе цепочки вложений могут одновременно выполняться только при условии F = G, т.е. множества функциональных зависимостей F и G эквивалентны. Другими словами, два множества функциональных зависимостей F и G, определенные на одном и том же наборе атрибутов U, эквивалентны тогда и только тогда, когда каждая зависимость из F логически следует из G и наоборот, каждая зависимость из G логически следует из F. Как только найдется зависимость, для которой это условие не выполняется, то дальнейшая проверка не проводится, и делается вывод о неэквивалентности заданных множеств зависимостей. Пример. Проверим эквивалентность множеств функциональных зависимостей F = {A  BC, A  D, CD  E} и G = {A  BCE, A  BD, CD  E}. Прежде чем решать вопрос об эквивалентности заданных множеств зависимостей, нужно проверить, на одном и том же множестве атрибутов заданы данные множества или нет. Легко увидеть, что множества F и G определены для одного и того же набора атрибутов U = ABCDE. Кроме того, зависимость CD  E присутствует как в множестве F, так и в множестве G, поэтому из проверки может быть исключена. Как было сказано выше, эквивалентность множеств зависимостей проверяется за два шага. 1. Для каждой зависимости (X  Y)  F проверяем ее принадлежность замыканию G, то есть справедливость выражения (X  Y)  G. Если это выражение справедливо, то исследуемая зависимость или содержится в G или выводится из G. Для (A  BC)  F имеем A(по G) = ABCED и BC  A. Поэтому по факту выводимости (A  BC) G. Для (A  D)  F имеем A(по G) = ABCED и D  A. Поэтому (A  D)  G. 2. Для каждой зависимости (P  Q)  G проверяем справедливость выражения (P  Q)  F. Для (A  BCE)  G имеем A(по F) = ABCDE и BCE  A. Поэтому (A  BCE)  F. Нетрудно проверить, что зависимость A  BD также принадлежит замыканию F. Следовательно, F = G и множества F и G эквивалентны. Пример. Проверим эквивалентность множеств функциональных зависимостей F = {A  BC, A  D, CD  E} и G = {A  BE, A  B, C  ED}. Убеждаемся, что множества зависимостей заданы на одном и том же множестве атрибутов U = ABCDE. Делаем первый шаг. 1. Для каждой зависимости (X  Y)  F проверяем ее принадлежность замыканию G, то есть справедливость выражения (X  Y)  G. Для (A  BC)  F имеем A(по G) = ABE и BC ⊈ A. Поэтому (A  BC)  G. Следовательно, дальнейшую проверку делать не надо, а сразу делаем вывод о неэквивалентности заданных множеств функциональных зависимостей. Понятие эквивалентности множеств функциональных зависимостей дает возможность замены исходного множества F другим, эквивалентным ему множеством зависимостей G без искажения семантики данных. 1.3. Покрытия Если множества F и G эквивалентны, то говорят, что F покрывает множество G, и наоборот, G покрывает F. В теории реляционных структур рассматривается несколько видов покрытий: • каноническое; • неизбыточное, или безызбыточное; • минимальное; • минимальное каноническое. Определим каждое из них. Множество функциональных зависимостей F называется каноническим покрытием [пособие], если оно удовлетворяет следующим трем условиям: 1) правая часть каждой зависимости из F содержит единственный атрибут; этого всегда можно добиться, используя правило декомпозиции правой части зависимости (см. предыдущую лекцию и контрольные задания к ней); 2) ни одна функциональная зависимость в F не является “лишней”, т.е. ни для какой зависимости (X  Y)  F множества F и F \ {X Y} не являются эквивалентными (здесь, как и прежде, знак “\” означает вычитание, в данном случае вычитание зависимостей); очевидно, “лишней” будет зависимость, которую можно вывести из остальных зависимостей. 3) ни один атрибут в левой части любой зависимости из F не является “лишним”. Зависимости без “лишних” атрибутов слева называют элементарными. Так, например, если X = AZ, X ≠ Z и (F \ {X  Y})  {Z  Y}  F, то атрибут A в зависимости X  Y является “лишним” и его можно удалить. Каноническое покрытие представляет только академический интерес, но не дает никаких преимуществ при реализации базы данных. Использование же неизбыточного и минимального покрытий при проектировании могут обеспечить эффективность реализации базы данных. Рассмотрим их подробнее. Множество функциональных зависимостей без “лишних” зависимостей, называется неизбыточным покрытием исходного множества зависимостей F, которое будем обозначать F0. Например, пусть F = {AB  C, A  B, B  C} Нетрудно показать, что множество G = {AB  C, A  B, B  C, A  C} эквивалентно F, но избыточно (зависимость A  C – “лишняя”, так как транзитивно выводится из зависимостей A  B и B  C). Кроме того, “лишней” оказывается и зависимость AB  C, так как она выводится из зависимостей A  B и B  C (Пополняем атрибутом B зависимость A  B. Получаем AB  B. Используя еще зависимость B  C, транзитивно получаем AB  C). Тогда множество F0 = {A  B, B  C} является неизбыточным покрытием как F, так и G. Множество функциональных зависимостей F называется минимальным, если оно содержит не больше F - зависимостей, чем любое эквивалентное ему множество зависимостей [ссылку см. в пособии]. В базах данных F - зависимости способствуют обеспечению целостности данных. Меньшее число F - зависимостей предпочтительнее, так как при этом используется меньший объем памяти и производится меньшее количество различных проверок при модификации данных, а потому гарантируется более быстрое исполнение алгоритмов. При проектировании базы данных методом синтеза, который будет подробно рассмотрен в последующих лекциях, каждая зависимость определяет отношение (таблицу). Поэтому стремление получить минимум зависимостей вполне оправдано, так как получим минимум таблиц. Однако в литературе по базам данных не содержится указаний не только на способы построения минимальных покрытий, но даже на проверку минимальности. В работе [ссылку см. в пособии] предлагается способ вычисления минимальных покрытий при одном частном случае функциональной определенности. Очевидно, в общем случае для построения минимальных покрытий, как и для получения оптимальных решений, требуются алгоритмы высокой вычислительной сложности. На практике часто оптимальные решения заменяются подоптимальными, которые получить гораздо проще, а по своим характеристикам они часто незначительно уступают оптимальным решениям. При проектировании реляционных баз данных таким подоптимальным решением можно считать неизбыточное покрытие. Однако использование неизбыточных покрытий – не единственный способ уменьшения таблиц в проектируемой базе данных. Минимизировать количество таблиц реляционной базы данных можно следующими способами: • построением неизбыточных покрытий; • удалением “лишних” атрибутов в левых частях зависимостей; • выявлением эквивалентных зависимостей. Все перечисленные способы используются в методе синтеза. Рассмотрим каждый из этих способов подробнее. 1.3.1. Построение неизбыточных покрытий Построение неизбыточного покрытия рассмотрим на следующем примере. Пример. Пусть U = ABC и F = {A  B, B  A, C  A, A  C, B  C}. Попытаемся построить неизбыточное покрытие F, то есть множество без “лишних” зависимостей. Выберем направление просмотра зависимостей сначала слева – направо, а затем справа – налево и покажем, что различный порядок просмотра зависимостей из F может привести к разным результатам. Просматриваем зависимости из F слева - направо. Для получения результата зависимости выводить не будем, а будем использовать факт выводимости конкретной зависимости из остальных зависимостей (теорема 1 из пособия). Первая зависимость слева A  B. Для зависимости A  B строим замыкание A (левой части этой зависимости) по множеству остальных зависимостей из F, т.е. зависимостей без A  B: F \ {A  B} = {B  A, C  A, A  C, B  C}. Здесь символ “\” означает вычитание, в данном случае вычитание зависимостей. Получим A = AC. Так как правая часть зависимости B  A , то зависимость A  B не является “лишней”, то есть она не выводится из остальных зависимостей из F. Оставляем эту зависимость. Для следующей зависимости B  A имеем B = BCA. Так как A  B, то зависимость B  A – “лишняя”. Удалим ее из F. Получим новое множество F1 = {A  B, C  A, A  C, B  C}. Для следующей зависимости C  A имеем C = C. Зависимость не является “лишней”. Оставляем ее. Для зависимости A  C имеем A = ABC и C  A . Зависимость является “лишней”. Удалим ее из F1. Получим F2 = {A  B, C  A, B  C}. Проверяем последнюю зависимость B  C. Для зависимости B  C имеем B = B и C  B. Зависимость не является “лишней”. Таким образом, получили неизбыточное покрытие множества F в виде F0 (слева - направо) = {A  B, C  A, B  C}. Просматривая зависимости в исходном множестве F справа - налево и удаляя “лишние” зависимости, как было сделано выше, получим неизбыточное покрытие F в виде F0 (справа - налево) = {A  B, B  A, C  A, A  C}. Видно, что полученные множества не совпадают и имеют разное количество зависимостей, т.е. выбор направления просмотра зависимостей влияет на результат. Существует ли процедура построения неизбыточного покрытия, которая давала бы одинаковый результат независимо от направления просмотра зависимостей? Эта задача успешно решается, если воспользоваться понятием расширенного множества зависимостей. Расширение касается правых частей каждой зависимости из F. Поскольку расширяется каждая зависимость, то количество зависимостей исходного и расширенного множеств одинаково. Расширенное множество зависимостей строится по правилу: ℱ = {(Xi  Ỹi) (Xi  Yi)  F, Ỹi = Xi+ \ Xi}, где символ “” означает “при условии”, а символом “\”, как и всюду выше, обозначена операция вычитания (здесь имеется в виду вычитание множеств атрибутов). Это означает, что правая часть Ỹi каждой зависимости расширенного множества содержит все атрибуты из U, зависимость которых от атрибутов левой части X следует из F. Это означает следующее: чтобы расширить зависимость из F, надо в правую часть этой зависимости включить все зависимые атрибуты, т.е. построить замыкание атрибутов левой части. Поэтому, если левые части каких-либо зависимостей из F совпадают, то и их правые части в расширенном множестве также будут совпадать. Так удается легко выявить “лишние” зависимости с одинаковой левой частью. Вычеркнув найденные таким образом “лишние” зависимости, получаем множество ℱ0, в котором могут остаться лишние зависимости с разными левыми частями. Поэтому множество ℱ0 будем называть условно неизбыточным или псевдонеизбыточным покрытием F. Далее можно осуществить поиск в множестве ℱ0 “лишних” зависимостей так, как было выполнено в предыдущем примере, результат которого уже не будет зависеть от направления просмотра зависимостей. Удаляя “лишние” зависимости, легко получаем неизбыточное покрытие множества F, которое в общем случае не является каноническим. В некоторых частных случаях оно может быть и минимальным покрытием. Если условно неизбыточное покрытие ℱ0 содержит большое количество зависимостей, то обычная процедура поиска “лишних” зависимостей может оказаться утомительной. Можно показать, что часть оставшихся “лишних” зависимостей будет находиться среди так называемых эквивалентных зависимостей. Процедура с использованием эквивалентных зависимостей будет подробно описана при изложении метода синтеза. Построим расширенное множество зависимостей для только что рассмотренного примера. Итак, исходное множество F = {A  B, B  A, C  A, A  C, B  C}. Расширяем первую зависимость A  B. Для этого вычисляем замыкание атрибутов левой части зависимости: A+ = ABC. Отсюда следует (для обозначения следования, как и прежде, будем использовать символ ), что в расширенное множество будет включена зависимость A  BC. Процедуру получения расширенной зависимости будем кратко записывать так: A+ = ABC  A  BC. Для второй зависимости B  A: B+ = BAC  B  AC Для третьей зависимости C  A: C+ = CAB  C  AB Для четвертой зависимости A  C: A+ = ABC  A  BC Для пятой зависимости B  C: B+ = BAC  B  AC Таким образом, расширенное множество зависимостей будет таким: ℱ = {A  BC, B  AC, C  AB, A  BC, B  AC}. В этом множестве легко определяются “лишние” зависимости (подчеркнуты). Удалим их. В результате получим условно неизбыточное покрытие множества F, которое будет включать три зависимости: ℱ0 = {A  BC, B  AC, C  AB}. Отметим, что это множество содержит также три зависимости, как и минимальное покрытие F0 (слева - направо), но не является каноническим. 1.1.1. Проверка зависимостей на элементарность Зависимости без “лишних” атрибутов слева называются элементарными. Следующий пример показывает, как можно привести зависимости к элементарному виду. Пример. Пусть множество функциональных зависимостей F = {ABE  C, A  B, B  A} задано на множестве атрибутов U = ABCE. Очевидно, анализу на элементарность должны подвергаться зависимости, в левой части которых содержится несколько атрибутов. В данном примере такой зависимостью является ABE  C. Остальные зависимости уже являются элементарными. Попытаемся исключить атрибут A из зависимости ABE  C, т.е. проверим справедливость зависимости BE  C. Для этого, используя факт выводимости зависимости, вычислим (BE) = BEAC. Правая часть этой зависимости C  (BE). Следовательно, зависимость BE  C выводится из F, то есть (BE  C)  F, и атрибут A можно исключить. В результате множество F можно заменить на F1 = {BE  C, A  B, B  A}. Рассмотрим теперь полученную зависимость BE  C и попытаемся исключить из нее атрибут B. Чтобы это можно было сделать, установим справедливость зависимости E  C. Так как E = E и C  E, то делаем вывод о невозможности исключения B. Возвращаем B. Попытаемся теперь из зависимости BE  C исключить атрибут E, то есть установить справедливость зависимости B  C. Так как B = BA и C  B, то делаем вывод о невозможности исключения атрибута E. Таким образом, окончательно имеем F1 = {BE  C, A  B, B  A}. Множество F1 содержит только элементарные зависимости, но количество зависимостей не уменьшилось. Нетрудно показать, что множества F и F1 эквивалентны. В рассмотренной процедуре порядок просмотра зависимостей также влияет на результат. Формальная процедура, оптимизирующая этот процесс, в настоящее время неизвестна. Однако известна рекомендация о первоочередном анализе на избыточность атрибутов той зависимости, которая содержит наибольшее количество атрибутов в левой части. В следующем примере показано, как приведение зависимостей к элементарному виду, может уменьшить количество зависимостей. Пример. Пусть множество функциональных зависимостей F = {L  KA, A  DOXZC, DEM  K, D  EK} справедливо на множестве атрибутов U = ACDEKLMOXZ. Здесь все зависимости, кроме DEM  K являются элементарными. Поэтому надо исследовать только эту зависимость. Проверим зависимость DEM  K на элементарность. Пытаемся из анализируемой зависимости исключить атрибут D. Используя факт выводимости, установим справедливость зависимости EM  K. Так как EM+ = EM и K EM+, то делаем вывод о невозможности исключения D. Возвращаем D. Пытаемся теперь из зависимости DEM  K исключить атрибут E, т.е. проверяем справедливость зависимости DMK. Так как DM+ = DMEK и K DM+, то атрибут E можно исключить. В результате множество F можно заменить на F1 = {L  KA, A  DOXZC, DM  K, D  EK}. Продолжаем процесс исключения атрибутов теперь уже из зависимости DM  K. Пытаемся исключить из этой зависимости атрибут M. Так как D+ = DEK и K D+, то атрибут M можно исключить. В результате множество F1 можно заменить на F2 = {L  KA, A  DOXZC, D  K, D  EK}. Поскольку зависимость D  K получается из декомпозиции правой части зависимости D  EK, то D  K является лишней и ее можно исключить из F2. Таким образом, вместо F окончательно имеем множество F3 = {L  KA, A  DOXZC, D  EK}, которое содержит меньше зависимостей, чем исходное множество F. Нетрудно показать, что множества F и F3 эквивалентны. 1.1.1. Поиск эквивалентных зависимостей Используя понятие эквивалентности зависимостей, можно также уменьшить количество зависимостей в исходном множестве. Рассмотрим, почему это происходит. Зависимости Xi  Yi и Xj  Yj будем называть эквивалентными, если (Xi  Yi) = (Xj  Yj) . Например, эквивалентными будут зависимости A  BCD и AB  CD. Набор эквивалентных между собой зависимостей называют классом эквивалентности. Очевидно, зависимости из одного класса эквивалентности дадут схемы отношений с одинаковым набором атрибутов. Если каждой зависимости будет соответствовать таблица в базе данных, то эквивалентные зависимости дадут таблицы с одинаковым набором полей. Иметь в базе данных несколько таблиц с одинаковым набором полей бессмысленно. В этом случае целесообразно в каждом классе эквивалентности оставлять одного (почти всегда любого) представителя. Пример. Пусть множество функциональных зависимостей F = {A  BCD, CDА  B, C  EMK, KMС  E, E  B} справедливо на множестве атрибутов U = ABCDEKM. Легко заметить, что множество F содержит два класса эквивалентности (один класс выделен красным цветом, другой – фиолетовым). Оставляем одного, в данном случае любого представителя в каждом классе эквивалентности. Поскольку в методе синтеза левые части зависимостей определяют первичные ключи таблицы, то в рассматриваемом примере оставляем в качестве представителей классов эквивалентности зависимости с одиночными атрибутами в левых частях. В результате получаем новое множество зависимостей: F1 = {A  BCD, C  EMK, E  B}, которое содержит меньше зависимостей, чем исходное множество F. Нетрудно показать, что множества F и F1 эквивалентны.