Тема 1. 4 Основы реляционной алгебры

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

2. Операции над отношениями: проекция, селекция, соединение.

3. Операции над отношениями: объединение, разность, деление, пересечение, декартово произведение.

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

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

Под высказыванием в алгебре логики понимают, что может иметь место только одно из двух указанных значений (например: ≪Москва — столица России≫ — истинное высказывание; ≪снег черен≫ — ложное высказывание).

Отдельные высказывания в алгебре логики обозначаются буквами какого-либо алфавита,например: А, В, С. Истинность или ложность высказываний называется их значениями истинности. В алгебре логики принято отождествлять истинность высказывания с числом 1, а ложность высказывания — с числом 0. Запись А = 1 и С = 0 означает, что А истинно и что С ложно.

Из одного или нескольких простых высказываний можно составлять сложные высказывания.

К числу основных логических операций относятся следующие: отрицание, конъюнкция, дизъюнкция, эквивалентность, импликация.

Логические функции задаются аналитически (формулами), таблицами истинности, графически (диаграммы Венна).

Отрицание высказывания. Отрицание высказывания А — это высказывание, которое истинно, когда А ложно, и ложно, когда А истинно;

обозначается: А; читается: ≪не А≫.

Конъюнкция двух высказываний. Конъюнкция двух высказываний— это сложное высказывание, которое истинно в случае истинности обоих высказываний, его образующих, и ложно в остальных случаях. Конъюнкция двух высказываний обозначается: А ˄ В; читается ≪А и В≫. Знак конъюнкции ≪˄≫ имеет смысл союза ≪и≫. Операция конъюнкции имеет также смысл логического умножения и может обозначается знаком ≪&≫.

Дизъюнкция двух высказываний. Дизъюнкция двух высказываний— это сложное высказывание, которое ложно в случае ложности обоих составляющих его высказываний и истинно в остальных случаях.

Операция дизъюнкции обозначается: A v В; читается: ≪А или В≫ (другое обозначение: А + В; другое название — ≪логическое сложение≫

Таблицы истинности

Отрицание

А	В
1	0
0	1

Конъюнкция

А	В	А˄В
1	1	1
0	1	0
1	0	0
0	0	0

Дизъюнкция

А	В	А˅В
1	1	1
0	1	1
1	0	1
0	0	0

Эквивалентность двух высказываний. Эквивалентность двух высказываний— это сложное высказывание, истинное тогда, когда значения истинности составляющих высказываний одинаковы, и ложное — в противном случае; обозначается: А ≡В; читается: ≪А эквивалентно В≫.

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

Импликация двух высказываний. Импликация двух высказываний обозначается:

А ﬤ В; читается: ≪если А, то В≫. Это такое сложное высказывание, которое ложно только в том случае, когда А истинно, а В ложно.

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

Важнейшую роль в алгебре логики играют следующие равносильные соотношения, выражающие основные законы алгебры логики:

1) А = А означает, что не А истинно, если А ложно;

2) А ˄ В = В ˄ А означает, что (А и В = В и А);

3) (А ˄ В) ˄ С = А ˄ (В ˄ С) означает, что ((А и В) и С) =

= (А и (В и С)) или, иначе, это закон логического умножения ((А - В) -С) = (А • (В • С));

4)A v B = B v A означает, что А + В = В + А — известный из курса арифметики закон: ≪от перемены мест слагаемых сумма не меняется≫;

5) (A v В) v С = A v (В v С) или (А + В) + С = А + (В + С);

6) А ˄ (В v С) = (А ˄ В) v (А ˄ С) означает, что левая часть выражения истинна при истинности правой части;

7) A v (В ˄ С) = (A v В) ˄ (A v С);

8 (Ā˅ =

9) ( ˄ )=

10) А ˄А = А;

11) A v А = А;

12) А ˄ 1 = А;

13) A v 0 = А.

Проверка справедливости указанных соотношений может быть произведена на основании определений и таблиц логических операций — конъюнкции, дизъюнкции и отрицания. Соотношения 1 — 13 используются для преобразования сложных логических выражений к более простому виду. Соотношения 2—5 показывают, что для операций конъюнкции и дизъюнкции справедливы переместительный и сочетательный законы, в силу чего многочленные конъюнкции и дизъюнкции можно записывать без скобок. Например, вместо [(А ˄ В) ˄ С] ˄D можно записать А ˄В ˄ С ˄ D.

Выражения вида А ˄В ˄ С ˄ D... часто называются произведением, а его члены — множителями.

Выражения вида Av Вv С v... называют суммой, а его члены — слагаемыми.

Соотношение 6 показывает, что в алгебре логики справедлив закон распределительности конъюнкции относительно дизъюнкции.

Соотношение 7 показывает, что в алгебре логики имеет место еще закон распределительности дизъюнкции относительно конъюнкции

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

Соотношения 8 и 9 называются законами де Моргана и вместе с соотношением 1 позволяют преобразовывать логические выражения к виду, в котором знаки отрицания относятся только к простым высказываниям.

Законы Моргана – логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана.

Отрицание конъюнкции есть ни что иное как дизъюнкция отрицания.

Отрицание дизъюнкции есть не что иное как конъюнкция отрицания.

Помимо соотношений 1 — 13 весьма полезными для преобразования логических выражений являются следующие равносильные соотношения:

Диаграммы Венна

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

Конъюнкция двух высказываний будет представляться пересечением двух множеств (рис. 1.4, б). Действительно, А ˄ В = 1 только тогда, когда А = 1 и В = 1, а это имеет место лишь для точек, одновременно принадлежащих множеству А и множеству В (их пересечению).

Дизъюнкция двух высказываний A v В будет изображаться множеством, которое получается путем объединения множеств А и В (рис. 1.4, в).

Эквивалентность двух высказываний А ≡ В изобразится так, как показано на рис. 1.4, г, так как истинность А В равна 1 либо при А = 1 и В = 1, либо при А = 0 и В = 0.

Отрицание эквивалентности А ≡ В, показанное на рис. 1.4, д, получается, если учесть, что А ≡ В равно А≡ В.

Отрицание конъюнкции обозначается: А / В и называется операцией Шеффера (см. рис.1.4,е).

Отрицание дизъюнкции , выраженное штрихом Шеффера, имеет смысл Ā= А / В

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

Действия в реляционных БД базируются на операциях реляционной алгебры.

1. Ограничение (выборка) - создание новой таблицы путём отбора строк исходной таблицы, которые удовлетворяют условию ограничения.

2. Проекция - создание новой таблицы путём отбора определённых столбцов исходной таблицы.

3. Объединение - создание новой таблицы, содержащей все строки исходных таблиц, которые должны иметь одинаковые столбцы.

4. Пересечение -- создание новой таблицы, содержащей строки общие для исходных таблиц. При этом исходные таблицы должны иметь одинаковые столбцы

5. Разность -- создание новой таблицы, содержащей строки 1-ой таблицы, отсутствующие во 2-ой таблице. При этом и первая и вторая таблицы должны иметь одинаковые столбцы.

6. Произведение – создание новой таблицы, в которой имеются все столбцы 1-ой и 2-ой таблицы, а строки получены попарным сцеплением строк их таблиц. Число строк новой таблицы равно произведению количества строк исходных таблиц.

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

Пример. По двум таблицам найти произведение

ПОСТАВЩИК ПОТРЕБИТЕЛЬ

Поставщик

Поставщик 1

Поставщик 2

Потребитель

Потребитель 1

Потребитель 2

Результат операции произведения

Поставщик	Потребитель
Поставщик 1	Потребитель 1
Поставщик 1	Потребитель 1
Поставщик 2	Потребитель 2
Поставщик 2	Потребитель 2

7. Деление – создание новой таблицы, содержащей столбцы 1-ой таблицы, отсутствующие во 2-ой таблице, и строки 1-ой таблицы, которые совпали со строками 2-ой таблицы. Для выполнения этой операции вторая таблица должна содержать лишь столбцы, совпадающие со столбцами первой таблицы.

Пример. Требуется отобрать студентов группы, получающих стипендию.

Исходная таблица:(ФИО, Дата рождения, Шифр группы, Признак наличия стипендии)

Результат (таблица): (ФИО, Дата рождения)

Создадим вспомогательную таблицу со столбцами (Шифр группы, Признак наличия стипендии). Заполним одну строку этой таблицы, поместив в неё шифр заданной группы и отметку о получении стипендии.

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

8. Соединение – создание новой таблицы, строки которой являются сцеплением строк исходных таблиц.

Различают два вида соединения таблиц: естественное и по условию.

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

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

Пример. Соединить таблицы СТУДЕНТ и ОЦЕНКА.

Общий атрибут- Номер зачётной книжки.

СТУДЕНТ

ФИО	Дата рождения		Номер зачётной книжки
Иванов М.Т.	22.12.80		1234
Петров П.Л.	12.05.80		1235
Сидоров С.С.		30.09.80	1236

ОЦЕНКА

Код дисциплины	Номер зачётной книжки	Оценка
1	1234	4
1	1235	3
2	1234	4
2	1235	3

Результирующая таблица

ФИО	Дата рождения	Номер зачётной книжки	Код дисциплины	Номер зачётной книжки	Оценка
Иванов М.Т.	22.12.80	1234	1	1234	4
Иванов М.Т.	22.12.80	1234	2	1234	4
Петров П.Л.	12.05.80	1235	1	1235	3
Петров П.Л.	12.05.80	1235	2	1235	3
Сидоров С.С.	30.09.80	1236