Реляционная алгебра. Решение задач

1. Реляционнаяалгебра

Решение задач

2. Предметная область

• В модели должна храниться информация о студентах. О каждом
студенте известны:
• номер его студенческого билета, фамилия, инициалы, пол, дата
рождения и выплачиваемая ему стипендия.
• Все студенты распределены по группам. Как правило, один из
студентов в группе выбирается старостой, чтобы представлять
интересы группы в деканате. Иногда назначение старосты
затягивается, и мы должны знать дату его назначения.
• Может случиться, что студенты нескольких групп учатся
одинаковой специальности и тогда группы объединяются в
общий поток.
• В базе данных должно храниться название специальности,
которую получат студенты по окончании обучения

3. Предметная область

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

4. Предметная область

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

5. метод ER- диаграмм (сущностей-связей). Элементы «прямоугольник» представляют сущности предметной области, «овал» - атрибуты

сущностей, «ромб» - связи между сущностями.

6.

• Все типы связей в данной модели
бинарные и около каждой из них указана
кардинальная пропорция
• Одинарная линия, соединяющая
прямоугольник и ромб означает, что не
обязательно каждый экземпляр типа
объекта участвует в связи, а двойная
линия – обязательное участие
• в овалах указаны атрибуты типов
объектов и типов связей. многозначный (в
двойном овале) составной атрибут типа
связи "ОЦЕНЕН", что подчеркивает, что
любой студент по одной и той же
дисциплине может иметь несколько
оценок полученных в разные дни

7. 2. Реляционная модель

Сокращения
СТ – СТУДЕНТ
ГР – ГРУППА
ПТ – ПОТОК
КФ – КАФЕДРА
ДЦ – ДИСЦИПЛИНА
ВЫБ – ВЫБИРАЕТ
ИЗЧ – ИЗУЧАЕТ
ОТВ – ОТВЕЧАЕТ
ОЦН – ОЦЕНЕН.
Кст – код (шифр, номер
студенческого билета) студента
Фам – фамилия студента
Дрожд – дата рождения
Стип – стипендия
Ккур – код помогающего студента
Кстг – код старосты группы
Дстг – дата назначения старосты
Назв – название кафедры или
дисциплины
Труд – трудоемкость дисциплины
Цикл – цикл, к которому относится
дисциплина; один из трех:
ГСЭ – гуманитарный, ЕН –
естественно-научный, СД –
специальный
Спец – название направления
(специальности)
Nгр, Nпт, Nкф, Nдц – номера
соответственно группы, потока,
кафедры и дисциплины

8. Схема 2. Реляционная модель данных

СТ(Кст, Фам, Дрожд, Пол, Стип, Ккур, Nгр, Nкф, Тема, Дата, Оценка)
ГР(Nгр, Nпт, Кстг, Дстг)
ПТ(Nпт, Спец)
КФ(Nкф, Назв)
ДЦ(Nдц, Назв, Труд)
ИЗЧ(Nпт, Nдц)
ВЫБ(Кст, Nдц)
ОТВ(Nкф, Nдц)
ОЦН(Кст, Nдц, Дата, Оценка)
Жирным шрифтом в реляционной модели выделены первичные
ключи каждого отношения, а курсивом – внешние связи.
СТ.Ккур реализует тип связи "ПОМОГАЕТ", СТ.Nгр – "УЧИТСЯ В",
СТ.Nкф – "ВЫПУСКАЕТ", ГР.Nпт – "ВХОДИТ", Кстг – "ПРЕДСТАВЛЯЕТ".
В связях типа M:N (ИЗЧ, ОЦН, ОТВ, ВЫБ), реализованных
отдельными отношениями, жирным курсивом выделены
первичные ключи, относящихся к этим связям типов объектов.

9. 3 Решение задач в реляционной алгебре

• 3.1 Простые задачи
Требуется собрать в одном отношении
свойства (как правило) различных
объектов, причем, если и заданы какие
либо дополнительные условия, то они
относятся к значениям кортежей,
анализируемых независимо друг от друга.

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

• Задача 1. Выдать фамилии студентов, родившихся
до 1 сентября 1990 года.
• Задача 2. Выдать фамилии студентов, не
получающих стипендию.
• Задача 3. Сформировать список студентов – мужчин
старше 20 лет, получающих стипендию.
Если параметры отсутствуют, то получаем текущую дату (обозначим ее dt).
Кроме того, от любой даты можно вычислить день (day(дата)), месяц
(month(дата)) и год (year(дата)), а также добавить/вычесть указанное
количество дней
• Задача 4. Дать список групп, для которых староста в
текущем учебном году либо не назначен, либо
назначен позже 10 дней после начала учебы

11. Задача 1. Выдать фамилии студентов, родившихся до 1 сентября 1990 года

условием является факт, что дата рождения
меньше
указанной.
Следовательно,
решение может быть записано так.
• R1 Дрожд<"01.09.90" (СТ),
• REZ Фам (R1)
Отметим, что любую константу мы будем
писать в двойных кавычках. Напомним,
схема R1 совпадает со схемой СТ и,
следовательно,
взятие
проекции
правомочно. Этот же результат может быть
записан одной строкой, одним выражением
• REZ Фам ( Дрожд<"01.09.90" (СТ))

12. Задача 2. Выдать фамилии студентов, не получающих стипендию

условием является отсутствие стипендии, что
означает,
что
стипендия
студенту
не
назначалась, т.е. ее значение задано константой
nil. В остальном реше-ние очень похоже на
решение задачи 1.
• REZ Фам ( Стип=nil (СТ))

13. Задача 3. Сформировать список студентов – мужчин старше 20 лет, получающих стипендию

В третьей задаче четко не обозначено какие атрибуты
следует собрать в результирующем отношении.
• необходимо включить в результат не только фамилии
студента, но и атрибута, играющего роль ключевого (в нашем
случае Кст). Иначе различные студенты, обладающие
одинаковой фамилией, останутся в единственном
экземпляре.
• естественно включить в результат также Дрожд и Стип,
• атрибута Возраст в нашей модели не предусмотрено, но
всегда существует возможность получить любую дату
(функция date(день, месяц, год)).
REZ Кст,Фам,Дрожд,Стип ( Стип nil
Дрожд<date(day(dt), month(dt),year(dt)-20) (СТ))
.
and
Пол=“Муж”
and

14. Задача 4. Дать список групп, для которых староста в текущем учебном году либо не назначен, либо назначен позже 10 дней после

начала учебы
• REZ Nгр ( Дстг=nil or Дстг>date(10,9,year(dt)if(month(dt)>8,0,1)) (ГР)),

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

объекта, а
остальные из другого
• Задача 5. Дать номера групп с указанием фамилии
старосты.
• Задача 6. Привести перечень групп с указанием
названия специальности, по которой учатся
студенты этих групп.
• Задача 7. Дать перечень студентов, тем их
выпускных работ и название выпускающих кафедр.
При решении этих задач (также как и
последующих) важно выбрать именно тот
атрибут реализации связи, о котором говорится
в условии задачи.

16. Задача 5. Дать номера групп с указанием фамилии старосты.

• В задаче 5 фамилия старосты хранится в отношении СТ, а связь
ПРЕДСТАВЛЯЕТ реализована атрибутом Кстг в отношении ГР.
Поэтому необходимо соединить отношения СТ и ГР при
условии, что значение кода студента в отношении СТ совпадает
с кодом старосты в отношении ГР, что записывается следующим
образом
• R1 СТ ><СТ.Кст=ГР.Кстг ГР,
• REZ ГР.Nгр, СТ.Фам (R1)
• Напомним, что, если староста еще не назначен, то информации
об этой группе в результирующем отношении не будет. Если бы
мы хотели иметь информацию обо всех группах, не зависимо от
назначения старосты, то решение следовало бы записать через
правое внешнее соединение (запишем его одним выражением)
• REZ ГР.Nгр, СТ.Фам (СТ >< СТ.Кст=ГР.Кстг ГР)

17. Задача 6. Привести перечень групп с указанием названия специальности, по которой учатся студенты этих групп.

• Решение задачи 6 можно записать в
виде
• REZ ГР.Nгр, ПТ.Спец (ПТ X ГР),
• где естественное соединение проходит
по единственному совпадающему
атрибуту Nпт

18. Задача 7. Дать перечень студентов, тем их выпускных работ и название выпускающих кафедр

Решение задачи 7 можно записать в виде
REZ СТ.Фам, Ст.Тема, КФ.Назв (СТ X КФ),
где естественное соединение проходит
по единственному совпадающему
атрибуту Nкф.

19. Задачи, в которых типы объектов связаны между собой связью с кардинальной пропорцией M:N, реализуемой в реляционной модели

отдельным отношением.
• Задача 8. Привести названия дисциплин,
изучаемых по специальности "Химия".
• Задача 9. Дать список названий кафедр, и
названий дисциплин из цикла "ЕН", за
преподавание которых она отвечает.
• Задача 10. Дать список студентов,
получивших оценку 4 или 5 по дисциплине
"Матанализ".

20. Задача 8. Привести названия дисциплин, изучаемых по специальности "Химия вариант 1.

Задача 8. Привести названия дисциплин, изучаемых
по специальности "Химия вариант 1.
R1 ИЗЧ.Nдц, ПТ.Спец (ИЗЧ X ПТ),
R2 ДЦ.Назв, R1.Спец (R1 X ДЦ),
REZ R2.Назв ( R2.Спец="Химия" (R2))
Так как отношение ИЗЧ содержит первичны ключи как потока, так
и дисциплины, то естественное соединение в первой строке
пройдет по единственному совпадающему атрибуту (Nпт) и,
следовательно, R1 содержит перечень номеров дисциплин с
указанием специальностей, студентами которых они изучаются.
Аналогичная операция, но уже с заменой номеров дисциплин на
их названия получатся после выполнения второй строки.
И, наконец, третья строка оставит только названия дисциплин,
которые изучаются студентами специальности "Химия".
Напомним, что отношение это множество. В данном случае R1 –
множество пар: номер дисциплины, название специальности.
Однако без необходимости повторять это мы не будем.

21. Задача 8. Привести названия дисциплин, изучаемых по специальности "Химия вариант 2.

Задача 8. Привести названия дисциплин, изучаемых
по специальности "Химия вариант 2.
Напомним, что по временным затратам естественное соединение
близко к декартовому произведению, то есть, как правило,
достаточно большое. Более эффективной окажется следующая
логика решения задачи.
R1 Nпт ( Спец="Химия" (ПТ)),
сразу сокращаем мощность ПТ
R2 Nдц (R1 * ИЗЧ),
REZ Назв (R2 * ДЦ)
Здесь мы сначала получим отношение, содержащее номер
потока "Химия", затем номера дисциплин, изучаемых
студентами этого потока и, наконец, названия дисциплин, о
которых говорится в условии задачи.

22. Задача 9. Дать список названий кафедр, и названий дисциплин из цикла "ЕН", за преподавание которых она отвечает

Задача 9. Дать список названий кафедр, и
названий дисциплин из цикла "ЕН", за
преподавание которых она отвечает
R1 ДЦ.Nдц ( ДЦ.Цикл="ЕН" (ДЦ))
– номера дисциплин, относящихся к "ЕН",
R2 ОТВ.Nкф (R1 * ОТВ)
– номера кафедр, отвечающих за эти дисциплины,
REZ КФ.Назв (R2 * КФ)
– названия кафедр, соответствующие их номерам

23. Задача 10. Дать список студентов, получивших оценку 4 или 5 по дисциплине «Матанализ».

R1 ДЦ.Nдц ( ДЦ.Назв="Матанализ" (ДЦ))
– номера дисциплин с названием "Матанализ",
R2 ОЦН.Кст ( ОЦН.Оценка >= 4 (R1 XОЦН))
– коды студентов, получивших оценку 4 или 5 по этим
дисциплинам,
REZ СТ.Фам (R2 X CТ)
– фамилии этих студентов Так как может быть
несколько различных дисциплин с одинаковым
названием, но разными номерами, мы используем
множественное число

24.

• Для решения простых задач общего характера
требуется определить цепочку отношений, в
которых заложены требуемые характеристики и
упомянутые в условии задачи связи. Например, в
задаче 11 эту цепочку составляют отношения: ДЦ
(в нем есть название дисциплин), ИЗЧ (номера
потоков, изучающих эти дисциплины), ГР (номера
групп, входящих в потоки, так как связь ВХОДИТ
реализована атрибутом Nпт в отношении ГР), СТ
(фамилии студентов, учащихся в этих группах,
через связь УЧИТСЯ_В, реализованную атрибутом
Nгр в СТ)

25.

• Задача 11. Дать список студентов, изучающих
дисциплину "Информатика".
• Задача 12. Дать фамилии старост групп и
названия специальностей для потоков со
специальностью "Химия" или "Физика".
• Задача 13. Привести перечень названий
кафедр, названий дисциплин, за которые они
отвечают и фамилии студентов, получивших
двойки по этим дисциплинам за последнюю
неделю

26. Решение задачи 11 можно записать в виде

• R1 ДЦ. Nдц (ДЦ. Назв="Информатика"(ДЦ)) - номера дисциплин с
названием "Информатика", R2 ИЗЧ. Nпт (R1 * ИЗЧ) - номера
потоков, студенты которых изучают дисциплины,
номера которых собраны в отношении R1,R3 ГР. Nгр (R2 *
ГР) - номера групп, входящих в потоки, номера которых
собраны в отношении R2,REZ СТ. Фам (R3 * CТ) - фамилии
студентов, учащихся в группах, номера которых собраны
в отношении R3.
• Обратите внимание, что воспользоваться более
короткой связью ОЦЕНЕН между отношениями ДЦ и СТ
нельзя. Не все студенты, изучающие дисциплину, уже
сдавали по ней экзамен и получили оценку, в
результате чего может быть потеряна часть информации

27. Решение задачи 12 можно записать в виде

• R1 ПТ. Nпт, ПТ. Назв (Назв="Физика" orНазв="Химия" (ПТ)) номера потоков с названиями "Физика" или
"Химия", R2 (Кст, Назв) ГР. Кстг, R1. Назв (R1 * ГР) коды старост групп и названия
специальностей, которым обучаются студенты
групп, относящихся к потокам, номера которых
собраны в отношении R1; мы воспользовались
переименованием атрибутов в R2, чтобы в
следующем операторе применить
естественное соединение. REZ СТ. Фам, R2. Назв (R2
* CТ) - фамилии старост групп и названия
специальностей

28. Решение задачи 13 может быть записано в виде

• R1 ОЦН. Кст, ОЦН. Nдц (Оценка=2and Дата>date () - 7 (ОЦН)) - коды студентов и
номера дисциплин, по которым этими студентами были
получены двойки за последнюю неделю,
R2 R1. Кст,ДЦ. Nдц, ДЦ. Назв (R1 * ДЦ) - к кодам студентов и номерам
дисциплин из R1 добавлены названия этих дисциплин.
• R3 (Кст, Назв_д, Назв_к) R1. Кст, ДЦ. Назв, КФ. Назв (R2 * КФ) - к кодам
студентов и названиям дисциплин из R2 добавлены названия
кафедр, отвечающих за эти дисциплины. Естественное
соединение прошло по атрибуту Кдц. Переименование
атрибутов выполнено, чтобы не было в отношении R3 двух
атрибутов с одинаковым названием.
• REZ СТ. Фам, R3. Назв_д, R3. Назв_к (R3 * CТ) - фамилии студентов,
названия дисциплин и отвечающих за них кафедр, по которым
за последнюю неделю получены двойки.

29.

• Следующий тип задач - задачи на сравнение двух
множеств. Как правило, в формулировке таких задач
присутствуют слова "все", "только", "все и только". Текст
задач этого типа построен таким образом, что в нем
записана необходимость выделения двух отношений
(множеств) с одинаковой структурой (схемой), причем
одно из этих отношений должно быть подмножеством
другого (АВ). При реализации на компьютере условие,
чтовсе элементы одного отношения (А) являются
элементами другого (В), легче всего реализуется
попыткой создания разности двух отношений (А-В) (из
меньшего вычитается большее), после чего полученное
отношение анализируется на пустоту.

30. При решении задач на сравнение двух отношений, таким образом, требуется:

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

31.

• Задача 14. Дать фамилии студентов,
выбравших все дисциплины типового
учебного плана.
• Задача 15. Дать фамилии старост групп
обучающихся только по типовым учебным
планам.
• Задача 16. Названия специальностей, все
студенты которых учатся по типовым
учебным планам

32.

• Начнем с задачи 14. Какие два отношения скрыты в этой
формулировке? На самом деле для каждого студента мы
должны сравнить множество дисциплин типового учебного
плана для выбранной им специальности и множество
дисциплин, которые он фактически выбрал. Если множество
дисциплин, которые он фактически выбрал, включает
соответствующее множество дисциплин типового учебного
плана, то это и означает, что он изучает все дисциплины
типового учебного плана. Однако в реляционной алгебре мы не
можем организовать цикл по всем студентам с целью проверки
того, как соотносятся эти два множества для каждого из них.
Поэтому реально мы должны рассматривать два множества
пар, элементами которых являются пары значений атрибутов код студента и номер дисциплины