Примеры применения реляционной алгебры

ПРИМЕР 1. Возьмем набор отношений, которые моделируют сдачу сессии студентами неко­торого учебного заведения. Тема весьма понятная и привычная.

R₁ (ФИО, Дисциплина, Оценка) - информация о попытках (как успешных, так и неуспешных) сдачи экзаменов студентами;

R₂(ФИО, Группа) - состав групп;

R₃ (Группа, Дисциплина) -список дисциплин, которые надо сдавать каждой группе

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

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

1. Список студентов (только ФИО), которые сдали экзамен по БД на «отлично». Результат может быть получен применением операции выборки по сложному условию к отношению R₁ и последующим проектированием на атрибут «ФИО» (нам ведь требуется только список фамилий).

S = П_ФИО(s_{Оценка=5 Λ Дисциплина= БД} (R₁))

2. Список тех, кто должен был сдавать экзамен по БД, но пока еще не сдавал. Сначала найдем всех, кто должен был сдавать экзамен по БД. В отношении R₃ находится список всех дисциплин, по которым каждая группа должна была сдавать экзамены, ограничим перечень дисциплин только «БД», используя операцию выборки

R₄ = s_{Дисциплина= БД} (R₃)

Для получения всех ФИО из тех групп, которые должны сдавать БД, необходимо соединить R₂ с R₄, а потом спроектировать на ФИО. Используем операции естественного соединения и проекции:

R₅= П_ФИО(R₂ R₄)

Создадим список тех, кто сдавал БД согласно отношению R₁ (нас пока не интересует результат сдачи, а интересует сам факт попытки сдачи, то есть при­сутствие в отношении R₁):

R₇=П_ФИО(s_{Дисциплина= БД} (R₁))

Окончательный результат (список еще не сдававших БД) получается путем вычитания R₇ из отношения R₅ (все кто есть в R₅, но нет в R₇):

S = R₅ – R₇

Примечание: Для получения R₅ (минуя получение R₄ ) мож но было сразу написать операцию тета-соединения

R₅= П_ФИО (R_{2 R3.НомерГруппы = R2.НомерГруппы Λ R3.Дисциплина = «БД»} R₃)

3. Список несчастных, имеющих несколько двоек (только ФИО):

Этот пример весьма интересен: для поиска строк, удовлетворяющих в совокупности условию больше одного, применяется операция тета-соединения отношения с самим собой. Поэтому мы как бы взяли копию отношения R₁ и назвали ее R'₁. Напомним, что тета-соединение – это подмножество декартового произведения, удовлетворяющее определенному предикату (условию). А декартово произведение получается путем конкатенации (сцепления) кортежей.

S = П_ФИО(R_{1 R1.ФИО= R'1.ФИО Λ R1.Дисциплина≠ R'1.Дисциплина Λ R1.Оценка=2 Λ R'1.Оценка=2} R'₁)

Обратите внимание на эту операцию – она применяется очень часто, когда надо найти список или перечень объектов, удовлетворяющих условию «больше одного».

4. Список круглых отличников.

Строим список всех пар <студент—дисциплина>, которые в принципе должны быть сданы:

R₄ =П_{ФИО, Дисциплина} (R_{2 R2.Группа = R3.Группа} R₃))

Строим список пар <студент— дисциплина>, где получена оценка «отлично»:

R₅ = П_{ФИО,Дисциплина} ((s_{Оценка=5} (R₁ ))

Строим список студентов, что-либо не сдавших на «отлично»:

R₆ = П_ФИО (R₄ - R₅)

Наконец, исключив последнее отношение из общего списка студентов, получаем результат:

П_ФИО (R₂) - R₆

Обратите внимание, что для получения множества студентов, что-либо не сдав­ших на «отлично» (R₆), мы осуществили «инверсию» множества всех отлично сданных пар <студент—дисциплина> (R₅) путем вычитания его из предвари­тельно построенного универсального множества (R₄). Рекомендуем очень внимательно разобрать этот пример и вникнуть в смысл каждого действия — это очень пригодится для понимания реляционной алгебры. ЗАМЕЧАНИЕ: Вместо двух операций R5 и R6 здесь можно было сразу найти список студентов, что-либо не сдавших на отлично, если поставить в выборке условие Оценка≠5.

5. Общий список студентов, которые сдали все экзамены (для данной сессии)

Особенность ситуации такая, что есть группы как с одинаковыми, так и с разными экзаменами, что отражается в отношении R₃. Для определенности положим, что у нас 3 группы с номерами 406, 407 и 507. Будем «погруппно» искать студентов, сдавших все экзамены, а потом объединим эти списки.

· Составим список пар «студент-дисциплина», у которых оценка больше

двойки:

R₄ = П_{ФИО,Дисциплина} ((s_{Оценка>2} (R₁ ))

Здесь указаны студенты всех групп, сдавшие хотя бы один экзамен.

· Для каждой группы определим список дисциплин, по которым сдаются экзамены

R₄₀₆ = П_{Дисциплина} ((s_{Группа=406} (R₃ ))

R₄₀₇ = П_{Дисциплина} ((s_{Группа=407} (R₃ ))

R₅₀₇ = П_{Дисциплина} ((s_{Группа=507} (R₃ ))

Если у групп 406 и 407 экзамены совпадают, то R₄₀₆ = R₄₀₇.

· Найдем списки студентов каждой группы, которые сдали все экзамены. Поскольку мы отвечаем на вопрос «все», то здесь нужно применить операцию деления. При этом студенты тех групп, в которых экзамены совпадают, попадут в одно отношение.

Если у групп 406 и 407 одинаковые экзамены, то R₅ = R₆

R₅ = R₄ ÷ R₄₀₆

R₆ = R₄ ÷ R₄₀₇

R₇ = R₄ ÷ R₅₀₇

· Объединим эти отношения для получения общего списка студентов, сдавших все экзамены. Учтем, что при операции объединения кортежи-дубликаты исключаются.

R₈ = R₅ R₆ R₇

Получили список студентов всех групп (406, 407, 507), которые сдали все экзамены.

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

6. Список студентов, которые сдали только один экзамен.

Другими словами, надо найти список студентов, которые получили только по одной дисциплине оценку выше 2.

· Найдем список студентов и дисциплин, по которым эти студенты имеют оценку выше двойки, т.е. сдали хотя бы один экзамен

R₄ = П_{ФИО,Дисциплина} ((s_{Оценка>2} (R₁ ))

· Найдем студентов, которые сдали более одного экзамена, т.е. сдали экзамены по двум и более дисциплинам. Для этого используем тета-соединение отношения R₄ с его копией R'₄.

R₅ = (R_{4 R4.ФИО=R'4.ФИО Λ R4.Дисциплина≠ R'4.Дисциплина} R'₄)

· Список студентов, сдавших только один экзамен, получается как разность между R₄ и R₅ с последующей проекцией на ФИО

S= П_ФИО (R₄ - R₅)

Итак, здесь был ход решения «от противного» с использованием тета-соединения отношения R4 с самим собой.

ПРИМЕР 2. Для демонстрации возможностей операций объединения, пересечения и разности рассмотрим один пример. Рассмотрим ситуацию поступления в высшие учебные заведения, которая была характерна для периода, когда были разрешены так называемые репетиционные вступительные экзамены, которые сдавались раньше основных вступительных экзаменов в вуз. Исходными являются три отношения R₁, R₂ и R₃. Все они имеют эквивалентные схемы (совместимы по объединению).

R₁= (ФИО, Паспорт, Школа) -список абитуриентов, сдававших репетиционные экзамены.

R₂= (ФИО, Паспорт, Школа) -список абитуриентов, сдававших экзамены на общих условиях.

R₃= (ФИО, Паспорт, Школа) -список абитуриентов, принятых в институт.

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

Ответим на следующие вопросы:

1. Список абитуриентов, которые поступали два раза и не поступили в вуз

R = R₁ R₂ – R₃

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

2. Список абитуриентов, которые поступили в вуз с первого раза, то есть они сдавали экзамены только один раз и сдали их так хорошо, что сразу были зачислены в ВУЗ.

R = (R₁ - R₂ R₃) (R₂ - R₁ R₃)

3. Список абитуриентов, которые поступили в вуз только со второго раза.

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

R = R₁ R₂ R₃

4. Список абитуриентов, которые поступали только один раз и не поступили.

Это прежде всего те абитуриенты, которые присутствуют в R₁ и не присутствуют в R₂, и те, кто присутствуют в R₂ и не присутствуют в R₁. И разумеется, никто из них не присутствует в R₃.

R = (R₁ - R₂) (R₂ - R₁) - R₃

В отсутствие скобок порядок выполнения операций реляционной алгебры естественный, поэтому сначала будут выполнены операции в скобках, а затем будет выполнена последняя операция вычитания отношения R₃.

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

Пример 3 (нет в билетах, можно использовать для примеров)

Даны отношения, моделирующие работу фирмы, занимающейся разработкой программных систем. Каждый сотрудник административно закреплен только за одним отделом. Файлы хранятся на разных серверах. На разных серверах файлы могут иметь одинаковые имена. Создатель файла является его владель­цем, поэтому у каждого файла только один владелец, но владелец файла может разрешить пользоваться файлом другим сотрудникам. Существует множество системного программного обеспечения, каждая программа может работать с од­ним или с несколькими файлами, расположенными на одном или нескольких серверах:

Дата добавления: 2015-07-08