к алгоритмизации   алгоритмы, струкутуры данных и программирование   СУБД   ЯиМП   3GL   4GL   5GL   технологии прогр.

Специальные операции реляционной алгебры

Первой специальной операцией реляционной алгебры является горизонтальный выбор, или операция фильтрации, или операция ограничения отношений. Для определения этой операции нам необходимо ввести дополнительные обозначения.

Пусть а — Булево выражение, составленное из термов сравнения с помощью связок И (^), ИЛИ (), НЕ (-) и, возможно, скобок. В качестве термов сравнения допускаются:

а) терм А ос а, где А — имя некоторого атрибута, принимающего значения из домена D; а — константа, взятая из того же домена D, a D; ос — одна из допустимых для данного домена D операций сравнения;

б) терм А ос В, где А, В — имена некоторых Q-сравнимых атрибутов, то есть атрибутов, принимающих значения из одного и то же домена D.

Тогда результатом операции выбора, или фильтрации, заданной на отношении R в виде Булева выражения, определенного на атрибутах отношения R, называется отношение R[G], включающее те кортежи из исходного отношения, для которых истинно условие выбора или фильтрации:

R[G(r)] = {r | r R ^ G(r) = "Истина"}

Операция фильтрации является одной из основных при работе с реляционной моделью данных. Условие а может быть сколь угодно сложным.

Например, выбрать из R10 детали с шифром «0011003». R12 =R10[ Шифр детали = «0011003»]

R12

Шифр детали

Название детали

Цех

000 1 1003

Болт М 1

Цех 1

00011003

Болт М 1

Цех 3

Следующей специальной операцией является операция проектирования. Пусть R — отношение, SR = (А1, ... , Аn) — схема отношения R. Обозначим через В подмножество [ Аi]; В { Аi } При этом пусть В1 — множество атрибутов из { Ai }, не вошедших в В. Если В = {A1j.A2j .....Akj}, В1 = {А1j,А2j,...,Аkj}и r = <а1j, а2j,...,аkj >, аkj Аkji, то r [В], s= < a1j, а2j, ... , аm, > ; аm, Аmj

Проекцией отношения R па набор атрибутов В, обозначаемой R[B], называется отношение со схемой, соответствующей набору атрибутов В SR|B| = В, содержащему кортежи, получаемые из кортежей исходного отношения R путем удаления из них значений, не принадлежащих атрибутам из набора В.

R[B] = {r[В]}

По определению отношений все дублирующие кортежи удаляются из результирующего отношения.

Операция проектирования, называемая иногда также операцией вертикального выбора, позволяет получить только требуемые характеристики моделируемого объекта. Чаще всего операция проектирования употребляется как промежуточный шаг в операциях горизонтального выбора, или фильтрации. Кроме того, она используется самостоятельно на заключительном этапе получения ответа на запрос. Например, выберем все цеха, которые изготавливают деталь «Болт Ml».

Для этого нам необходимо из отношения R10 выбрать детали с заданным названием, а потом полученное отношение спроектировать на столбец «Цех». Результатом выполнения этих операций будет отношение R14:

R13 = R10 [ Название детали = «Болт Ml» ]

R14 = R13 [ Цех |

R13

Шифр детали детали

Название

Цех

00011003 Болт M1 Цех 1

00011003

Болт M1l

Цех3

 

R14

Цех

Цех 1

Цех 3

Следующей специальной операцией реляционной алгебры является операция условного соединения.

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

Пусть R = {r}, Q = { q } — исходные отношения,

SR, SQ — схемы отношений R и Q соответственно.

SR = (А1, А2, ... , Ak): SQ = (В1 В2, ... , Bm),

где А,, В, — имена атрибутов в схемах отношений R и Q соответственно. При этом полагаем, что заданы наборы атрибутов А и В

А { Аi } ,j=1,k; В { Bj } j=1,m, и эти наборы состоят из Q-сравнимых атрибутов.

Тогда соединением отношений R и Q при условии р будет подмножество декартова произведения отношений R и Q, кортежи которого удовлетворяют условию р, рассматриваемому как одновременное выполнение условий:

R [ Р ] Q = { r.q) | (г. q) | r.A Qj q.Bj - «Истина», i=l,k}

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

R15

Шифр детали

Название детали

Материал

00011073

Гайка Ml

сталь-ст1

00011075

Гайка М2

сталь-ст2

00011076

Гайка МЗ

сталь-ст1

00011003

Болт М1

сталь-стЗ

00011006

Болт МЗ

сталь-стЗ

00013063

Шайба Ml

сталь-ст1

00013066

Шайба МЗ

сталь-ст1

00011077

Гайка М4

сталь-ст2

00011004

Болт М2

сталь-стЗ

00011005

Болт М5

сталь-стЗ

00013062

Шайба М2

сталь-ст1

 

R16

Название детали

Гайка M1

Гайка МЗ

Шайба М1

Шайба МЗ

Шайба М2

Получим перечень деталей, которые изготавливаются в цеху 1 из материала «сталь-ст1»

R16 = (R15[(R15Шифр детали =R10.Шифр детали) ^R10.Цех = «Цех1» ^ ^ R15.Материал =«сталь-ст1»] R10)[Hазвание детали]

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

Для определения операции деления рассмотрим сначала понятие множества образов.

Пусть R — отношение со схемой SR = (A1, A2 ,..., Ak);

Пусть А — некоторый набор атрибутов А { Аi } i=l,k , А1 — набор атрибутов, не входящих в множество А.

Пересечение множеств А и А1 пусто: А А1 = 0; объединение множеств равно множеству всех атрибутов исходного отношения: A А1 = SR.

Тогда множеством образов элемента у проекции R[А] называется множество таких элементов у проекции R[A1] , для которых сцепление (х, у) является кортежами отношения R, то есть

QA(x) = {у | у R[A1] ^ (х, у) R} - множество образов.

Например, множеством образов отношения R15 по материалу «сталъ-ст2» будет множество кортежей

К15.Материал = {< 00011075, Гайка М2, «сталь-ст2»>, < 00011077, Гайка М4, «сталь-ст2»>}

Дадим теперь определение операции деления. Пусть даны два отношения R и Т соответственно со схемами: SR = (А1, А2, ... , Ak); ST =-(В1, В2, ... , Вm);

А и В — наборы атрибутов этих отношений, одинаковой длины (без повторений);

А SR ; В ST. Атрибуты А1 — это атрибуты из R, не вошедшие в множество А.

Пересечение множеств А А1 = — пусто и A А1 = SR. Проекции R[A] и Т[В] совместимы по объединению, то есть имеют эквивалентные схемы: SR|A|~ ST[B|.

Тогда операция деления ставит в соответствие отношениям R и Т отношение

Q = R[A:B]T, кортежи которого являются теми элементами проекции R[A1], для которых Т[В] входит в построенные для них множество образов:

R[A:B]T = {r | r R[A1] ^ Т[В] (у | у R [А] ^ (r, у) R } }.

Операция деления удобна тогда, когда требуется сравнить некоторое множество характеристик отдельных атрибутов. Например, пусть у нас есть отношение R7, которое содержит номенклатуру всех выпускаемых деталей на нашем предприятии, а в отношении R10 хранятся сведения о том, что и в каких цехах действительно выпускается. Поставим задачу определить перечень цехов, в которых выпускается вся номенклатура деталей.

Тогда решением этой задачи будет операция деления отношения R10 на отношение R7 по набору атрибутов (Шифр детали, Наименование детали).

R17 = R10[Шифр детали, Наименование детали: Шифр детали, Наименование детали] R7

R 17

Цех

Цех1

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

  1. Построим отношение, которое моделирует ситуацию, когда в каждом цеху изготавливается вся номенклатура, это уже построенное нами ранее расширенное декартово произведение отношений R7 и R8. Это отношение R9:

    R9 = R7R8

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

    R11 =R9\R10

  3. Далее найдем те цеха, в которых не все детали выпускаются, для этого нам надо отношение R11 спроектировать на столбец «Цех»:

    R18 = R11[Цех]

R18

Цех

Цех 2

ЦeхЗ

 

  1. А теперь из перечня всех цехов вычтем те, кто выпускает не все детали, и получим ответ на запрос, и это будет тот же результат, что и в отношении R17.

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

R1 = <ФИО, Дисциплина, Оценка>;

R2 = <ФИО, Группа>;

R3 = < Группы, Дисциплина>,

где R1 — информация о попытках (как успешных, так и неуспешных) сдачи экзаменов студентами; R2 — состав групп; R3 — список дисциплин, которые надо сдавать каждой группе. Домены для атрибутов формально задавать не будем, но, ориентируясь на здравый смысл, будем считать, что доменом для атрибута Дисциплина будет множество всех дисциплин, преподающихся в ВУЗе, доменом для атрибута Группа будет множество всех групп ВУЗа и т. д.
Покажем, каким образом можно получить из этих таблиц интересующие нас

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

S = (R1[R1.ФИО = Rl.ФИО ^ R1Дисцинлина не равно R'1.Дисциплина ^

R1Оценка <= 2^ R'1.Оценка < 2] Rэ1,)[ФИО]

Этот пример весьма интересен: для поиска строк, удовлетворяющих в совокупности условию больше одною, применяется операция соединения отношения с самим собой. Поэтому мы как бы взяли копию отношения R1 и назвали ее R'1.

R5 = (R1|[Оценкa = 5])[ФИО, Дисциплина];

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

R6=(R4\R5)[ФИО].

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

R2[ФИО] \ R6

Обратите внимание, что для получения множества студентов, что-либо не сдавших на «отлично» (R6). мы осуществили «инверсию» множества всех отлично сданных пар <студент—дисциплина> (R5) путем вычитания его из предварительного построенного универсального множества (R4). Рекомендуем очень внимательно разобрать этот пример и вникнуть в смысл каждого действия — это очень пригодится для понимания реляционной алгебры.

Задания для самостоятельной работы

Задание 1

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

R,

ФИО клиента

филиала

№ счета

Остаток

Кредит

 



 

R2

№ филиала

Район



С использованием языка реляционной алгебры составить запросы, позволяющие выбрать:

  1. Филиалы, клиенты которых имеют счета с остатком, превышающим $1000.
  2. Клиентов, которые имеют счета во всех филиалах данного банка.
  3. Клиентов, которые имеют только по одному счету в разных филиалах банка. То есть в общем у этих клиентов может быть несколько счетов, но в одном филиале не более одного счета.
  4. Клиенты, которые имеют счета в нескольких филиалах банка расположенных только в одном районе.
  5. Филиалы, которые не имеют ни одного клиента.
  6. Филиалы, которые имеют клиентов с остатком на счету 0 (ноль).
  7. Филиалы, у которых есть клиенты с кредитом, превышающим остаток на счету в 2 раза.

Задание 2

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

R1

Филиал

Страна



 

R2

Филиал

Заказчик

№ заказа




 

R3

N заказа

Товар

Количество




 

R4

Заказчик

Страна



С использованием реляционной алгебры составить запросы, позволяющие выбрать:

  1. Заказчиков, которые работают со всеми филиалами фирмы, но покупают только один товар.
  2. Филиалы фирмы, которые торгуют всеми товарами.
  3. Товары, которые фирма продает только в одной стране.
  4. Заказчиков, которые работают с филиалами фирмы, которые расположены только в одной стране.
  5. Филиалы, с которыми не работает ни один заказчик.
  6. Заказчиков, которые работают только с филиалами, расположенными в той же стране, что и заказчик.
  7. Заказчиков, которые покупают все товары, представленные в отношении R3.
к алгоритмизации   алгоритмы, струкутуры данных и программирование   СУБД   ЯиМП   3GL   4GL   5GL   технологии прогр.

(время поиска примерно 20 секунд)

Знаете ли Вы, что cогласно релятивистской мифологии "гравитационное линзирование - это физическое явление, связанное с отклонением лучей света в поле тяжести. Гравитационные линзы обясняют образование кратных изображений одного и того же астрономического объекта (квазаров, галактик), когда на луч зрения от источника к наблюдателю попадает другая галактика или скопление галактик (собственно линза). В некоторых изображениях происходит усиление яркости оригинального источника." (Релятивисты приводят примеры искажения изображений галактик в качестве подтверждения ОТО - воздействия гравитации на свет)
При этом они забывают, что поле действия эффекта ОТО - это малые углы вблизи поверхности звезд, где на самом деле этот эффект не наблюдается (затменные двойные). Разница в шкалах явлений реального искажения изображений галактик и мифического отклонения вблизи звезд - 1011 раз. Приведу аналогию. Можно говорить о воздействии поверхностного натяжения на форму капель, но нельзя серьезно говорить о силе поверхностного натяжения, как о причине океанских приливов.
Эфирная физика находит ответ на наблюдаемое явление искажения изображений галактик. Это результат нагрева эфира вблизи галактик, изменения его плотности и, следовательно, изменения скорости света на галактических расстояниях вследствие преломления света в эфире различной плотности. Подтверждением термической природы искажения изображений галактик является прямая связь этого искажения с радиоизлучением пространства, то есть эфира в этом месте, смещение спектра CMB (космическое микроволновое излучение) в данном направлении в высокочастотную область. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 13.06.2019 - 05:11: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМА ГЛОБАЛЬНОЙ ГИБЕЛИ ПЧЁЛ И ДРУГИХ ОПЫЛИТЕЛЕЙ РАСТЕНИЙ - Карим_Хайдаров.
12.06.2019 - 09:05: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
11.06.2019 - 18:05: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> Эксперименты Сёрла и его последователей с магнитами - Карим_Хайдаров.
11.06.2019 - 18:03: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Андрея Маклакова - Карим_Хайдаров.
11.06.2019 - 13:23: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вячеслава Осиевского - Карим_Хайдаров.
11.06.2019 - 13:18: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Светланы Вислобоковой - Карим_Хайдаров.
11.06.2019 - 06:28: АСТРОФИЗИКА - Astrophysics -> К 110 летию Тунгуской катастрофы - Карим_Хайдаров.
10.06.2019 - 21:23: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Владимира Васильевича Квачкова - Карим_Хайдаров.
10.06.2019 - 19:27: СОВЕСТЬ - Conscience -> Высший разум - Карим_Хайдаров.
10.06.2019 - 19:24: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
10.06.2019 - 19:14: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
10.06.2019 - 08:40: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
Bourabai Research Institution home page

Боровское исследовательское учреждение - Bourabai Research Bourabai Research Institution