Теоретико-множественные операции реляционной алгебры
Напомним, что
алгеброй- называется множество объектов с заданной на нем совокупностью операции, замкнутых относительно этого множества, называемого основным множеством.
Основное множество в реляционной алгебре- это всё возможное множество отношений.
Всего Э. Ф. Коддом было предложено 8 операций для реляционной алгебры. В общем это множество избыточное, так как одни операции могут быть представлены через другие, однако множество операций выбрано из соображений максимального удобства при реализации произвольных запросов к БД. Все множество операций можно разделить на две группы: теоретико-множественные операции и специальные операции. В первую группу входят 4 операции. Три первые теоретико-множественные операции являются бинарными, то есть в них участвуют два отношения и они требуют эквивалентных схем исходных отношений.
Объединение двух отношений- это отношение, содержащее множество кортежей, принадлежащих либо первому, либо второму исходным отношениям, либо обоим отношениям одновременно.
Пусть заданы два отношения R1 = { r1 } , R2 = { r2 }. где r1 и r2 — соответственно кортежи отношений R1 и R2, то объединение
R1R2 = { г | г R1r R2 }. Здесь r — кортеж нового отношения, — операция логического сложения «ИЛИ».
Пример применения операции объединения приведен на рис. 4.1. Исходными отношениями являются отношения R1 и R2, которые содержат перечни деталей. изготавливаемых соответственно на первом и втором участках цеха. Отношение R3 содержит общин перечень деталей, изготавливаемых в цеху, то есть характеризует общую номенклатуру цеха.
| R1 | |
| Шифр детали | Название детали |
| Гаика Ml | |
| Гайка М2 | |
| Гаика M3 | |
| Болт Ml | |
| Болт МЗ | |
| Шайба Ml | |
| Шайба МЗ |
| R2 | |
| Шифр детали | Название детали |
| Гайка М1 | |
| Гайка М3 | |
| Гайка М4 | |
| Гайка М2 | |
| Гайка М3 |
| R3 | |
| Шифр детали | Название детали |
| Гайка Ml | |
| Гайка М2 | |
| Гайка МЗ | |
| Болт Ml | |
| Болт МЗ | |
| Шайба Ml | |
| Шайба МЗ | |
| Гайка М4 | |
| Болт М2 |
Пересечение отношений в реляционной алгебре- это отношение, которое содержит множество кортежей, принадлежащих одновременно и первому и второму отношениям. R1 и R2:
R3 = R1 
R2={ г | r R1 ^ г R2 }, здесь ^ - операция логического умножения (логическое «И»).
В отношении R4 содержатся перечень деталей, которые выпускаются одновременно на двух участках цеха.
| R4 | |
| Шифр детали | Название детали |
| Гайка Ml | |
| Гайка МЗ | |
| Болт МЗ |
Разность отношений в реляционной алгебре- это отношение R1 и R2, содержащее множество кортежей, принадлежащих R1 и не принадлежащих R2:
R5 = RI \ R2 = { r | r R1 ^ r R2 }
Отношение R5 содержит перечень деталей, изготавливаемых только на участке 1, отношение RG содержит перечень деталей, изготавливаемых только на участке 2.
R6 = R2 \ R1 = { r | r R2 ^ rR1 }
| R5 | |
| Шифр детали | Название детали |
| Гайка М2 | |
| Болт Ml | |
| Шайба Ml | |
| Шайба МЗ |
| R6 | |
| Шифр детали | Название детали |
| Гайка М4 | |
| Болт М2 |
Следует отметить, что первые две операции, объединение и пересечение, являются коммутативными операциями, то есть результат операции не зависит от порядка аргументов в операции. Операция же разности является принципиально несимметричной операцией, то есть результат операции будет различным для разного порядка аргументов, что и видно из сравнения отношений R5 и R6.
В отличие от навигационных средств манипулирования данными в теоретико-графовых моделях операции реляционной алгебры позволяют получить сразу иной качественный результат, который является семантически гораздо более ценным и понятным пользователям. Например, сравнение результатов объединения и разности номенклатуры двух участков позволит оценить специфику производства: насколько оно уникально на каждом участке, и, в зависимости от необходимости, принять соответствующее решение по изменению номенклатуры.
Для демонстрации возможностей трех первых операций реляционной алгебры рассмотрим еще один пример — уже из другой предметной области. Исходными являются три отношения R1 R2 и R3. Все они имеют эквивалентные схемы.
- R1= (ФИО, Паспорт, Школа);
- R2= (ФИО, Паспорт, Школа);
- R3= (ФИО, Паспорт, Школа).
Рассмотрим ситуацию поступления в высшие учебные заведения, которая была характерна для периода, когда были разрешены так называемые репетиционные вступительные экзамены, которые сдавались раньше основных вступительных экзаменов в вуз. Отношение R1 содержит список абитуриентов, сдававших репетиционные экзамены. Отношение, R2 содержит список абитуриентов, сдававших экзамены на общих условиях. И наконец, отношение R3 содержит список абитуриентов, принятых в институт. Будем считать, что при неудачной сдаче репетиционных экзаменов абитуриент мог делать вторую попытку и сдавать экзамены в общем потоке, поэтому некоторые абитуриенты могут присутствовать как в первом, так и во втором отношении.
Ответим на следующие вопросы:
- Список абитуриентов, которые поступали два раза и не поступили в вуз. R = R1 R2 \ R3
- Список абитуриентов, которые поступили в вуз с первого раза, то есть они сдавали экзамены только один раз и сдали их так хорошо, что сразу были зачислены в вуз. R = (R1 \ R2 R3 )(R2 \ R1 R3)
- Список абитуриентов, которые поступили в вуз только со второго раза.
Прежде всего это те абитуриенты, которые присутствуют в отношениях R1 и R2, потому что они поступали два раза, и присутствуют в отношении R3, потому что они поступили. R = R1 R2 R3
- Список абитуриентов, которые поступали только один раз и не поступили.
Это прежде всего те абитуриенты; которые присутствуют в R1и не присутствуют в R2, и те, кто присутствуют в R2 и не присутствуют в R1. И разумеется, никто из них не присутствует в R3. R = (R1 \ R2) (R2 \ R1) \ R3
В отсутствие скобок порядок выполнения операций реляционной алгебры естественный, поэтому сначала будут выполнены операции в скобках, а затем будет выполнена последняя операция вычитания отношения R3.
Операции объединения, пересечения и разности применимы только к отношениям с эквивалентными схемами.
Кроме перечисленных трех теоретико-множественных операций в рамках реляционной алгебры определена еще одна теоретико-множественная операция — расширенное декартово произведение. Эта операция не накладывает никаких дополнительных условий на схемы исходных отношений, поэтому операция расширенного декартова произведения, обозначаемая R1 ® R2, допустима для любых двух отношений. Но прежде чем определить саму операцию, введем дополнительно понятие конкатенации, или сцепления, кортежей.
Сцеплением, пли конкатенацией, кортежей с = <c1, с2, ..., сn> и q = <q1, q2, ..., qm> называется кортеж, полученный добавлением значений второго в конец первого. Сцепление кортежей с и q обозначается как (с , q).
(с, q) = <с1 с2, ... , сn, q1, q2, .... qm>
Здесь n — число элементов в первом кортеже с, m — число элементов во втором кортеже q.
Все предыдущие операции не меняли степени или арности отношений — это следует из определения эквивалентности схем отношений. Операция декартова произведения меняет степень результирующего отношения.
Расширенным декартовым произведением отношения R, степени n со схемой
SR1=(А1,А2...,Аn) и отношения R2 степени m со схемой
SR2=(В1,В2, ... , Вm) называется отношение R3 степени n+m со схемой
SR3 = (А1, А2, ... , Аn, В1, В2, ..., Вm),
содержащее кортежи, полученные сцеплением каждого кортежа г отношения R] с каждым кортежем q отношения R2.
То есть если R1 = { r }, R2 = { q }
R1R2 = {(r, q) | r R1 ^ q R2}
Операцию декартова произведения с учетом возможности перестановки атрибутов в отношении можно считать симметричной. Очень часто операция расширенного декартова произведения используется для получения некоторого универсума — т. е. отношения, которое характеризует все возможные комбинации между элементами отдельных множеств. Однако самостоятельного значения результат выполнения операции обычно не имеет, он участвует в дальнейшей обработке. Например, на производстве в отношении 07 задана обязательная номенклатура деталей для всех цехов, а в отношении 08 дан перечень всех цехов.
| R7 | |
| Шифр детали | Название детали |
| Гайка M1 | |
| Гайка М2 | |
| Гайка МЗ | |
| Болт М1 | |
| Болт МЗ | |
| Шайба Ml | |
| Шайба МЗ | |
| Гайка М4 | |
| 000ll004 | Болт М2 |
| Болт М5 | |
| Болт М6 | |
| Шайба М2 |
| R8 |
| Цех |
| Цех 1 |
| Цех 2 |
| Цех 3 |
Тогда отношение R9, которое соответствует ситуации, когда каждый цех изготавливает все требуемые детали, будет выглядеть следующим образом:
| R9 | ||
| Шифр детали | Название детали | Цех |
| Гайка Ml | Цех 1 | |
| Гайка М2 | Цех 1 | |
| Гайка МЗ | Цех 1 | |
| Болт Ml | Цех 1 | |
| Болт МЗ | Цех 1 | |
| Шайба Ml | Цех 1 | |
| Шайба МЗ | Цех 1 | |
| Гайка М4 | Цех 1 | |
| Болт М2 | Цех 1 | |
| Болт М5 | Цех 1 | |
| Болт Мб | Цех 1 | |
| Шайба М2 | Цех 1 | |
| Гайка Ml | Цех 2 | |
| Ганка М2 | Цех 2 |
| R10 | ||
| Шифр | Название детали | Цех |
| Гайка Ml | Цех 1 | |
| (МО И 075 000 11 076 | Гайка М2 Гайка МЗ | Цех 1 Цех 1 |
| 000 11 003 | ! Болт Ml | Цех 1 |
| 0011 0006 | Болт МЗ | Цех 1 |
| Шайба Ml | Цех 1 | |
| 000 11060 | Шайба МЗ | Цех 1 |
| 000 11 004 | Болт М2 | Цех 1 |
| Гайка М4 | Цех 1 | |
| Болт МЗ | Цех2 | |
| Шайба Ml | Цех 2 | |
| Шайба МЗ | Цех 2 | |
| Гайка М4 | Цех 2 | |
| 0001 0778 | Болт М2 | Цех 2 |
| Гайка МЗ | Цех 2 | |
| 00011U03 | Болт Ml | Цех 2 |
| Болт МЗ | Цех 2 | |
| Шайба Ml | Цех 2 | |
| Шайба МЗ | Цех 2 | |
| Гайка М4 | Цех 2 | |
| Болт М'2 | Цех 2 | |
| Болт М5 | Цех 2 | |
| Болт Мб | Цех 2 | |
| Шайба М2 | Цех 2 | |
| Гайка Ml | ЦсхЗ | |
| Гайка М2 | ЦехЗ | |
| Гайка МЗ | Цех 3 | |
| Болт Ml | ЦехЗ | |
| Болт МЗ | ЦехЗ | |
| Шайба Ml | Цех 3 | |
| Шайба МЗ | ЦехЗ | |
| Гайка М4 | ЦехЗ | |
| Болт М2 | Цех 3 | |
| Болт М5 | ЦехЗ | |
| Болт Мб | ЦехЗ | |
| Шайба М2 | ЦехЗ |
| Болт Мб | Цех 2 | |
| Шайба М2 | Цех 2 | |
| Гайка Ml | ЦeхЗ | |
| Гайка М2 | ЦехЗ | |
| Гайка МЗ | ЦехЗ | |
| Болт Ml | ЦехЗ | |
| Болт МЗ | Цех 3 | |
| Шайба Ml | Цех 3 | |
| Шайба МЗ | ЦехЗ | |
| Гайка М4 | Цeх3 | |
| Болт М5 | Цех3 | |
| Болт Мб | Цех3 | |
| Болт М5 | Цех 1 | |
| Болт Мб | Цех 1 | |
| Шайба М2 | Цех1 |
В каких запросах нужно использовать расширенное декартово произведение? Эта операция моделирует некоторую ситуацию, которая характеризуется словом «все». Поэтому если нам надо узнать, какие детали в каких цехах из общей обязательной номенклатуры не выпускаются, то мы можем вычесть из полученного отношения R9 отношение R10, характеризующее реальный выпуск деталей в каждом цехе.
Отношение R11, которое является результатом выполнения этой операции, имеет вид:
R11= R9 \ R10
| R11 | ||
| Шифр детали | Название детали | Цех |
| Гайка Ml | Цех 2 | |
| Гайка М2 | Цех 2 | |
| Гайка МЗ | Цех 2 | |
| Болт М2 | ЦехЗ | |
| Шайба М2 | ЦехЗ | |
| Болт Ml | Цех 2 | |
| Болт М5 | ЦехЗ |
Группа теоретико-множественных операций избыточна, так, например, операцию можно заменить сочетанием операций объединения и пересечения.
(R1R2) \ (R1 \ R2) \ (R2 \ R1)
Однако это достаточно сложная формула, и именно поэтому все три теоретико-множественные операции вошли в базовый набор операций реляционной алгебры.
Далее мы переходим к группе операций, названных специальными операциями реляционной алгебры.