Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество - Вклад [ru]

ТОРА (9) - Лекция №11 - Оценки

2012-11-20T08:38:48Z

LenaP: /* Пример */

{{Backward|l=ТОРА (9) - Лекция №10 - Логический и физический план запроса}}
== Оптимизация SQL-запросов ==

=== Оценка числа кортежей в промежуточной таблице ===

В таблице {{Формула|f=Q}}. Вычисляется по формуле:

{{Формула|f=Q = \Pi_A(\sigma_f(R))}}

{{Формула|f=T(Q) = T(R)\cdot p}} (7)

здесь:
:{{Формула|f=Q}} - промежуточная таблица;
:{{Формула|f=T(Q)}} - число кортежей в промежуточной таблице;
:{{Формула|f=T(R)}} - число записей в исходной таблице {{Формула|f=R}};
:{{Формула|f=p}} - вероятность того, запись из таблицы {{Формула|f=R}} удовлетворяет условию {{Формула|f=F}}.

Расчёт {{Формула|f=p}}:
# если {{Формула|f=f = F_1\bigcap F_2}}, то {{Формула|f=p = p_1\cdot p_2}};
# если {{Формула|f=f= F_1\bigcup F_2}}, то {{Формула|f=p = p_1 + p_2 - p_1\cdot p_2}};
# если {{Формула|f=f = \overline{F_1} }}, то {{Формула|f=p = 1 - p_1}}.

Для {{Формула|f=i}}-ой вероятности:

{{Формула|f=p_i = \frac{k}{I(R,a)} }}

здесь:
:{{Формула|f=k}} - мощность атрибута {{Формула|f=a}} в запросе;
:{{Формула|f=I(R,a)}} - мощность атрибута {{Формула|f=a}} в таблице {{Формула|f=R}}.

==== Пример ====

Допустим, {{Формула|f=T(R) = 1000}}, {{Формула|f=I(R,a) = 5}}, {{Формула|f=I(R,b) = 10}}, {{Формула|f=I(R,c) = 2}}, где {{Формула|f=a,b,c}} - положительные натуральные числа.

И {{Формула|f=f = (a<3}} {{Формула|f=OR}} {{Формула|f=b\geq5)}} {{Формула|f=AND}} {{Формула|f=c=2}}

Найти {{Формула|f=T(Q)}}.

Обозначим:
* {{Формула|f=a<3}} как {{Формула|f=F_1}};
* {{Формула|f=b\geq 5}} как {{Формула|f=F_2}};
* {{Формула|f=f = (a<3}} {{Формула|f=OR}} {{Формула|f=b\geq5)}} как {{Формула|f=F_3}};
* {{Формула|f=c=2}} как {{Формула|f=F_4}}.

1)

:{{Формула|f=F_1\bigcup F_2 = F_3}}
:{{Формула|f=p_3 = p_1 + p_2 - p_1\cdot p_2 = \frac{2}{5} + \frac{6}{10} - \frac{2}{5}\cdot\frac{6}{10} = 0.76}}

2)

:{{Формула|f=f = F_3\bigcap F_4}}
:{{Формула|f=p = p_3\cdot p_4 = 0.76\cdot\frac{1}{2} = 0.38}} - это вероятность того, что запись из {{Формула|f=R}} удовлетворяет условию {{Формула|f=f}}.

3)

:{{Формула|f=T(Q) = 1000\cdot 0.38 = 380}}

=== Оценка количества блоков ===

{{Формула|f=Q = \Pi_A(\sigma_f(R))}}

{{Формула|f=B(Q) = \Bigr[\frac{T(Q)}{L_B}\Bigl]}} - скобки обзначают, что огругление с избытком.

здесь:
:{{Формула|f=T(Q)}} - прогнозируемое число записей в подзапросе;
:{{Формула|f=L_B}} - длина блока (число записей в блоке) с учётом {{Формула|f=\Pi_A}}.

=== Деревья соединения ===

Три вида:
* левостороннее;
* кустовое, ветвящееся;
* правостороннее.

==== Левостороннее ====

Предположим, соединяются таблицы {{Формула|f=R,S,T,U}}:

[[Файл:9sTORAl11pic1.png|300px]]

В каждом соединении правым аргументом является одна из таблиц.

Преимущества:
* число перебора вариантов меньше, чем для произвольного варианта соединения (если количество соединений {{Формула|f=n}}, то вариантов перебора будет {{Формула|f=n!}});
* достаточно просто организивать ''каналы обработки'' - возможность передачи результата выполнения одной операции на вход другой через оперативную память (без сохранения на диск);

В канале левый аргументы называется ''опорным'' и он должен храниться в оперативной памяти. Правый аргумент называется ''тестируемым'' и он может храниться и на диске. При хранении в оперативной памяти не надо читать с диска, потому всё можно выполнить за одни проход.

Недостатки:
* путём перебора порядков соединения можно выбрать квазиоптимальный план (потому что на самом деле вариантов перебора больше, чем {{Формула|f=n!}}, потому что правый аргумент - всегда таблица).

==== Кустовое ====

Тут таблицы могут соединяться в любом порядке.

[[Файл:9sTORAl11pic2.png|300px]]

Так что перебираются все возможные варианты соединения.

Преимущества:
* всегда выбирается оптимальный план.

Недостатки:
* если количество соединяемых таблиц велико, то перебор всех деревьев может занять много времени;
* могут возникнуть сложности в организации канала обработки, так как возрастают требования к объёму оперативной памяти. Чтобы реализовать соединение за один проход, в памяти должно храниться слишком много таблиц.

==== Правостороннее ====

При таком порядке левым аргументом каждого соединения является исходная таблица.

[[Файл:9sTORAl11pic3.png|300px]]

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

=== Методы соединения таблиц ===

Методы реализации естественного соединения {{Формула|f=\bowtie}}.

Три метода:
* ложных циклов (NLJ - Nested Loop Join);
* сортировки слияния (SMJ - Sort Merge Join);
* хэшированных соединений (Hash Join).

==== Метод ложных циклов ====

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

[[Файл:9sTORAl11pic4.png|500px]]

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

СЭВМ (9) - Лекция №10 - Обслуживание мейнфреймов

2012-11-19T13:51:32Z

LenaP: /* Системный программист */

{{Backward|l= СЭВМ (9) - Лекция №9 - Мейнфреймы}}

== Мейнфреймы ==

=== Функции ===

==== Пакетная обработка ====

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

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

Пакетные задания считывают и обрабатывают данные в больших количествах и формируют выходные данные.

Однако, пакетная обработка не так распространена, как мейнфреймы, так как распределённых систем часто не хватает:
* дискового пространства;
* доступной мощности процессора;
* управления системными ресурсами;
* планирование заданий на уровне [http://en.wikipedia.org/wiki/IBM_Parallel_Sysplex#Sysplex Sysplex].

Пакетные процессы обычно имеют следующие свойства:
* обработка и хранения больших объёмов вводимых данных;
* доступ к большому количеству записей;
* большой объём выходных данных;
* мгновенная реакция (обычно, это обязательное требование);
* генерируется информация о большом количестве пользователей или информационных объектов.

Запланированный пакетный процесс может представлять выполнение тысяч задач в заданной последовательности. Рассмотрим последовательность выполнения запланированного пакетного процесса:
# ночью происходит обработка множества пакетных заданий, осуществляющих запуск программ и утилит. Эти задания консолидируют результаты оперативных транзакций, прошедших в течение дня;
# до и после выполнения заданий создаются резервные копии критически важных данных;
# отчёты с коммерческой статистикой передаются в специальный отдел для анализа;
# отчёты с заключениями(исключениями?) пересылаются в филиалы;
# отчёты о суммарной обработке данных отправляются партнёрской компании, владельцу торговой марки;
# владелец осуществляет мониторинг;
# задания и транзакции выполняют чтение или обновление БД.

==== Обработка оперативных транзакций ====

Это обработка транзакций, выполняемая интерактивно с участием конечного пользователя.

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

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

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

Оперативные транзакции обладают следующими свойствами:
* небольшое количество входных данных;
* небольшое количество хранимых записей, к которым осуществляется доступ и обработка;
* небольшое количество выходных данных.

Требования к транзакционным системам:
* высокая скорость реакции;
* больше количество пользователей;
* круглосуточная доступность транзакционного интерфейса для пользователя;
* безопасность выполнения транзакций.

Пример транзакционной системы:
# клиент использует обычный банкомат с понятным пользователю графическим интерфейсом;
# в филиале банка той же сети сидит сотрудник и осуществляет операции;
# в центральном офисе тоже что-то происходит, например бизнес-аналитик настраивает транзакции и решает производительность;
# все запросы отправляются на мейнфрейм для обработки;
# приложения на мейнфрейме выполняют обновление и запросы к СУБД;
# сохранение файлов БД.

=== Обслуживание мейнфреймов ===

На обслуживание мейнфрейма требуется тьма всяких должностей: от администраторов и программистов до завскладом.

==== Системный программист ====

Занимается установкой, настройкой и обслуживанием операционной системы. Он же ставит и обновляет ПО.

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

Должен иметь навыки исправления ошибок системного ПО. Смотрит дампы и выясняет.

Занимается обслуживанием промежуточного ПО (программный слой между ОС и приложением конечного пользователя).

==== Системный администратор ====

Обслуживает критически важные данные предприятия (БД).

Задачи:
* установка ПО;
* добавление и удаление пользователей;
* управление правами доступа;
* управление устройствами хранения;
* управление сетями и связью;
* мониторинг системной производительности.

==== Проектировщики и программисты приложений ====

Проектирование, компоновка, тестирование и доставка приложений к конечному пользователю.

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

Тестирование:
* функциональное - соответствие ТЗ;
* модульное - проверка модуля отдельно;
* интеграционное - как будет работать вся система.

==== Системный оператор ====

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

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

==== Аналитик производственного контроля ====

Отвечает за проверку безошибочного и бесперебойного выполнения пакетных заданий.

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

Благодаря контролю, осуществляемому аналитиком, сложно внести какие-либо изменения в систему в обход предусмотренных процедур.

==== Изготовитель ====

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

Должностные лица поддержки:
* наладчик. Устанавливает, ремонтирует;
* специалист по поддержке ПО.

[[Категория:Супер ЭВМ (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

СЭВМ (9) - Лекция №10 - Обслуживание мейнфреймов

2012-11-19T13:48:40Z

LenaP: /* Обработка оперативных транзакций */

{{Backward|l= СЭВМ (9) - Лекция №9 - Мейнфреймы}}

== Мейнфреймы ==

=== Функции ===

==== Пакетная обработка ====

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

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

Пакетные задания считывают и обрабатывают данные в больших количествах и формируют выходные данные.

Однако, пакетная обработка не так распространена, как мейнфреймы, так как распределённых систем часто не хватает:
* дискового пространства;
* доступной мощности процессора;
* управления системными ресурсами;
* планирование заданий на уровне [http://en.wikipedia.org/wiki/IBM_Parallel_Sysplex#Sysplex Sysplex].

Пакетные процессы обычно имеют следующие свойства:
* обработка и хранения больших объёмов вводимых данных;
* доступ к большому количеству записей;
* большой объём выходных данных;
* мгновенная реакция (обычно, это обязательное требование);
* генерируется информация о большом количестве пользователей или информационных объектов.

Запланированный пакетный процесс может представлять выполнение тысяч задач в заданной последовательности. Рассмотрим последовательность выполнения запланированного пакетного процесса:
# ночью происходит обработка множества пакетных заданий, осуществляющих запуск программ и утилит. Эти задания консолидируют результаты оперативных транзакций, прошедших в течение дня;
# до и после выполнения заданий создаются резервные копии критически важных данных;
# отчёты с коммерческой статистикой передаются в специальный отдел для анализа;
# отчёты с заключениями(исключениями?) пересылаются в филиалы;
# отчёты о суммарной обработке данных отправляются партнёрской компании, владельцу торговой марки;
# владелец осуществляет мониторинг;
# задания и транзакции выполняют чтение или обновление БД.

==== Обработка оперативных транзакций ====

Это обработка транзакций, выполняемая интерактивно с участием конечного пользователя.

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

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

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

Оперативные транзакции обладают следующими свойствами:
* небольшое количество входных данных;
* небольшое количество хранимых записей, к которым осуществляется доступ и обработка;
* небольшое количество выходных данных.

Требования к транзакционным системам:
* высокая скорость реакции;
* больше количество пользователей;
* круглосуточная доступность транзакционного интерфейса для пользователя;
* безопасность выполнения транзакций.

Пример транзакционной системы:
# клиент использует обычный банкомат с понятным пользователю графическим интерфейсом;
# в филиале банка той же сети сидит сотрудник и осуществляет операции;
# в центральном офисе тоже что-то происходит, например бизнес-аналитик настраивает транзакции и решает производительность;
# все запросы отправляются на мейнфрейм для обработки;
# приложения на мейнфрейме выполняют обновление и запросы к СУБД;
# сохранение файлов БД.

=== Обслуживание мейнфреймов ===

На обслуживание мейнфрейма требуется тьма всяких должностей: от администраторов и программистов до завскладом.

==== Системный программист ====

Занимается установкой, настройкой и обслуживанием операционной системы. Он же ставит и обновляет ПО.

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

Должен иметь навыки исправления ошибок системного ПО. Смотрит дампы и выясняет.

Занимается обслуживанием промежуточного ПО (программный слой между ОС и приложением конечного пользователя).

==== Системный администратор ====

Обслуживает критически важные данные предприятия (БД).

Задачи:
* установка ПО;
* добавление и удаление пользователей;
* управление правами доступа;
* управление устройствами хранения;
* управление сетями и связью;
* мониторинг системной производительности.

==== Проектировщики и программисты приложений ====

Проектирование, компоновка, тестирование и доставка приложений к конечному пользователю.

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

Тестирование:
* функциональное - соответствие ТЗ;
* модульное - проверка модуля отдельно;
* интеграционное - как будет работать вся система.

==== Системный оператор ====

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

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

==== Аналитик производственного контроля ====

Отвечает за проверку безошибочного и бесперебойного выполнения пакетных заданий.

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

Благодаря контролю, осуществляемому аналитиком, сложно внести какие-либо изменения в систему в обход предусмотренных процедур.

==== Изготовитель ====

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

Должностные лица поддержки:
* наладчик. Устанавливает, ремонтирует;
* специалист по поддержке ПО.

[[Категория:Супер ЭВМ (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь

2012-09-25T05:43:50Z

LenaP: /* Пример БД, обладающей свойством соединения без потерь */

Пусть {{Формула|f=F}} и {{Формула|f=G}} - два множества ФЗ.

{{Формула|f=G}} называется ''покрытием'' {{Формула|f=F}}, если имеет место равенство {{Формула|f=G^+ = F^+}}

Существуют различные виды покрытий. Но мы рассмотрим только один - ''условно-неизбыточное покрытие''.

== Алгоритм построения условно-неизбыточного покрытия ==

1) если в множестве ФЗ {{Формула|f=F}} встречаются ФЗ с одинаковой левой частью {{Формула|f=X}}, то следует объединить эти ФЗ в одну ФЗ. Это следует из аксиомы объединения. Получившееся множество ФЗ обозначим {{Формула|f=G}};

2) для каждой ФЗ {{Формула|f=X\rightarrow Y}} из {{Формула|f=G}} заменить её на {{Формула|f=X\rightarrow X^+ - X}};

После выполнения 1) и 2) получаем замыкание {{Формула|f=G^+ = F}}

=== Доказательство ===

1)

:если ФЗ {{Формула|f=X\rightarrow Y\in F}}, то эта ФЗ принадежит {{Формула|f=G^+}}, а из этого следует, что {{Формула|f=Y \subseteq X^+}}

:По построению G имеет место ФЗ: {{Формула|f=X\rightarrow X^+ - X}}

:Пополним эту ФЗ: {{Формула|f=X\rightarrow (X^+ - X)\bigcup X = X^+}}

:Теперь по первой аксиоме Армстронга имеем {{Формула|f=X^+\rightarrow Y}}

:Значит, {{Формула|f=X\rightarrow Y \in G^+}}, по третьей аксиоме Армстронга.

2)

:{{Формула|f=X\rightarrow Y \in G}}, {{Формула|f=X\rightarrow Y \in F^+}}

:{{Формула|f=Y = X^+ - X}}

:{{Формула|f=X\rightarrow X^+}} (по определению)

:{{Формула|f=X^+\rightarrow X^+ - X}} (1 аксиома Армстронга)

:{{Формула|f=X^+\rightarrow X^+ - X = Y}} (3 аксимома Армстронга)

:{{Формула|f=X^+\rightarrow Y \in F^+}}

=== Пример ===

УСО: {{Формула|f=R = (A, B, C)}}

Множество ФЗ: {{Формула|f=F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)}}

1)

:{{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A}}

2)

:{{Формула|f=A^+ = ABC}}, {{Формула|f=A^+ - A = BC}}

:{{Формула|f=B^+ = BAC}}, {{Формула|f=B^+ - B = AC}}

:{{Формула|f=C^+ = CAB}}, {{Формула|f=C^+ - C = AB}}

Тогда {{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)}} будет являться УНП.

== Свойства "хорошей" схемы БД ==

"Хорошая", но не оптимальная. Должна обладать следующими свойствами:
* соединение без потерь;
* сохранение ФЗ;
* каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
** избыточность;
** потенциальная противоречивсть;
** аномалия обновления;
** аномалия удаления.

=== Соединение без потерь ===

Пусть {{Формула|f=\rho = (R_1 ... R_n)}} - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения {{Формула|f=r}} из {{Формула|f=R}} справедливо равенство: {{Формула|f=r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)}}, где {{Формула|f=\Pi_{R_i}(r)}} - это проекция экземпляра отношения {{Формула|f=r}} на множество атрибутов {{Формула|f=R_i}}

==== Пример БД, не обладающей свойством соединения без потерь ====

{{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, BC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Достаточно привести пример экземпляра {{Формула|f=r}}, для которого равенство не выполняется:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

{|
| valign="top" |
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! В !! С
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}
|}

Полученное соединение не будет равняться {{Формула|f=r}}:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="4" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center" bgcolor="#FFB6C1"
| {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|- align="center" bgcolor="#FFB6C1"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.

==== Пример БД, обладающей свойством соединения без потерь ====

{{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Возьмём тот же экземпляр:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

{|
| valign="top" |
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A !! С
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=c_2}}
|}
|}

Полученное соединение будет равняться {{Формула|f=r}}:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.

==== Алгоритм проверки схемы БД на свойство соединения без потерь ====

{{Формула|f=\rho = (R_1 ... R_n)}}

{{Формула|f=R = (A_1 ... A_n)}}

1) построить таблицу T:

{| class="wikitable"
! !! {{Формула|f=A_1}} || {{Формула|f=A_2}} || ... || {{Формула|f=A_k}}
|- align="center"
! {{Формула|f=R_1}}
| || || ||
|- align="center"
! {{Формула|f=R_2}}
| || || ||
|- align="center"
! ...
| || || ||
|- align="center"
! {{Формула|f=R_n}}
| || || ||
|}

И заполнить таблицу T по правилу: если {{Формула|f=A_j \in R_i}}, то {{Формула|f=T_{ij}=a}}, иначе {{Формула|f=T_{ij}=b_i}}

2) изменить таблицу T - циклически просматривать ФЗ из {{Формула|f=F}} в любом порядке, и для очередной ФЗ {{Формула|f=X\rightarrow Y \in F}} выполнить следующие действия:
* найти в таблице T строки, совпадающие по атрибутам {{Формула|f=X}} (по левой части);
* если хотя бы в одной такой строке значение атрибута {{Формула|f=A_m \in Y = a}}, то во всех найденных строках присвоить {{Формула|f=A_m = a}}, иначе присвоить {{Формула|f=A_m = b_i}} (}}i}} - номер одной из найденных строк, {{Формула|f=b_i}} должно быть одинаково во всех указанных строках);
* выполнить предыдущие два пункта для всех атрибутов {{Формула|f=A_l \in Y}};
* выполнить предыдущие три пункта для всех ФЗ из {{Формула|f=F}}, циклически их просматривая.

3) алгоритм останавливается, если при очередном просмотре ФЗ из {{Формула|f=F}}:
* не произошло никаких изменений в таблице T;
* какая-нибудь строка в T не стала состоять сплошь из символов {{Формула|f=a}} (наличие такой строки и говорит о выполнении свойства соединения без потерь).

===== Пример =====

Пусть {{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь.

1)

{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}}
|}

2)

{|
| valign="top" |
{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}}
|}
|}

Получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь.

===== Другой пример =====

Пусть {{Формула|f=R = (A, B, C, D, E, F, P, S)}}

{{Формула|f=\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)}}

{{Формула|f=F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)}}

Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь.

1)

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

2)

первый просмотр:

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

второй просмотр:

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

Вот и получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь.

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь

2012-09-25T05:37:37Z

LenaP: /* Пример БД, не обладающей свойством соединения без потерь */

Пусть {{Формула|f=F}} и {{Формула|f=G}} - два множества ФЗ.

{{Формула|f=G}} называется ''покрытием'' {{Формула|f=F}}, если имеет место равенство {{Формула|f=G^+ = F^+}}

Существуют различные виды покрытий. Но мы рассмотрим только один - ''условно-неизбыточное покрытие''.

== Алгоритм построения условно-неизбыточного покрытия ==

1) если в множестве ФЗ {{Формула|f=F}} встречаются ФЗ с одинаковой левой частью {{Формула|f=X}}, то следует объединить эти ФЗ в одну ФЗ. Это следует из аксиомы объединения. Получившееся множество ФЗ обозначим {{Формула|f=G}};

2) для каждой ФЗ {{Формула|f=X\rightarrow Y}} из {{Формула|f=G}} заменить её на {{Формула|f=X\rightarrow X^+ - X}};

После выполнения 1) и 2) получаем замыкание {{Формула|f=G^+ = F}}

=== Доказательство ===

1)

:если ФЗ {{Формула|f=X\rightarrow Y\in F}}, то эта ФЗ принадежит {{Формула|f=G^+}}, а из этого следует, что {{Формула|f=Y \subseteq X^+}}

:По построению G имеет место ФЗ: {{Формула|f=X\rightarrow X^+ - X}}

:Пополним эту ФЗ: {{Формула|f=X\rightarrow (X^+ - X)\bigcup X = X^+}}

:Теперь по первой аксиоме Армстронга имеем {{Формула|f=X^+\rightarrow Y}}

:Значит, {{Формула|f=X\rightarrow Y \in G^+}}, по третьей аксиоме Армстронга.

2)

:{{Формула|f=X\rightarrow Y \in G}}, {{Формула|f=X\rightarrow Y \in F^+}}

:{{Формула|f=Y = X^+ - X}}

:{{Формула|f=X\rightarrow X^+}} (по определению)

:{{Формула|f=X^+\rightarrow X^+ - X}} (1 аксиома Армстронга)

:{{Формула|f=X^+\rightarrow X^+ - X = Y}} (3 аксимома Армстронга)

:{{Формула|f=X^+\rightarrow Y \in F^+}}

=== Пример ===

УСО: {{Формула|f=R = (A, B, C)}}

Множество ФЗ: {{Формула|f=F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)}}

1)

:{{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A}}

2)

:{{Формула|f=A^+ = ABC}}, {{Формула|f=A^+ - A = BC}}

:{{Формула|f=B^+ = BAC}}, {{Формула|f=B^+ - B = AC}}

:{{Формула|f=C^+ = CAB}}, {{Формула|f=C^+ - C = AB}}

Тогда {{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)}} будет являться УНП.

== Свойства "хорошей" схемы БД ==

"Хорошая", но не оптимальная. Должна обладать следующими свойствами:
* соединение без потерь;
* сохранение ФЗ;
* каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
** избыточность;
** потенциальная противоречивсть;
** аномалия обновления;
** аномалия удаления.

=== Соединение без потерь ===

Пусть {{Формула|f=\rho = (R_1 ... R_n)}} - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения {{Формула|f=r}} из {{Формула|f=R}} справедливо равенство: {{Формула|f=r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)}}, где {{Формула|f=\Pi_{R_i}(r)}} - это проекция экземпляра отношения {{Формула|f=r}} на множество атрибутов {{Формула|f=R_i}}

==== Пример БД, не обладающей свойством соединения без потерь ====

{{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, BC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Достаточно привести пример экземпляра {{Формула|f=r}}, для которого равенство не выполняется:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

{|
| valign="top" |
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! В !! С
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}
|}

Полученное соединение не будет равняться {{Формула|f=r}}:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="4" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center" bgcolor="#FFB6C1"
| {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|- align="center" bgcolor="#FFB6C1"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.

==== Пример БД, обладающей свойством соединения без потерь ====

{{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Возьмём тот же экземпляр:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

{|
| valign="top" |
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=c_2}}
|}
|}

Полученное соединение будет равняться {{Формула|f=r}}:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.

==== Алгоритм проверки схемы БД на свойство соединения без потерь ====

{{Формула|f=\rho = (R_1 ... R_n)}}

{{Формула|f=R = (A_1 ... A_n)}}

1) построить таблицу T:

{| class="wikitable"
! !! {{Формула|f=A_1}} || {{Формула|f=A_2}} || ... || {{Формула|f=A_k}}
|- align="center"
! {{Формула|f=R_1}}
| || || ||
|- align="center"
! {{Формула|f=R_2}}
| || || ||
|- align="center"
! ...
| || || ||
|- align="center"
! {{Формула|f=R_n}}
| || || ||
|}

И заполнить таблицу T по правилу: если {{Формула|f=A_j \in R_i}}, то {{Формула|f=T_{ij}=a}}, иначе {{Формула|f=T_{ij}=b_i}}

2) изменить таблицу T - циклически просматривать ФЗ из {{Формула|f=F}} в любом порядке, и для очередной ФЗ {{Формула|f=X\rightarrow Y \in F}} выполнить следующие действия:
* найти в таблице T строки, совпадающие по атрибутам {{Формула|f=X}} (по левой части);
* если хотя бы в одной такой строке значение атрибута {{Формула|f=A_m \in Y = a}}, то во всех найденных строках присвоить {{Формула|f=A_m = a}}, иначе присвоить {{Формула|f=A_m = b_i}} (}}i}} - номер одной из найденных строк, {{Формула|f=b_i}} должно быть одинаково во всех указанных строках);
* выполнить предыдущие два пункта для всех атрибутов {{Формула|f=A_l \in Y}};
* выполнить предыдущие три пункта для всех ФЗ из {{Формула|f=F}}, циклически их просматривая.

3) алгоритм останавливается, если при очередном просмотре ФЗ из {{Формула|f=F}}:
* не произошло никаких изменений в таблице T;
* какая-нибудь строка в T не стала состоять сплошь из символов {{Формула|f=a}} (наличие такой строки и говорит о выполнении свойства соединения без потерь).

===== Пример =====

Пусть {{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь.

1)

{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}}
|}

2)

{|
| valign="top" |
{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}}
|}
|}

Получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь.

===== Другой пример =====

Пусть {{Формула|f=R = (A, B, C, D, E, F, P, S)}}

{{Формула|f=\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)}}

{{Формула|f=F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)}}

Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь.

1)

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

2)

первый просмотр:

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

второй просмотр:

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

Вот и получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь.

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь

2012-09-25T05:36:13Z

LenaP: /* Соединение без потерь */

Пусть {{Формула|f=F}} и {{Формула|f=G}} - два множества ФЗ.

{{Формула|f=G}} называется ''покрытием'' {{Формула|f=F}}, если имеет место равенство {{Формула|f=G^+ = F^+}}

Существуют различные виды покрытий. Но мы рассмотрим только один - ''условно-неизбыточное покрытие''.

== Алгоритм построения условно-неизбыточного покрытия ==

1) если в множестве ФЗ {{Формула|f=F}} встречаются ФЗ с одинаковой левой частью {{Формула|f=X}}, то следует объединить эти ФЗ в одну ФЗ. Это следует из аксиомы объединения. Получившееся множество ФЗ обозначим {{Формула|f=G}};

2) для каждой ФЗ {{Формула|f=X\rightarrow Y}} из {{Формула|f=G}} заменить её на {{Формула|f=X\rightarrow X^+ - X}};

После выполнения 1) и 2) получаем замыкание {{Формула|f=G^+ = F}}

=== Доказательство ===

1)

:если ФЗ {{Формула|f=X\rightarrow Y\in F}}, то эта ФЗ принадежит {{Формула|f=G^+}}, а из этого следует, что {{Формула|f=Y \subseteq X^+}}

:По построению G имеет место ФЗ: {{Формула|f=X\rightarrow X^+ - X}}

:Пополним эту ФЗ: {{Формула|f=X\rightarrow (X^+ - X)\bigcup X = X^+}}

:Теперь по первой аксиоме Армстронга имеем {{Формула|f=X^+\rightarrow Y}}

:Значит, {{Формула|f=X\rightarrow Y \in G^+}}, по третьей аксиоме Армстронга.

2)

:{{Формула|f=X\rightarrow Y \in G}}, {{Формула|f=X\rightarrow Y \in F^+}}

:{{Формула|f=Y = X^+ - X}}

:{{Формула|f=X\rightarrow X^+}} (по определению)

:{{Формула|f=X^+\rightarrow X^+ - X}} (1 аксиома Армстронга)

:{{Формула|f=X^+\rightarrow X^+ - X = Y}} (3 аксимома Армстронга)

:{{Формула|f=X^+\rightarrow Y \in F^+}}

=== Пример ===

УСО: {{Формула|f=R = (A, B, C)}}

Множество ФЗ: {{Формула|f=F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)}}

1)

:{{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A}}

2)

:{{Формула|f=A^+ = ABC}}, {{Формула|f=A^+ - A = BC}}

:{{Формула|f=B^+ = BAC}}, {{Формула|f=B^+ - B = AC}}

:{{Формула|f=C^+ = CAB}}, {{Формула|f=C^+ - C = AB}}

Тогда {{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)}} будет являться УНП.

== Свойства "хорошей" схемы БД ==

"Хорошая", но не оптимальная. Должна обладать следующими свойствами:
* соединение без потерь;
* сохранение ФЗ;
* каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
** избыточность;
** потенциальная противоречивсть;
** аномалия обновления;
** аномалия удаления.

=== Соединение без потерь ===

Пусть {{Формула|f=\rho = (R_1 ... R_n)}} - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения {{Формула|f=r}} из {{Формула|f=R}} справедливо равенство: {{Формула|f=r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)}}, где {{Формула|f=\Pi_{R_i}(r)}} - это проекция экземпляра отношения {{Формула|f=r}} на множество атрибутов {{Формула|f=R_i}}

==== Пример БД, не обладающей свойством соединения без потерь ====

{{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, BC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Достаточно привести пример экземпляра {{Формула|f=r}}, для которого равенство не выполняется:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

{|
| valign="top" |
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}
|}

Полученное соединение не будет равняться {{Формула|f=r}}:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="4" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center" bgcolor="#FFB6C1"
| {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|- align="center" bgcolor="#FFB6C1"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.

==== Пример БД, обладающей свойством соединения без потерь ====

{{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Возьмём тот же экземпляр:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

{|
| valign="top" |
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=c_2}}
|}
|}

Полученное соединение будет равняться {{Формула|f=r}}:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.

==== Алгоритм проверки схемы БД на свойство соединения без потерь ====

{{Формула|f=\rho = (R_1 ... R_n)}}

{{Формула|f=R = (A_1 ... A_n)}}

1) построить таблицу T:

{| class="wikitable"
! !! {{Формула|f=A_1}} || {{Формула|f=A_2}} || ... || {{Формула|f=A_k}}
|- align="center"
! {{Формула|f=R_1}}
| || || ||
|- align="center"
! {{Формула|f=R_2}}
| || || ||
|- align="center"
! ...
| || || ||
|- align="center"
! {{Формула|f=R_n}}
| || || ||
|}

И заполнить таблицу T по правилу: если {{Формула|f=A_j \in R_i}}, то {{Формула|f=T_{ij}=a}}, иначе {{Формула|f=T_{ij}=b_i}}

2) изменить таблицу T - циклически просматривать ФЗ из {{Формула|f=F}} в любом порядке, и для очередной ФЗ {{Формула|f=X\rightarrow Y \in F}} выполнить следующие действия:
* найти в таблице T строки, совпадающие по атрибутам {{Формула|f=X}} (по левой части);
* если хотя бы в одной такой строке значение атрибута {{Формула|f=A_m \in Y = a}}, то во всех найденных строках присвоить {{Формула|f=A_m = a}}, иначе присвоить {{Формула|f=A_m = b_i}} (}}i}} - номер одной из найденных строк, {{Формула|f=b_i}} должно быть одинаково во всех указанных строках);
* выполнить предыдущие два пункта для всех атрибутов {{Формула|f=A_l \in Y}};
* выполнить предыдущие три пункта для всех ФЗ из {{Формула|f=F}}, циклически их просматривая.

3) алгоритм останавливается, если при очередном просмотре ФЗ из {{Формула|f=F}}:
* не произошло никаких изменений в таблице T;
* какая-нибудь строка в T не стала состоять сплошь из символов {{Формула|f=a}} (наличие такой строки и говорит о выполнении свойства соединения без потерь).

===== Пример =====

Пусть {{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь.

1)

{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}}
|}

2)

{|
| valign="top" |
{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}}
|}
|}

Получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь.

===== Другой пример =====

Пусть {{Формула|f=R = (A, B, C, D, E, F, P, S)}}

{{Формула|f=\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)}}

{{Формула|f=F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)}}

Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь.

1)

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

2)

первый просмотр:

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

второй просмотр:

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

Вот и получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь.

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь

2012-09-25T04:48:50Z

LenaP: /* Алгоритм построение условно-неизбыточного покрытия */

Пусть {{Формула|f=F}} и {{Формула|f=G}} - два множества ФЗ.

{{Формула|f=G}} называется ''покрытием'' {{Формула|f=F}}, если имеет место равенство {{Формула|f=G^+ = F^+}}

Существуют различные виды покрытий. Но мы рассмотрим только один - ''условно-неизбыточное покрытие''.

== Алгоритм построения условно-неизбыточного покрытия ==

1) если в множестве ФЗ {{Формула|f=F}} встречаются ФЗ с одинаковой левой частью {{Формула|f=X}}, то следует объединить эти ФЗ в одну ФЗ. Это следует из аксиомы объединения. Получившееся множество ФЗ обозначим {{Формула|f=G}};

2) для каждой ФЗ {{Формула|f=X\rightarrow Y}} из {{Формула|f=G}} заменить её на {{Формула|f=X\rightarrow X^+ - X}};

После выполнения 1) и 2) получаем замыкание {{Формула|f=G^+ = F}}

=== Доказательство ===

1)

:если ФЗ {{Формула|f=X\rightarrow Y\in F}}, то эта ФЗ принадежит {{Формула|f=G^+}}, а из этого следует, что {{Формула|f=Y \subseteq X^+}}

:По построению G имеет место ФЗ: {{Формула|f=X\rightarrow X^+ - X}}

:Пополним эту ФЗ: {{Формула|f=X\rightarrow (X^+ - X)\bigcup X = X^+}}

:Теперь по первой аксиоме Армстронга имеем {{Формула|f=X^+\rightarrow Y}}

:Значит, {{Формула|f=X\rightarrow Y \in G^+}}, по третьей аксиоме Армстронга.

2)

:{{Формула|f=X\rightarrow Y \in G}}, {{Формула|f=X\rightarrow Y \in F^+}}

:{{Формула|f=Y = X^+ - X}}

:{{Формула|f=X\rightarrow X^+}} (по определению)

:{{Формула|f=X^+\rightarrow X^+ - X}} (1 аксиома Армстронга)

:{{Формула|f=X^+\rightarrow X^+ - X = Y}} (3 аксимома Армстронга)

:{{Формула|f=X^+\rightarrow Y \in F^+}}

=== Пример ===

УСО: {{Формула|f=R = (A, B, C)}}

Множество ФЗ: {{Формула|f=F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)}}

1)

:{{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A}}

2)

:{{Формула|f=A^+ = ABC}}, {{Формула|f=A^+ - A = BC}}

:{{Формула|f=B^+ = BAC}}, {{Формула|f=B^+ - B = AC}}

:{{Формула|f=C^+ = CAB}}, {{Формула|f=C^+ - C = AB}}

Тогда {{Формула|f=G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)}} будет являться УНП.

== Свойства "хорошей" схемы БД ==

"Хорошая", но не оптимальная. Должна обладать следующими свойствами:
* соединение без потерь;
* сохранение ФЗ;
* каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
** избыточность;
** потенциальная противоречивсть;
** аномалия обновления;
** аномалия удаления.

=== Соединение без потерь ===

Пусть {{Формула|f=\rho = (R_1 ... R_n)}} - схема БД. Она будет обладать свойствоем соединения без потерь, если для любого экземпляра отношения {{Формула|f=r}} из {{Формула|f=R}} справедливо равенство: {{Формула|f=r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)}}, где {{Формула|f=\Pi_{R_i}(r)}} - это проекция экземпляра отношения {{Формула|f=r}} на множество атрибутов {{Формула|f=R_i}}

==== Пример БД, не обладающей свойством соединения без потерь ====

{{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, BC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Достаточно привести пример экземпляра {{Формула|f=r}}, для которого равенство не выполняется:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

{|
| valign="top" |
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}
|}

Полученное соединение не будет равняться {{Формула|f=r}}:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="4" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center" bgcolor="#FFB6C1"
| {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|- align="center" bgcolor="#FFB6C1"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.

==== Пример БД, обладающей свойством соединения без потерь ====

{{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Возьмём тот же экземпляр:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=r}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

{|
| valign="top" |
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A !! B
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=c_2}}
|}
|}

Полученное соединение будет равняться {{Формула|f=r}}:

{| class="wikitable"
! !! A !! B !! C
|- align="center"
| rowspan="2" | {{Формула|f=\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)}} || {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}}
|- align="center"
| {{Формула|f=a_2}} || {{Формула|f=b_1}} || {{Формула|f=c_2}}
|}

Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.

==== Алгоритм проверки схемы БД на свойство соединения без потерь ====

{{Формула|f=\rho = (R_1 ... R_n)}}

{{Формула|f=R = (A_1 ... A_n)}}

1) построить таблицу T:

{| class="wikitable"
! !! {{Формула|f=A_1}} || {{Формула|f=A_2}} || ... || {{Формула|f=A_k}}
|- align="center"
! {{Формула|f=R_1}}
| || || ||
|- align="center"
! {{Формула|f=R_2}}
| || || ||
|- align="center"
! ...
| || || ||
|- align="center"
! {{Формула|f=R_n}}
| || || ||
|}

И заполнить таблицу T по правилу: если {{Формула|f=A_j \in R_i}}, то {{Формула|f=T_{ij}=a}}, иначе {{Формула|f=T_{ij}=b_i}}

2) изменить таблицу T - циклически просматривать ФЗ из {{Формула|f=F}} в любом порядке, и для очередной ФЗ {{Формула|f=X\rightarrow Y \in F}} выполнить следующие действия:
* найти в таблице T строки, совпадающие по атрибутам {{Формула|f=X}} (по левой части);
* если хотя бы в одной такой строке значение атрибута {{Формула|f=A_m \in Y = a}}, то во всех найденных строках присвоить {{Формула|f=A_m = a}}, иначе присвоить {{Формула|f=A_m = b_i}} (}}i}} - номер одной из найденных строк, {{Формула|f=b_i}} должно быть одинаково во всех указанных строках);
* выполнить предыдущие два пункта для всех атрибутов {{Формула|f=A_l \in Y}};
* выполнить предыдущие три пункта для всех ФЗ из {{Формула|f=F}}, циклически их просматривая.

3) алгоритм останавливается, если при очередном просмотре ФЗ из {{Формула|f=F}}:
* не произошло никаких изменений в таблице T;
* какая-нибудь строка в T не стала состоять сплошь из символов {{Формула|f=a}} (наличие такой строки и говорит о выполнении свойства соединения без потерь).

===== Пример =====

Пусть {{Формула|f=R = (A, B, C)}}

{{Формула|f=\rho = (AB, AC) = (R_1, R_2)}}

{{Формула|f=F = (A\rightarrow B)}}

Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь.

1)

{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}}
|}

2)

{|
| valign="top" |
{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}}
|}
|
| valign="top" |
|
{| class="wikitable"
! !! A || B || C
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}}
|- align="center"
! BC
| {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}}
|}
|}

Получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь.

===== Другой пример =====

Пусть {{Формула|f=R = (A, B, C, D, E, F, P, S)}}

{{Формула|f=\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)}}

{{Формула|f=F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)}}

Доказать, что {{Формула|f=\rho}} обладает свойством соединения без потерь.

1)

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

2)

первый просмотр:

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

второй просмотр:

{| class="wikitable"
! !! A || B || C || D || E || F || P || S
|- align="center"
! AB
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="#32CD32" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}
|- align="center"
! ACDPS
| {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! BCPS
| {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}}
|- align="center"
! DEF
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}}
|}

Вот и получили строку, сплошь состоящую из {{Формула|f=a}}. Значит {{Формула|f=\rho}} обладает свойством соединения без потерь.

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №2 - Функциональные зависимости

2012-09-18T07:55:57Z

LenaP: /* Пример построения множества ФЗ */

Функциональные зависимости, замыкание множества функциональных зависимостей, атрибутов.

== Функциональные зависимости ==

Пусть <math>R=(A_1 ... A_n)</math> является функциональной схемой отношения и <math>X</math>, <math>Y</math> - некоторые подмножества атрибутов этой схемы. Говорят, что <math>X</math> функционально определяет <math>Y</math> (<math>X\rightarrow Y</math>), если в любом экземпляре отношения со схемой <math>R</math> не существует двух кортежей, совпадающих по подмножеству <math>X</math> и не совпадающих по подмножеству <math>Y</math>

Иначе говоря, если два кортежа совпадают по <math>x</math>, то они должны совпадать и по <math>y</math>

Например, <math>R=(A_1, A_2, A_3, A_4)</math>, есть зависимости:
* (1): <math>A_1\rightarrow A_2</math>
* (2): <math>A_1A_3\rightarrow A_4</math>

Предположим, что имеет место один экземпляр отношения со схемой <math>R</math>

{| class="wikitable"
! !! <math>A_1</math> !! <math>A_2</math> !! <math>A_3</math> !! <math>A_4</math>
|- align="center"
| rowspan="3" | <math>R</math> || фирма X || улица Ленина, д.1 || сахар || 40
|- align="center"
| фирма X || улица Ленина, д.1 || карамель || 50
|- align="center"
| фирма X || улица Ленина, д.1 || пастила || 90
|}

Вторая ФЗ (2) имеет место быть, так как нет двух кортежей, совпадающих по этой паре. А первая ФЗ (1) не имеет место быть.

== Замыкание множества функциональных зависимостей ==

Пусть <math>R</math> - универсальная схема отношения, а <math>F</math> - исходное множество функциональной зависимости на этой схеме. Замыканием <math>F</math> называется всё множество функциональной зависимости, которое логически следует из <math>F</math> - обозначается как <math>F^+</math>

Функциональная зависимость логически следует из <math>F</math>, если её можно вывести (получить) с помощью аксиом Армстронга.

=== Аксиомы Армстронга ===

Или правила вывода функциональной зависимости. Существуют различные интерпретации аксиом, но все эквивалентны. Потому приведём только один вариант.

Аксиомы Армстронга являются надёжными и полными.

'''Надёжность''' - если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ <math>F</math>

'''Полнота''' - если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга.

==== Рефлексивность ====

Если <math>Y \subseteq X \subseteq R</math>

то <math>X\rightarrow Y</math>. Тривиальная аксиома.

==== Дополнение ====

Если <math>X\rightarrow Y</math>,

<math>Z \subseteq R</math> (<math>Z</math> может быть пустым),

тогда <math>X\bigcup Y\rightarrow Z</math> или <math>XZ\rightarrow YZ</math>

==== Транзитивность ====

Если <math>X\rightarrow Y</math>

а <math>Y\rightarrow Z</math>

то <math>X\rightarrow Z</math>

=== Пример построения множества ФЗ ===

Пусть задана УСО (универсальная схема отношения) <math>R=(A, B, C)</math> и зависимости <math>F=(A\rightarrow B, B\rightarrow C)</math>

# <math>A\rightarrow A</math>, <math>B\rightarrow B</math>, <math>C\rightarrow C</math>, <math>AB\rightarrow A</math>, <math>AB\rightarrow B</math>, <math>AC\rightarrow A</math>, <math>AC\rightarrow C</math>, <math>BC\rightarrow B</math>, <math>BC\rightarrow C</math>, <math>ABC\rightarrow A</math>, <math>ABC\rightarrow C</math>, <math>AB\rightarrow AB</math>, <math>AC\rightarrow AC</math>, <math>BC\rightarrow BC</math>, <math>ABC\rightarrow AB</math>, <math>ABC\rightarrow AC</math>, <math>ABC\rightarrow BC</math>, <math>ABC\rightarrow ABC</math> 
# <math>A\rightarrow AB</math> (1ФЗ и пополняем A), <math>AC\rightarrow BC</math>, <math>B\rightarrow BC</math> (2 ФЗ и пополняем B), <math>AB\rightarrow AC</math>, <math>AC\rightarrow ABC</math>, <math>AB\rightarrow ABC</math>, <math>AB\rightarrow BC</math>, <math>A\rightarrow AC</math> 
# <math>A\rightarrow C</math> (1 и 2 ФЗ), <math>A\rightarrow ABC</math>

Всё, замыкание (<math>F^+</math>) построено. Все перечисленные зависимости образуют замыкание.

=== Лемма ===

Справедливы следующие правила. Для их доказательства необходимо пополнить ФЗ так, чтобы можно было использовать аксиомы.

==== Правило объединения ====

Если <math>X\rightarrow Y</math> и <math>X\rightarrow Z</math>, то <math>X\rightarrow YZ</math>

Доказательство:
# <math>X\rightarrow XY</math> (1 ФЗ и пополняем X);
# <math>XY\rightarrow YZ</math> (2 ФЗ и пополняем Y);
# <math>X\rightarrow YZ</math> (по аксиоме транзитивности).

==== Правило декомпозиции ====

Если <math>X\rightarrow Y</math>, а <math>Z \subseteq Y</math>, то <math>X\rightarrow Z</math>

Доказательство:
# <math>X\rightarrow Y</math> (по условию);
# <math>Y\rightarrow Z</math> (по аксиоме рефлексивности);
# <math>X\rightarrow Z</math> (по аксиоме транзитивности).

==== Правило псевдотранзитивности ====

Если <math>X\rightarrow Y</math> и <math>WY\rightarrow Z</math>, то <math>WX\rightarrow Z</math>

Доказательство:
# <math>WX\rightarrow WY</math> (1 ФЗ и пополняем W);
# <math>WY\rightarrow Z</math> (по условию);
# <math>WX\rightarrow Z</math> (по аксиоме транзитивности).

== Замыкание множества атрибутов ==

Замыкание <math>F^+</math> может включать в себя очень большое количество ФЗ. Например:

<math>F=(X\rightarrow A_1, X\rightarrow A_2 ... X\rightarrow A_n)</math>

<math>X\rightarrow Y \subseteq F^+</math>

<math>Y \subseteq (A_1, A_2 ... A_n)</math> и таких подмножеств может быть <math>2^n</math>

Поэтому "в лоб" замыкание <math>F^+</math> никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ <math>X\rightarrow Y</math> к <math>F^+</math>

Для этого применяется ''замыкание множества атрибутов''. Пусть <math>R</math> - универсальная схема отношения, а <math>X</math> - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов <math>X^+</math> называется совокупность атрибутов <math>A_{i1}, A_{i2} ... A_{ik}</math> таких, что <math>X\rightarrow A_{i1}, X\rightarrow A_{i2} ... X\rightarrow A_{ik}</math>

=== Алгоритм построения ===

Алгоритм является итерационной процедурой.

# полагаем <math>i = 0</math> и <math>X_0^+=X</math>, а <math>X_i^+</math> - замыкание множества атрибутов на i-том шаге;
# <math>X _{i+1} ^+ = X _i ^+ \bigcup V</math>, где V - такое множество атрибутов в F, и <math>Y\rightarrow Z</math>, <math>Y \subseteq X _i ^+</math>, <math>V \subseteq Z</math>;
# если <math>X_{i+1}^+ = X_i^+</math>, то <math>X^+ = X_i^+</math>, иначе <math>i = i + 1</math> и возвращаемся в пункт 2.

==== Пример построения ====

Пусть <math>R=(A, B, C, D, E, G)</math>

<math>F=(AB\rightarrow C, C\rightarrow A, BC\rightarrow D, ACD\rightarrow B, D\rightarrow EG, BE\rightarrow C, CG\rightarrow BD, CE\rightarrow AG)</math>

<math>X = BD</math>

Надо построить <math>X^+</math>:

# <math>i = 0</math>, <math>X _0 ^+ = BD</math>
#
{| class="wikitable"
! <math>i</math> !! <math>Y\rightarrow Z</math>, для которых <math>Y \subseteq X_i^+</math> !! <math>V\subseteq Z</math> !! <math>X_{i+1}^+ = X_i^+\bigcup V</math>
|- align="center"
| 0 || <math>D\rightarrow EG</math> || <math>EG</math> || <math>BDEG</math>
|- align="center"
| 1 || <math>BE\rightarrow C</math> || <math>C</math> || <math>BDEGC</math>
|- align="center"
| 2 || <math>C\rightarrow A</math> <math>BC\rightarrow D</math> <math>CG\rightarrow BD</math> <math>CE\rightarrow AG</math> || <math>A</math> || <math>BDEGCA</math>
|- align="center"
| 3 || <math>AB\rightarrow C</math> <math>ACD\rightarrow B</math> || - || <math>BDEGCA</math>
|}

Получили, что <math>X_4^+ = X_3^+</math>

значит <math>X^+ = X_3^+ = BDEGCA</math>

Это означает, что имеют место следующие ФЗ: <math>BD\rightarrow B</math>, <math>BD\rightarrow D</math>, <math>BD\rightarrow E</math>, <math>BD\rightarrow G</math>, <math>BD\rightarrow C</math>, <math>BD\rightarrow A</math>, и все они <math>\subseteq F^+</math>

Короче, чтобы проверить <math>X\rightarrow Y \subseteq F^+</math>, необходимо построить <math>X^+</math>

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Семинар №1 - Операции реляционной алгебры

2012-09-18T07:14:02Z

LenaP: /* Задача №7 */

Операции реляционной алгебры и их связь с SQL.

== Операторы SQL ==

=== SELECT ===

SELECT - выборка, DISTINCT - исключая.

<source lang=sql>SELECT [DISTINCT] * | атрибуты
FROM таблицы
WHERE условие</source>

=== UPDATE ===

UPDATE - обновление, изменение.

<source lang=sql>UPDATE таблица
SET атрибут = выражение
WHERE условие</source>

=== INSERT ===

INSERT - вставка, добавление новых записей.

<source lang=sql>INSERT
INTO таблица
записи</source>

=== DELETE ===

DELETE - удаление записей.

<source lang=sql>DELETE
FROM таблица
WHERE условие</source>

== Предметная область, используемая в задачах ==

Этого семинара, само собой.

=== Таблицы ===

Таблицы <math>\rho=(S,P,SP)</math>

*<math>S</math> - поставщики.
**SN - номер поставщика;
**SF - фамилия;
**SS - статус;
**SG - город.

*<math>P</math> - деталь.
** PN - номер детали, ключ;
** PF - название детали;
** PC - цена за единицу.

*<math>SP</math> - поставка.
** N - номер поставщика;
** PN - номер детали;
** kol - количество поставляемых деталей.

=== Примеры экземпляров отношений ===

{|
| valign="top" |
{| class="wikitable"
|+ <math>S</math>
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S2 || Петров || 40 || Самара
|- align="center"
| S3 || Кротов || 100 || Москва
|}
|
| valign="top" |
|
{| class="wikitable"
|+ <math>P</math>
! PN || PF || PC
|- align="center"
| P1 || болт || 20
|- align="center"
| P2 || гайка || 25
|- align="center"
| P3 || шайба || 10
|- align="center"
| P4 || гайка || 30
|}
|
| valign="top" |
|
{| class="wikitable"
|+ <math>SP</math>
! SN || PN || kol
|- align="center"
| S1 || P1 || 100
|- align="center"
| S1 || P3 || 200
|- align="center"
| S2 || P3 || 150
|- align="center"
| S3 || P3 || 50
|}
|}

== Задачи ==

=== Задача №1 ===

Проекция. Найти города, где проживают поставщики.

<math>t=\Pi_{SG}(S)</math>

Получится:

{| class="wikitable"
! SG
|- align="center"
| Москва
|- align="center"
| Самара
|}

<source lang=sql>SELECT DISTINCT SG FROM S</source>

=== Задача №2 ===

Селекция. Найти поставщиков со статусом больше 70.

<math>t=\sigma_{SS>70}(S)</math>

Получится:

{| class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S3 || Кротов || 100 || Москва
|}

<source lang=sql>SELECT * FROM S WHERE SS > 70</source>

=== Задача №3 ===

Найти номера и фамилии поставщиков со статусом меньше 80.

<math>t=\Pi_{SN,SF}(\sigma_{SS<80}(S))</math>

Получится:

{| class="wikitable"
! SN || SF
|- align="center"
| S2 || Петров
|}

<source lang=sql>SELECT SN, SF
FROM S
WHERE SS < 80</source>

=== Задача №4 ===

Удалить все поставки поставщика с номером S1.

<math>SP = SP - \sigma_{SN=S1}(SP)</math>

Получится:

{|+SP | class="wikitable"
! SN || PN || kol
|- align="center"
| S2 || P3 || 150
|- align="center"
| S3 || P3 || 50
|}

<source lang=sql>DELETE
FROM SP
WHERE SN = S1</source>

=== Задача №5 ===

Добавить в таблицу S новых поставщиков из таблицы SNEW.

{|+SNEW | class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S4 || Петров || 30 || Тверь
|- align="center"
| S5 || Сидоров || 50 || Тверь
|}

<math>S = SP\bigcup S</math>

Получится:

{|+ таблица SNEW | class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S2 || Петров || 40 || Самара
|- align="center"
| S3 || Кротов || 100 || Москва
|- align="center"
| S4 || Петров || 30 || Тверь
|- align="center"
| S5 || Сидоров || 50 || Тверь
|}

<source lang=sql>INSERT
INTO S
SELECT * FROM SNEW</source>

=== Задача №6 ===

Найти номера поставщиков, поставляющих детали по цене меньше 30.

<math>r = \sigma_{PC<30}(P)</math>

<math>t = SP \bowtie_{PN} r </math>

Получится:

{| class="wikitable"
! PN !! PF !! PC !! SN !! kol
|- align="center"
| P1 || болт || 20 || S1 || 100
|- align="center"
| P3 || шайба || 10 || S1 || 200
|- align="center"
| P3 || шайба || 10 || S2 || 150
|- align="center"
| P3 || шайба || 10 || S3 || 50
|}

<math>z = \Pi_{SN}(t)</math>

Получится:

{| class="wikitable"
! SN
|- align="center"
| S1
|- align="center"
| S2
|- align="center"
| S3
|}

<source lang=sql>SELECT DISTINCT SN
FROM SP, P
WHERE PC < 30 AND SP.PN = P.PN</source>

=== Задача №7 ===

Найти номера и фамилии поставщиков, поставляющих шайбы в количестве больше 100.

<math>w = \sigma_{PF=}</math>'шайба'<math>(P)</math>

<math>t = w \bowtie_{PN}SP </math>

<math>z = \sigma_{kol>100}(t)</math>

<math>q = z \bowtie_{SN} S</math>

<math>x = \Pi_{SN,SF}(q)</math>

Получится:

{| class="wikitable"
! SN || SF
|- align="center"
| S1 || Иванов
|- align="center"
| S2 || Петров
|}

<source lang=sql>SELECT SN, SF
FROM S, P, SP
WHERE PF = шайба AND kol > 100 AND P.PN = SP.PN AND SP.SN = S.SN</source>

=== Задача №8 ===

Все поставщики переехали из Москвы в Питер. Модифицировать таблицу S.

[[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Семинар №1 - Операции реляционной алгебры

2012-09-18T07:01:20Z

LenaP: /* Задача №6 */

Операции реляционной алгебры и их связь с SQL.

== Операторы SQL ==

=== SELECT ===

SELECT - выборка, DISTINCT - исключая.

<source lang=sql>SELECT [DISTINCT] * | атрибуты
FROM таблицы
WHERE условие</source>

=== UPDATE ===

UPDATE - обновление, изменение.

<source lang=sql>UPDATE таблица
SET атрибут = выражение
WHERE условие</source>

=== INSERT ===

INSERT - вставка, добавление новых записей.

<source lang=sql>INSERT
INTO таблица
записи</source>

=== DELETE ===

DELETE - удаление записей.

<source lang=sql>DELETE
FROM таблица
WHERE условие</source>

== Предметная область, используемая в задачах ==

Этого семинара, само собой.

=== Таблицы ===

Таблицы <math>\rho=(S,P,SP)</math>

*<math>S</math> - поставщики.
**SN - номер поставщика;
**SF - фамилия;
**SS - статус;
**SG - город.

*<math>P</math> - деталь.
** PN - номер детали, ключ;
** PF - название детали;
** PC - цена за единицу.

*<math>SP</math> - поставка.
** N - номер поставщика;
** PN - номер детали;
** kol - количество поставляемых деталей.

=== Примеры экземпляров отношений ===

{|
| valign="top" |
{| class="wikitable"
|+ <math>S</math>
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S2 || Петров || 40 || Самара
|- align="center"
| S3 || Кротов || 100 || Москва
|}
|
| valign="top" |
|
{| class="wikitable"
|+ <math>P</math>
! PN || PF || PC
|- align="center"
| P1 || болт || 20
|- align="center"
| P2 || гайка || 25
|- align="center"
| P3 || шайба || 10
|- align="center"
| P4 || гайка || 30
|}
|
| valign="top" |
|
{| class="wikitable"
|+ <math>SP</math>
! SN || PN || kol
|- align="center"
| S1 || P1 || 100
|- align="center"
| S1 || P3 || 200
|- align="center"
| S2 || P3 || 150
|- align="center"
| S3 || P3 || 50
|}
|}

== Задачи ==

=== Задача №1 ===

Проекция. Найти города, где проживают поставщики.

<math>t=\Pi_{SG}(S)</math>

Получится:

{| class="wikitable"
! SG
|- align="center"
| Москва
|- align="center"
| Самара
|}

<source lang=sql>SELECT DISTINCT SG FROM S</source>

=== Задача №2 ===

Селекция. Найти поставщиков со статусом больше 70.

<math>t=\sigma_{SS>70}(S)</math>

Получится:

{| class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S3 || Кротов || 100 || Москва
|}

<source lang=sql>SELECT * FROM S WHERE SS > 70</source>

=== Задача №3 ===

Найти номера и фамилии поставщиков со статусом меньше 80.

<math>t=\Pi_{SN,SF}(\sigma_{SS<80}(S))</math>

Получится:

{| class="wikitable"
! SN || SF
|- align="center"
| S2 || Петров
|}

<source lang=sql>SELECT SN, SF
FROM S
WHERE SS < 80</source>

=== Задача №4 ===

Удалить все поставки поставщика с номером S1.

<math>SP = SP - \sigma_{SN=S1}(SP)</math>

Получится:

{|+SP | class="wikitable"
! SN || PN || kol
|- align="center"
| S2 || P3 || 150
|- align="center"
| S3 || P3 || 50
|}

<source lang=sql>DELETE
FROM SP
WHERE SN = S1</source>

=== Задача №5 ===

Добавить в таблицу S новых поставщиков из таблицы SNEW.

{|+SNEW | class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S4 || Петров || 30 || Тверь
|- align="center"
| S5 || Сидоров || 50 || Тверь
|}

<math>S = SP\bigcup S</math>

Получится:

{|+ таблица SNEW | class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S2 || Петров || 40 || Самара
|- align="center"
| S3 || Кротов || 100 || Москва
|- align="center"
| S4 || Петров || 30 || Тверь
|- align="center"
| S5 || Сидоров || 50 || Тверь
|}

<source lang=sql>INSERT
INTO S
SELECT * FROM SNEW</source>

=== Задача №6 ===

Найти номера поставщиков, поставляющих детали по цене меньше 30.

<math>r = \sigma_{PC<30}(P)</math>

<math>t = SP \bowtie_{PN} r </math>

Получится:

{| class="wikitable"
! PN !! PF !! PC !! SN !! kol
|- align="center"
| P1 || болт || 20 || S1 || 100
|- align="center"
| P3 || шайба || 10 || S1 || 200
|- align="center"
| P3 || шайба || 10 || S2 || 150
|- align="center"
| P3 || шайба || 10 || S3 || 50
|}

<math>z = \Pi_{SN}(t)</math>

Получится:

{| class="wikitable"
! SN
|- align="center"
| S1
|- align="center"
| S2
|- align="center"
| S3
|}

<source lang=sql>SELECT DISTINCT SN
FROM SP, P
WHERE PC < 30 AND SP.PN = P.PN</source>

=== Задача №7 ===

Найти номера и фамилии поставщиков, поставляющих шайбы в количестве больше 100.

<math>w = \sigma_{PF=}</math>'шайба'<math>(P)</math>

<math>t = w \bowtie_{PN}SP </math>

<math>z = \sigma_{kol>100}(t)</math>

<math>q = z \bowtie_{SN} S</math>

<math>x = \Pi_{SN,SF}(q)</math>

Получится:

{| class="wikitable"
! SN || SF
|- align="center"
| S1 || Иванов
|- align="center"
| S2 || Петров
|}

<source lang=sql>SELECT SN, SF
FROM S, P, SP
WHERE kol > 100 AND P.PN = SP.PN AND SP.SN = S.SN</source>

=== Задача №8 ===

Все поставщики переехали из Москвы в Питер. Модифицировать таблицу S.

[[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №1 - Операции реляционной алгебры

2012-09-03T18:42:22Z

LenaP: /* Естественное соединение */

== Определения ==

=== Схема отношения ===

Это поименованная совокупность атрибутов.

<math>R = (A_1, ..., A_n)</math>, где <math>A_i</math> - некоторый атрибут из домена отношения.

<math>R = (</math>идентификатор поставщика, адрес, товар, цена<math>)=(A_1, A_2, A_3, A_4)</math>.

Здесь <math>(A_1, A_3)</math> - ключ, определяющий запись.

=== Степень схемы отношения ===

Это количество атрибутов в схеме.

Для <math>R = (A_1, A_2, A_3, A_4)</math> степень равна 4.

=== Экземпляр отношения ===

Это конкретная таблица с данной схемой отношения.

<math>R = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>.

{| class="wikitable"
! Идентификатор !! Адрес !! Товар !! Цена
|- align="center"
| ОАО "Х" || Ленина, 2 || сахар || 40
|- align="center"
| ОАО "У" || Комсомола, 25 || соль || 5
|}

=== Кортеж ===

Любая одна строка в таблице экземпляра отношения.

=== Схема БД.===

<math>A</math> - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

<math>R_1, ..., R_n</math> - совокупность атрибутов.

Тогда <math>\rho=(R_1, ..., R_n)</math> называется схемой БД.

Пример:

<math>A = (A_1, A_2, A_3, A_4)</math> 

и две схемы: <math>R_1 = (A_1, A_2)</math> и <math>R_2 = (A_1, A_3, A_4)</math> 

Так как <math>R_1\bigcup R_2 = A</math>, то <math>\rho = (R_1, R_2)</math>.

== Примеры схем БД ==

=== Пример "плохой" схемы БД ===

Пусть <math>A = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>

и есть одна схема <math>\rho = R_1 = A</math>

Данная схема БД обладает следующими недостатками (аномалиями):
* избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
* потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
* аномалия включения кортежа. В выбранном отношении <math>R</math> пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что <math>R_1</math> не находится в {{Википедия|Третья_нормальная_форма|3НФ}}

=== Пример "хорошей" схемы БД ===

Пусть <math>A = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>

<math>R_1 = (</math>идентификатор, адрес<math>)</math>

<math>R_2 = (</math>товар, цена<math>)</math>

Схема <math>\rho = (R_1, R_2)</math> находится в 3НФ и не обладает перечисленными выше недостатками.

== Основные операции реляционной алгебры ==

=== Объединение отношений ===

<math>R=R_1\bigcup R_2</math>

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо <math>R_1</math>, либо <math>R_2</math>.
{|
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_1</math>
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_2</math>
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="3" | <math>R</math>
| 1 || 2
|- align="center"
| 3 || 4
|- align="center"
| 5 || 6
|}

Дублирование кортежей не допускается.

=== Пересечение отношений ===

<math>R = R_1\bigcap R_2</math>

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и <math>R_1</math>, и <math>R_2</math>

{|
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_1</math>
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_2</math>
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! <math>R</math>
| 1 || 2
|}

=== Разность отношений ===

<math>R = R_1 - R_2</math>

Разность отношений - это отношение, кортежи которого принадлежат <math>R_1</math> и не принадлежат <math>R_2</math>

{|
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_1</math>
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_2</math>
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! <math>R</math>
| 3 || 4
|}

=== Декартово произведение ===

<math>R, S</math> - две схемы отношения со степенями <math>k_1</math> и <math>k_2</math>

<math>t = R \times S</math>

Декартово произведение - это отношение <math>t</math> со степенью <math>k_1 + k_2</math>, кортежи которого получаются {{Википедия|Конкатенация|конкатенацией}} кортежей из отношений <math>R</math> и <math>S</math>.

{|
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R</math>
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_3</math>
|- align="center"
! rowspan="2" | <math>S</math>
| 5 || 6
|- align="center"
| 7 || 8
|}
|}

{| class="wikitable"
! !!<math>R.A_2</math> !! <math>A_2</math> !! <math>S.A_1</math> !! <math>A_3</math>
|- align="center"
! rowspan="4" | <math>t</math>
| 1 || 2 || 5 || 6
|- align="center"
| 1 || 2 || 7 || 8
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 8
|}

=== Проекция ===

<math>t = \Pi_{A_{i1} ... A_{ik}}(R)</math>

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов <math>A_{i1} ... A_{ik}</math> исходного отношения <math>R</math>.

{| class="wikitable"
! !! <math>A_1</math> !! <math>A_2</math> !! <math>A_3</math> !! <math>A_4</math>
|- align="center"
! rowspan="4" | <math>R</math>
| 1 || 2 || 3 || 4
|- align="center"
| 7 || 8 || 9 || 10
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 6
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_4</math>
|- align="center"
! rowspan="3" | <math>t = \Pi_{A_1, A_4}(R)</math>
| 1 || 4
|- align="center"
| 7 || 10
|- align="center"
| 3 || 6
|}

=== Селекция ===

<math>t = \sigma_F(R)</math>

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению <math>R</math> и удовлетворяет логическому условию <math>F</math>.

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="3" | <math>R</math>
| 1 || 2
|- align="center"
| 9 || 8
|- align="center"
| 3 || 3
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_4</math>
|- align="center"
! rowspan="2" | <math>t = \sigma_{A_1\leq A_2}(R)</math>
| 1 || 2
|- align="center"
| 3 || 3
|}

=== Естественное соединение ===

<math>t = R\vartriangleright\vartriangleleft S</math>

Определение этой операции следует из способа построения естественного соединения.

{|
| valign="top" |
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math> !! <math>A_3</math>
|- align="center"
! rowspan="2" | <math>R</math>
| 1 || 2 || 3
|- align="center"
| 4 || 6 || 7
|}
| valign="top" |
{| class="wikitable" valign="top"
! !! <math>A_1</math> !! <math>A_2</math> !! <math>A_4</math> !! <math>A_5</math>
|- align="center"
! rowspan="3" | <math>S</math>
| 1 || 2 || 7 || 8
|- align="center"
| 8 || 9 || 10 || 11
|- align="center"
| 5 || 6 || 9 || 16
|}
|}

Построение естественного соединения:

:1) построить декартово произведение <math>R\times S</math>

{| class="wikitable"
! !! <math>R.A_1</math> !! <math>R.A_2</math> !! <math>A_3</math> !! <math>S.A_1</math> !! <math>S.A_2</math>!! <math>A_4</math> !! <math>A_5</math>
|- align="center"
! rowspan="6" | <math>t_1</math>
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 1 || 2 || 3 || 8 || 9 || 10 || 11
|- align="center"
| 1 || 2 || 3 || 4 || 6 || 9 || 16
|- align="center"
| 4 || 6 || 7 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 8 || 9 || 10 || 11
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:2) выбрать из этого произведения кортежи по условию <math>R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik}</math>, где <math>A_1 = A_k</math> - общие атрибуты в схеме отношений <math>R</math> и <math>S</math> (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

{| class="wikitable"
! !! <math>R.A_1</math> !! <math>R.A_2</math> !! <math>A_3</math> !! <math>S.A_1</math> !! <math>S.A_2</math>!! <math>A_4</math> !! <math>A_5</math>
|- align="center"
! rowspan="2" | <math>t_2</math>
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:3) удалить из полученного отношения <math>S.A_{i1} ... S.A_{ik}</math>, потому что они будут дублирующими.

{| class="wikitable"
! !! <math>R.A_1</math> !! <math>R.A_2</math> !! <math>A_3</math> !! <math>A_4</math> !! <math>A_5</math>
|- align="center"
! rowspan="2" | <math>t_3</math>
| 1 || 2 || 3 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 9 || 16
|}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)|Л]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №1 - Операции реляционной алгебры

2012-09-03T18:32:45Z

LenaP: /* Естественное соединение */

== Определения ==

=== Схема отношения ===

Это поименованная совокупность атрибутов.

<math>R = (A_1, ..., A_n)</math>, где <math>A_i</math> - некоторый атрибут из домена отношения.

<math>R = (</math>идентификатор поставщика, адрес, товар, цена<math>)=(A_1, A_2, A_3, A_4)</math>.

Здесь <math>(A_1, A_3)</math> - ключ, определяющий запись.

=== Степень схемы отношения ===

Это количество атрибутов в схеме.

Для <math>R = (A_1, A_2, A_3, A_4)</math> степень равна 4.

=== Экземпляр отношения ===

Это конкретная таблица с данной схемой отношения.

<math>R = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>.

{| class="wikitable"
! Идентификатор !! Адрес !! Товар !! Цена
|- align="center"
| ОАО "Х" || Ленина, 2 || сахар || 40
|- align="center"
| ОАО "У" || Комсомола, 25 || соль || 5
|}

=== Кортеж ===

Любая одна строка в таблице экземпляра отношения.

=== Схема БД.===

<math>A</math> - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

<math>R_1, ..., R_n</math> - совокупность атрибутов.

Тогда <math>\rho=(R_1, ..., R_n)</math> называется схемой БД.

Пример:

<math>A = (A_1, A_2, A_3, A_4)</math> 

и две схемы: <math>R_1 = (A_1, A_2)</math> и <math>R_2 = (A_1, A_3, A_4)</math> 

Так как <math>R_1\bigcup R_2 = A</math>, то <math>\rho = (R_1, R_2)</math>.

== Примеры схем БД ==

=== Пример "плохой" схемы БД ===

Пусть <math>A = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>

и есть одна схема <math>\rho = R_1 = A</math>

Данная схема БД обладает следующими недостатками (аномалиями):
* избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
* потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
* аномалия включения кортежа. В выбранном отношении <math>R</math> пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
* аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.
Первопричиной этих недостатков является то, что <math>R_1</math> не находится в {{Википедия|Третья_нормальная_форма|3НФ}}

=== Пример "хорошей" схемы БД ===

Пусть <math>A = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>

<math>R_1 = (</math>идентификатор, адрес<math>)</math>

<math>R_2 = (</math>товар, цена<math>)</math>

Схема <math>\rho = (R_1, R_2)</math> находится в 3НФ и не обладает перечисленными выше недостатками.

== Основные операции реляционной алгебры ==

=== Объединение отношений ===

<math>R=R_1\bigcup R_2</math>

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо <math>R_1</math>, либо <math>R_2</math>.
{|
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_1</math>
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_2</math>
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="3" | <math>R</math>
| 1 || 2
|- align="center"
| 3 || 4
|- align="center"
| 5 || 6
|}

Дублирование кортежей не допускается.

=== Пересечение отношений ===

<math>R = R_1\bigcap R_2</math>

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и <math>R_1</math>, и <math>R_2</math>

{|
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_1</math>
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_2</math>
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! <math>R</math>
| 1 || 2
|}

=== Разность отношений ===

<math>R = R_1 - R_2</math>

Разность отношений - это отношение, кортежи которого принадлежат <math>R_1</math> и не принадлежат <math>R_2</math>

{|
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_1</math>
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R_2</math>
| 5 || 6
|- align="center"
| 1 || 2
|}
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! <math>R</math>
| 3 || 4
|}

=== Декартово произведение ===

<math>R, S</math> - две схемы отношения со степенями <math>k_1</math> и <math>k_2</math>

<math>t = R \times S</math>

Декартово произведение - это отношение <math>t</math> со степенью <math>k_1 + k_2</math>, кортежи которого получаются {{Википедия|Конкатенация|конкатенацией}} кортежей из отношений <math>R</math> и <math>S</math>.

{|
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="2" | <math>R</math>
| 1 || 2
|- align="center"
| 3 || 4
|}
|
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_3</math>
|- align="center"
! rowspan="2" | <math>S</math>
| 5 || 6
|- align="center"
| 7 || 8
|}
|}

{| class="wikitable"
! !!<math>R.A_2</math> !! <math>A_2</math> !! <math>S.A_1</math> !! <math>A_3</math>
|- align="center"
! rowspan="4" | <math>t</math>
| 1 || 2 || 5 || 6
|- align="center"
| 1 || 2 || 7 || 8
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 8
|}

=== Проекция ===

<math>t = \Pi_{A_{i1} ... A_{ik}}(R)</math>

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов <math>A_{i1} ... A_{ik}</math> исходного отношения <math>R</math>.

{| class="wikitable"
! !! <math>A_1</math> !! <math>A_2</math> !! <math>A_3</math> !! <math>A_4</math>
|- align="center"
! rowspan="4" | <math>R</math>
| 1 || 2 || 3 || 4
|- align="center"
| 7 || 8 || 9 || 10
|- align="center"
| 3 || 4 || 5 || 6
|- align="center"
| 3 || 4 || 7 || 6
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_4</math>
|- align="center"
! rowspan="3" | <math>t = \Pi_{A_1, A_4}(R)</math>
| 1 || 4
|- align="center"
| 7 || 10
|- align="center"
| 3 || 6
|}

=== Селекция ===

<math>t = \sigma_F(R)</math>

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению <math>R</math> и удовлетворяет логическому условию <math>F</math>.

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math>
|- align="center"
! rowspan="3" | <math>R</math>
| 1 || 2
|- align="center"
| 9 || 8
|- align="center"
| 3 || 3
|}

{| class="wikitable"
! !!<math>A_1</math> !! <math>A_4</math>
|- align="center"
! rowspan="2" | <math>t = \sigma_{A_1\leq A_2}(R)</math>
| 1 || 2
|- align="center"
| 3 || 3
|}

=== Естественное соединение ===

<math>t = R\vartriangleright\vartriangleleft S</math>

Определение этой операции следует из способа построения естественного соединения.

{|
| valign="top" |
{| class="wikitable"
! !!<math>A_1</math> !! <math>A_2</math> !! <math>A_3</math>
|- align="center"
! rowspan="2" | <math>R</math>
| 1 || 2 || 3
|- align="center"
| 4 || 6 || 7
|}
| valign="top" |
{| class="wikitable" valign="top"
! !! <math>A_1</math> !! <math>A_2</math> !! <math>A_4</math> !! <math>A_5</math>
|- align="center"
! rowspan="3" | <math>S</math>
| 1 || 2 || 7 || 8
|- align="center"
| 8 || 9 || 10 || 11
|- align="center"
| 5 || 6 || 9 || 16
|}
|}

Построение естественного соединения:

:1) построить декартово произведение <math>R\times S</math>

{| class="wikitable"
! !! <math>R.A_1</math> !! <math>R.A_2</math> !! <math>A_3</math> !! <math>S.A_1</math> !! <math>S.A_2</math>!! <math>A_4</math> !! <math>A_5</math>
|- align="center"
! rowspan="6" | <math>t_1</math>
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 1 || 2 || 3 || 8 || 9 || 10 || 11
|- align="center"
| 1 || 2 || 3 || 4 || 6 || 9 || 16
|- align="center"
| 4 || 6 || 7 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 8 || 9 || 10 || 11
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:2) выбрать из этого произведения кортежи по условию <math>R.A_{i1} = S.A_{i1} ... R.A_{ik} = S.A_{ik}</math>, где <math>A_1 = A_k</math> - общие атрибуты в схема отношений <math>R</math> и <math>S</math> (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

{| class="wikitable"
! !! <math>R.A_1</math> !! <math>R.A_2</math> !! <math>A_3</math> !! <math>S.A_1</math> !! <math>S.A_2</math>!! <math>A_4</math> !! <math>A_5</math>
|- align="center"
! rowspan="2" | <math>t_2</math>
| 1 || 2 || 3 || 1 || 2 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 4 || 6 || 9 || 16
|}

:3) удалить из полученного отношения <math>S.A_{i1} ... S.A_{ik}</math>, потому что они будут дублирующими.

{| class="wikitable"
! !! <math>R.A_1</math> !! <math>R.A_2</math> !! <math>A_3</math> !! <math>A_4</math> !! <math>A_5</math>
|- align="center"
! rowspan="2" | <math>t_3</math>
| 1 || 2 || 3 || 7 || 8
|- align="center"
| 4 || 6 || 7 || 9 || 16
|}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)|Л]]
[[Категория:Конспекты лекций и семинаров]]