АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Теорема Фейджина

Читайте также:
  1. Вихревой характер магнитного поля. Теорема Ампера о циркуляции индукции магнитного поля в дифференциаль-ной и интегральной форме для магнитных полей в вакууме.
  2. Гільбертовий простір. Теорема про ізоморфізм.
  3. ЗАДАНИЕ № 2. Теорема полной вероятности события.
  4. ІІ. СУМІЖНІ КЛАСИ. ТЕОРЕМА ЛАНГРАНЖА.
  5. Корректные и некорректные декомпозиции отношений. Теорема Хита (с доказательством). Минимально зависимые атрибуты.
  6. Момент инерции. Теорема Штейнера.
  7. Основная теорема безопасности Белла — Лападулы
  8. Основная теорема зубчатого зацепления
  9. Принцип вкладених куль. Теорема Бера.
  10. Спектральная теорема
  11. Теорема
  12. Теорема

r PROJECT (AB) NJ r PROJECT (AC) = r тогда и только тогда, когда A->>B|C. (то есть отношение декомпозируется без потерь)

Докажем достаточность условия теоремы.

Пусть <a,b,c’> и <a,b’,c> принадлежaт r. Следовательно, <a,b> принадлежит r1 <a,c> принадлежит r2. Следовательно, <a,b,c> принадлежит r1 NJ r2. Значит, <a,b,c> принадлежит r. По определению A->>B|C.

Доказательство необходимости условия теоремы.

1) Предположим, что <a,b,c> принадлежит r, следовательно, <a,b> принадлежит r1 <a,c> принадлежит r2. Следовательно, <a,b,c> принадлежит r1 NJ r2.

2) Из того, что <a,b,c> принадлежит r1 NJ r2, следует, что <a,b> принадлежит r1 <a,c> принадлежит r2. Значит, существуют такие <a,b,c’> и <a,b’,c>, принадлежащие r, что <a,b,c> также принадлежит r (т.к. существует многозначная зависимость A->>B|C)

Конец доказательства.

 

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

 

(прим. Доказательства леммы и теоремы взяты из лекций Маши)


 

Многозначные зависимости. Аномалии, возникающие из-за наличия MVD. Пример декомпозиции, решающий проблему (на чем основывается). 4НФ. Нетривиальная и тривиальная многозначные зависимости.

В переменной отношения R с атрибутами A, B, C (в общем случае, составными) имеется многозначная зависимость B от A (AB) в том и только в том случае, когда множество значений атрибута B, соответствующее паре значений атрибутов A и C, зависит от значения A и не зависит от значения C.

Чтобы перейти к вопросам дальнейшей нормализации, рассмотрим еще одну возможную (четвертую) интерпретацию переменной отношения СЛУЖ_ПРО_ЗАДАН. Предположим, что каждый служащий может участвовать в нескольких проектах, но в каждом проекте, в котором он участвует, им должны выполняться одни и те же задания. Возможное значение четвертого варианта переменной отношения СЛУЖ_ПРО_ЗАДАН показано на рис. 9.1.

Рис. 9.1. Возможное значение переменной отношения СЛУЖ_ПРО_ЗАДАН (четвертый вариант)


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.01 сек.)