Задачи на сравнение множеств объектов

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

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

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

Задача 14. Дать фамилии студентов, выбравших все дисциплины типового учебного плана.

Задача 15. Дать фамилии старост групп обучающихся только по типовым учебным планам.

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

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

• · отношение R1 (Кст, Nдц) — множество всех студентов с указанием для каждого из них номеров дисциплин, которые он должен был бы изучить по типовому учебному плану,
• · отношение R2 (Кст, Nдц) — множество всех студентов с указанием для каждого из них номеров дисциплин, которые он выбрал для изучения.

Еще раз обратим внимание студента, что схемы отношений одинаковы, но получены они должны быть с использованием различных связей между типами объектов СТУДЕНТ и ДИСЦИПЛИНА. В первом случае это длинная цепочка: СТУДЕНТ, УЧИТСЯ_В, ГРУППА, ВХОДИТ, ПОТОК, ИЗУЧАЕТ, ДИСЦИПЛИНА, а во втором — СТУДЕНТ, ВЫБИРАЕТ, ДИСЦИПЛИНА. Подзадача получения отношения R1 относится к типу простых задач, а подзадача получения R2 вообще не требует усилий, так как R2 совпадает с отношением ВЫБ.

Что же мы получим, вычислив разность R3=R1-R2? Обратите внимание, что если студент выбрал все дисциплины типового учебного плана, то в R3 информации об этом студенте не останется (не будет ни одного кортежа содержащего код этого студента). Таким образом, в R3 останутся только коды тех студентов, которые не изучают все дисциплины типового учебного плана. Следовательно, если из всех студентов убрать тех, которые попали в отношение R3, то мы получим решение задачи 14.

Запишем теперь эти рассуждения в виде выражений реляционной алгебры.

R11 _{СТ. Кст, ГР. Nпт} (СТ * ГР)) — коды студентов с указанием номера потока, к которому они относятся; естественное соединение по единственному совпадающему атрибуту Nгр.

R1 _{R1. Кст, ИЗЧ. Nдц (}R11 * ИЗЧ) — коды студентов с указанием номеров дисциплин, которые они должны бы изучать по типовому учебному плану; естественное соединение по единственному совпадающему атрибуту Nпт.

R2 ВЫБ — это действие записано только для совпадения обозначений с используемыми при описании решения задачи.

R3 R1 — R2 — коды студентов с указанием номеров дисциплин из типового учебного плана, которые они не выбрали для изучения.

R4 _{R3. Кст (}R3) — коды студентов, которые не соответствуют условию задачи.

R5 _{СТ. Кст (}СТ) — R4 — коды студентов, которые соответствуют условию задачи.

REZ _{СТ. Фам} (R5 * CТ) — фамилии студентов, изучающих все дисциплины типового учебного плана.

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

R1 (Кст, Nдц) _{ГР. Кстг, ИЗЧ. Nдц (ГР. Кстг Nil (}ГР) * ИЗЧ) — коды старост групп с указанием номеров дисциплин, которые они должны бы изучать по типовому учебному плану; естественное соединение по единственному совпадающему атрибуту Nпт.

R2 ВЫБ — R1 — коды студентов с указанием выбранных номеров дисциплин, причем для старост групп выбранных не из типового учебного плана.

R3 _{R1. Кст (}R1) — _{R2. Кст (}R2) — коды старост групп, соответствующих условию задачи.

REZ _{СТ. Фам} (R3 * CТ) — фамилии студентов, изучающих все дисциплины типового учебного плана.

На что следует обратить внимание при анализе решения этой задачи? Отношение R1 содержит коды всех назначенных старост групп. Отношение R2 обо всех студентах, а не только о старостах групп. Нас это не волнует, так как при вычитании в следующей строке алгоритма это отношение является вычитаемым, а, значит, вся лишняя информация будет проигнорирована. При получении отношения R3 мы предварительно избавляемся от Nдц; они свою роль сыграли на предыдущем шаге. Последний шаг — стандартный прием перехода от ключевых атрибутов (Кст) к функционально от них зависящим, требуемым по условию задачи (Фам). Также отметим, что в задаче 14 речь шла о всех дисциплинах типового учебного плана и отношение ВЫБ было вычитаемым, а в задаче 15 говорилось о старостах, изучающих только дисциплины типового учебного плана, и ВЫБ стало уменьшаемым.

Перейдем к задаче 16. Напомним, что некоторые студенты могли либо заменить часть дисциплин типового учебного плана, либо дополнить его несколькими другими. Эта задача является вариацией задачи 14. Если мы определим коды студентов с указанием номеров потоков, к которым они относятся, и дисциплин, не относящихся к типовому учебному плану, то, следовательно, мы знаем номера потоков, в которых не все студенты учатся по типовым учебным планам. Небольшая трудность состоит в том, что отношение ВЫБ не содержит атрибут Nпт и, следовательно, при вычитании уменьшаемое тоже не должно содержать Nпт. Таким образом, мы вынуждены сначала получить коды студентов, которые учатся не только по типовым учебным планам, а по этим кодам получить номера потоков, не удовлетворяющих условиям задачи и затем перейти стандартным образом к названию специальности.

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

R11 _{СТ. Кст, ГР. Nпт} (СТ * ГР)) — коды студентов с указанием номера потока, к которому они относятся; естественное соединение по единственному совпадающему атрибуту Nгр.

R1 _{R1. Кст, ИЗЧ. Nдц (}R11 * ИЗЧ) — коды студентов с указанием номеров дисциплин, которые они должны бы изучать по типовому учебному плану; естественное соединение по единственному совпадающему атрибуту Nпт.

R3 R1 — ВЫБ — коды студентов с указанием номеров дисциплин из типового учебного плана, которые они не выбрали для изучения.

R4 _{R11. Nпт} (_{R3. Кст (}R3) * R11) — номера потоков, не все студенты которых соответствуют условию задачи.

REZ _{ПТ. Спец} ((_{ПТ. Nпт (}ПТ) — R4) * ПТ) — названия специальностей, все студенты которых учатся по типовым учебным планам (условие задачи).

Следующая задача несколько отличается от предыдущих.

Задача 17. Номера групп, все студенты которых изучают одни и те же дисциплины.

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

Учитывая это объяснение, решение задачи 17 можем записать в виде.

R1 _{СТ. Кст, СТ. Nгр, ВЫБ. Nдц} (СТ * ВЫБ) — для каждого студента указан номер группы, в которой он учится и номер дисциплины, которую он выбрал для изучения; естественное соединение по единственному совпадающему атрибуту Кст. Таким образом, мы получили множество троек — Кст, Nгр, Nдц по фактически изучаемым дисциплинам.

R2 _{R1. Nгр, R1. Nдц, (}R1) — избавившись от кода студента, мы получили множество пар — Nгр, Nдц, которое говорит в какой группе хотя бы кем-то изучается та или иная дисциплина. Другими словами, для каждой группы имеем свой максимальный перечень дисциплин, выбранный для изучения студентами группы.

R3 _{СТ. Кст, СТ. Nгр, R2. Nдц} (СТ * R2) — это множество троек построено так, что перечень дисциплин, изучаемых хотя бы кем-то из группы, приписан каждому студенту этой группы; естественное соединение по единственному совпадающему атрибуту Nгр.

R3 R1 — ВЫБ — коды студентов с указанием номеров дисциплин из типового учебного плана, которые они не выбрали для изучения.

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

REZ ГР — _{R4. Nгр} (R4) — те группы, в которых все студенты изучают одни и те же дисциплины (условие задачи).