Посторонние атрибуты

Посторонние атрибуты Если F – неизбыточное множество F–зависимостей, то его уже нельзя удалением целых F–зависимостей, однако может оказаться, что размер можно уменьшить удалением части атрибутов из отдельных F–зависимостей. Пусть F – множество F–зависимостей над схемой R и XY есть F–зависимость из F. Атрибут A из R называется посторонним в XY относительно F, если выполняется одно из следующих двух условий: 1. X=AZ, XZ и (F-{XY}){ZY}F 2. Y=AW, YW и (F-{XY}){XW}F Иными словами, A – посторонний атрибут в XY, если он может быть удален из правой или левой частей XY без изменения замыкания F. Пример: Пусть G={ABС, BС, ABD}. Атрибут C является посторонним правой части ABС, а атрибут B – в левой части ABD. Ф–зависимость XY называется редуцированной слева, если X не содержит атрибута A, постороннего в XY. Ф–зависимость XY называется редуцированной справа, если Y не содержит атрибута A, постороннего в XY. Зависимость называется редуцированной, если она редуцирована слева и справа и Y. Множество Ф–зависимостей F называется редуцированным (слева, справа), если каждая Ф–зависимость из F редуцирована (соответственно слева, справа). Пример: Множество G={ABС, BС, ABD} не является редуцированным ни слева, ни справа. Множество G1={ABС, BС, AD} редуцировано слева. Множество G2={AB, BС, ABD} редуцировано справа. Множество G3={AB, BС, AD} редуцировано. После удаления посторонних атрибутов из левых частей множества Ф–зависимостей всегда образуется более сильное множество Ф–зависимостей, поэтому редуцирование всегда начинают с левых частей. Алгоритмы редуцирования множества функциональных зависимостей слева и справа: LEFTRED и RIGHTRED. Алгоритм LEFTRED. Вход: множество F–зависимостей G. Выход: редуцированное слева покрытие G. FUNCTION LEFTRED PARAMETERS G F=G FOR каждая Ф–зависимость XY из G FOR каждый атрибут A из X IF MEMBER(F,(X-A)Y) удалить A из X в XY из F ENDIF ENDFOR ENDFOR RETURN F Алгоритм RIGHTRED. Вход: множество F–зависимостей G. Выход: редуцированное справа покрытие G. FUNCTION RIGHTRED PARAMETERS G F=G FOR каждая Ф–зависимость XY из G FOR каждый атрибут A из Y IF MEMBER(F-{XY} {X(Y-A)},XA) удалить A из Y в XY из F ENDIF ENDFOR ENDFOR RETURN F Алгоритм REDUCE. Вход: множество F–зависимостей G. Выход: редуцированное покрытие G. FUNCTION REDUCE PARAMETERS G F=RIGHTRED(LEFTRED(G)) удалить из F все F–зависимости вида X RETURN F Множество F–зависимостей называется каноническим, если F редуцировано слева и неизбыточно и каждая его F–зависимость имеет вид XA. Пример: Для множества G={ABСE, ABDE, BIJ} каноническим покрытием является множество F={AB, AС, AD, AE, BIJ}. Редуцированное и каноническое покрытие всегда эквивалентны. Если F – редуцированное покрытие, то получить каноническое покрытие можно, расщепляя каждую Ф–зависимость XA1…Am на XA1, XA2, …, XAm. Обратное преобразование состоит в объединении всех F–зависимостей с совпадающими левыми частями. Ориентированные ациклические графы вывода Ориентированный ациклическй граф (DA-граф) – это ориентированный граф, не имеющий циклов ни в одной вершин. Помеченный DA-граф – это DA-граф, каждой вершине которого поставлен в соответствие некоторый элемент из множества меток L. Пусть F – множество Ф-зависимостей над схемой R. DA-графом вывода над F называется ориентированный ациклический граф, помеченный символами атрибутов из R и построенный по следующим правилам: R1: Любое множество изолированных вершин с метками из R является DA-графом вывода над F. R2: Пусть H есть DA-граф вывода над F, содержащий вершины v1, v2, …, vk с метками A1, A2, …, Ak, и A1, A2, …, Ak  CZ есть F-зависимости в F. Построим H’, добавив к H вершину u, помеченную C, и дуги (v1,u), (v2,u), …, (vk,u). H’ является DA-графом вывода над F. R3: Никакой другой граф не является DA-графом вывода над F. В дальнейшем DA-граф вывода над F будем называть DDA-графом над F. Любой DDA-граф над F строится с помощью однократного применения правила R1 и некоторого числа применений правил R2. Пример: Пусть F={ABE, BEI, EG, GIH}. Этапы построения DDA-графа над F: 1. Применяем правило R1 2. Применяем правило R2 для ABE 3. Применяем правило R2 для EG 4. Применяем правило R2 для BEI, GIH Если H есть DDA-граф над v, то вершина v в H называет начальной вершиной, если v не имеет никаких входящих в нее дуг. Любую начальную вершину следует добавлять к H c помощью правила R1. Пусть H есть DDA-граф над F. Граф H называется графом для XY, если: D1: X является множеством меток начальных вершин. D2: Каждый атрибутY является меткой какой-нибудь вершины в H. Используемым множеством DDA-графа H над F (обозначается U(H)) называется множество всех F-зависимостей в F, использованных при применении правила R2 во время построения DDA-графа. Пример: на рис. DDA-граф над F для ABGH. U(H)={ABE, BEI, EG, GIH }. Начальные вершины: A и B. Помеченный направленный ациклический граф – это геометрический способ описания RAP-последовательности вывода, т.е. если дана RAP-последовательность вывода для XY, то можно построить DDA-граф над F для XY и наоборот. Другими словами, существует естественное соответствие между B-аксиомами, правилами построения DDA-графа над F для XY. Аксиома B1 соответствует правилу R1 построения DDA-графов. Аксиома B2 соответствует правилу R2. Аксиома B3 содержится в условии D2 определения DDA-графа для XY. Пример: DDA-графа над F для ABGH, может быть построен из RAP-последовательности вывода. Структура неизбыточных покрытий Любые два неизбыточных покрытия F и G некоторого множества F–зависимостей, помимо того, что FG, имеют также определенное сходство структур, а именно: для каждой левой части X в F–зависимости из F существует эквивалентная ей левая часть V в F–зависимости из G. При этом два множества атрибутов X и V считаются эквивалентными относительно множества Ф–зависимостей, когда последнее влечет как XV, так и V X (это обозначается так: XV). Пример: Пусть F={ABC, BA, ADE} и G={AABC, BA, BDE}. Множества F и G неизбыточны и эквивалентны друг другу. Эквивалентные множества атрибутов: AA, BB, ADBD. 1) Пусть F – множество Ф-зависимостей над схемой R, а X – множество атрибутов XR. 2) Обозначим EF(X) – подмножество Ф-зависимостей из F c левой частью, эквивалентной X. 3) Обозначим EF множество {EF(X) | XR и EF(X)}, которое является разбиением F на классы с эквивалентными левыми частями. Очевидно, что если в F не существует ни одной F-зависимости с левой частью, эквивалентной X, то EF(X) пусто. Утверждение: Если заданы эквивалентные неизбыточные множества F и G, то EF(X) не пусто тогда и только тогда, когда не пусто EG(X). Таким образом, EF содержит то же число множеств, что и EG. Это записывается таким образом: |EF|=|EG|. Множество всех левых частей EF(X) обозначается как eF(X). Пример: Пусть F={ABC, BA, ADE} и G={AABC, BA, BDE}, тогда множество EF имеет вид: EF(A)={ABC, BA}, EF(AD)={ADE}; множество EG имеет вид: EG(A)={AABC, BA}, EG(BD)={BDE}. Пример: Рассмотрим список автодорожных нарушений, представленный в виде отношения НАРУШЕНИЯ(Автомобиль, Удостоверение, Владелец, Дата, Время, Квитанция, Проступок). Одним из минимальных покрытий множества Ф-зависимостей для этого отношения является F={Автомобиль(Удостоверение, Владелец), УдостоверениеАвтомобиль, Квитанция(Удостоверение, Дата, Время, Проступок), (Удостоверение, Дата, Время)(Квитанция, Проступок)}. Эквивалентное минимальное множество F-зависимостей G={АвтомобильУдостоверение, Удостоверение(Автомобиль, Владелец), Квитанция(Автомобиль, Владелец, Дата, Время), (Автомобиль, Дата, Время)(Квитанция, Проступок)}. множество EF имеет вид: EF(Удостоверение)={ Автомобиль(Удостоверение, Владелец), УдостоверениеАвтомобиль}, EF(Квитанция)={ Квитанция(Удостоверение, Дата, Время, Проступок), (Удостоверение, Дата, Время)(Квитанция, Проступок)}; множество EG имеет вид: EG(Удостоверение)={АвтомобильУдостоверение, Удостоверение(Автомобиль, Владелец)}, EG(Квитанция)= { Квитанция(Автомобиль, Владелец, Дата, Время), (Автомобиль, Дата, Время)(Квитанция, Проступок)}. Для заданного множества Ф-зависимостей G подмножество X прямо определяет Y относительно G, если для Ф-зависимости XY существует неизбыточное покрытие F множества G, обладающее DDA-графом H над F, таким, что U(H)EF(X)= (обозначение XY). Другими словами, можно найти для G неизбыточное покрытие F, в котором XY выводима только из Ф-зависимостей, принадлежащих F-EF(X). Заметим, что всегда имеет место XX, что XY влечет XY и что EF(X) может быть пусто. Кроме того, AB имеет место только при A=B. Пример: Пусть G=F={ACD, ABE, BI, DIJ}. Тогда, как видно из DDA-графа ABJ относительно G. Множество EF(AB)={ABE}; U(H)={AСD, BI, DIJ}. Минимальные, оптимальные и кольцевые покрытия. Множество Ф-зависимостей F минимально, если оно содержит не больше F-зависимостей, чем любое эквивалентное множество F-зависимостей. Очевидно, что минимальное множество не может содержать избыточных зависимостей, то есть оно одновременно и неизбыточно. Пример: Множество G={ABC, BA, ADE, BDJ} неизбыточно, но не минимально, поскольку существует множество F={ABC, BA, ADEJ}, которое эквивалентно G и содержит меньшее число Ф-зависимостей. Множество F является минимальным покрытием G. Покрытия можно оценивать не только количеством содержащихся F-зависимостей, но и числом входящих в них атрибутов. Например, множество G={ABCD, ABE, EAB} согласно такой оценке имеет размерность 10. Множество F-зависимостей F оптимально, если не существует эквивалентного множества с меньшим числом атрибутных символов. Пример: Множество F={ECD, ABE, EAB} является оптимальным покрытием для G={ABCD, ABE, EAB}. Заметим, что G редуцировано и минимально, но не оптимально. Оптимальное множество Ф-зависимостей всегда редуцировано и минимально. После того, как множество Ф-зависимостей разделено на классы с эквивалентными левыми частями, информацию каждого класса эквивалентности можно представить одной обобщенной Ф-зависимостью. Составная функциональная зависимость (СF-зависимость) имеет вид (X1, X2, …, Xk)Y, где X1, X2, …, Xk и Y различные подмножества схемы R. Отношение r(R) удовлетворяет CF-зависимости. (X1, X2, …, Xk)Y, если оно удовлетворяет F-зависимостям XiXj и XiY, 1i,jk. В этой записи (X1, X2, …, Xk) называется левой частью, X1, X2, …, Xk – левыми множествами, а Y – правой частью. CF-зависимости есть не более чем сокращенный способ записи множества Ф-зависимостей с эквивалентными левыми частями. Допускается, что Y=. В этом случае CF-зависимость записывается в виде (X1, X2, …, Xk). Пусть G – множество CF-зависимостей над R, а F – множество F- или CF-зависимостей над R. GF, если каждое отношение r(R), удовлетворяющее G, удовлетворяет F и обратно. Это определение согласуется с эквивалентностью для множеств F-зависимостей. Множество F является покрытием G, если GF, где F и G состоят либо из множеств F-зависимостей и множеств CF-зависимостей, либо из множеств одного из этих видов. Пример: Множество CF-зависимостей G={(A,B),(AC,BC)DE} эквивалентно множеству F-зависимостей F={AB, BA, ACD, BCE}. Тематика задания: расписать множество CF-зависимостей в виде F-зависимостей. Множество F-зависимостей называется характеристическим множеством для CF-зависимости, если F{(X1, X2, …, Xk)Y}. Если каждое левое множество из CF-зависимости используется в качестве левой части F-зависимости в точности один раз, т.е. имеет вид {X1Y1, X2Y2, …, XkYk), то F называется естественным характеристическим множеством для F-зависимости. Другое характеристическое множество, соответствующее, по определению, CF-зависимости – это {X1X2, X2X3, …, XkX1Y}, которое является естественным и его структуре подмножеств обязан своим происхождением термин кольцевое множество. Кольцевое множество Множество CF-зависимостей F называется кольцевым, если не существует различных левых множеств X и Z, таких, что XZ в F. Для заданного множества F-зависимостей G можно найти кольцевое покрытие с не более чем |EF| CF-зависимостями, где F – неизбыточное покрытие множества G. Все F-зависимости из одного EF(X) можно объединить в одну CF-зависимость. Пример: Пусть G=F={ABC, BAD, AEI, BEJI}. Кольцевым покрытием множества G служит G’={(A,B)(ABCD), (AE,BE)JI}. Пусть G – множество CF-зависимостей, содержащее (X1, X2, …, Xk)Y . Пусть Xi – одно из левых множеств, а А – один из атрибутов Xi. Атрибут А называется перемещаемым, если его можно перенести из Xi в Y с сохранением эквивалентности. Левое множество Xi перемещаемо, если одновременно перемещаемы все его атрибуты. Пример: Множество G’={(A, AB, B)CD, (AE) JI} есть кольцевое покрытие для множества G={ABC, BAD, AEI, BEJI}. В (A, AB, B)CD атрибуты AB премещаемы. Результат перемещения есть G”={(A, B)ABCD, (AE) JI}. Заметим, что A в (A, AB, B)CD неперемещаемо. Кольцевое можество G неизбыточно, если из него нельзя удалить ни одну CF-зависимость без нарушения эквивалентности и, кроме того, ни одна CF-зависимость из G не содержит перемещаемых левых множеств. Множество G’ из предыдущего примера избыточно, а множество G” незбыточно. Если G – неизбыточное кольцевое множество CF-зависимостей, то объединение естественных характеристических множеств всех CF-зависимостей в G образует неизбыточное множество F-зависимостей, эквивалентное G. Пусть G – неизбытное кольцевое множество. CF-зависимость(X1, X2, …, Xk)Y называется редуцированной, если её левые множества не содержат перемещаемых атрибутов, а правые посторонних. Множество G редуцировано, если редуцирована каждая CF-зависимость в нем. Множество G минимально, если содержит столько же левых множеств, сколько любое другое эквивалентное колцевое множество. Пример: Множество G={(AB)CD, (AE)JI} является редуцированным минимальным кольцевым покрытием для множества G’={(A, AB, B)CD, (AE) JI}. Нахождение минимального кольцевого покрытия для множества F-зависимостей G начинают с нахождения о минимального покрытия, затем группируют F-зависимости с эквивалентными левыми частями в одну CF-зависимость и, наконец, выполняют ещё шаг редукции для получения редуцированного минимального кольцевого множества. РАСПИСАНИЕ ЭКЗАМЕНОВ - Код дисциплины, - Название дисциплины, -Табельный номер преподавателя – экзаменатора, -Ф.И.О. реподавателя, - Дата экзамена, - Время экзамена, - Место проведения экзамена, - Номер группы Функциональные зависимости: 1) - Код дисциплины однозначно определяет ее название. 2) - Табельный номер однозначно идентифицирует преподавателя 3) - В указанный день и время в аудитории проводится только по одной дисциплине, одним преподавателем и в одной студенческой группе. 4) - В каждой студенческой группе по каждой отдельной дисциплине принимает экзамен только один преподаватель. 5) - Преподаватель одновременно может принимать экзамен только в одной аудитории. 6) - Для каждой группы по одной дисциплине и соответствующего преподавателя однозначно определяются дата, время и место экзамена. 7) - Преподаватель одновременно может принимать экзамен только по одной дисциплине. Задания 1. Ниже приведено множество ФЗ для отношения R{A, B, C, D, E, F, G}: AB, BCDE, AEFG. Вычислите замыкание {A, C}+ для данного множества. Подразумевается ли зависимость ACFDG этим множеством? 2. Что означает понятие эквивалентности двух множеств функциональных зависимостей S1 и S2? 3. Что означает понятие неприводимости множества ФЗ? 4. Определите, эквивалентны ли два приведенных множества ФЗ для отношения R{A, B, C, D, E}: a) AB, ABC, DAC, DE; б) ABC, DAE. 5. Найдите неизбыточное покрытие приведенного ниже множества ФЗ для отношения R{A, B, C, D, E, F}: ABC, CA, BCD, ACDB, BEC, CEFA, CFBD, DEF. 6. Для отношения РАСПИСАНИЕ(D, P, C, T, L) определены перечисленные ниже атрибуты: D – день недели (1-5); P – период времени в течении дня (1-8); C – номер класса; T – имя учителя; L – название урока. Кортеж {D:d, P:p, C:c, T:t, L:l} является элементом этого отношения тогда и только тогда, когда урок l проводится учителем t в классе c в момент времени {d, p}. Предположим, что длительность всех уроков равна одному периоду времени, кроме того, каждый урок имеет название, уникальное по отношению ко всем урокам этой недели. Какие ФЗ выполняются для этого отношения? Какие потенциальные ключи существуют для этого отношения? 7. Дано отношение АДРЕС(ИМЯ, УЛИЦА, ГОРОД, ОБЛАСТЬ, ИНДЕКС), где каждому ИНДЕКСУ соответствует только один ГОРОД и одна ОБЛАСТЬ, а каждой УЛИЦЕ, ГОРОДУ и ОБЛАСТИ соответствует только один ИНДЕКС. Найти неприводимое множество ФЗ для этого отношения. Какие потенциальные ключи существуют для этого отношения? 8. Пусть дано отношение R c атрибутами A, B, С, D, E, F, G, H, I, J и приведенным ниже множеством ФЗ: ABDE, ABG, BF, CJ, CJI, GH. Является ли это множество неприводимым? Какие потенциальные ключи существуют для этого отношения?