17225

РЕЛЯЦИОННАЯ АЛГЕБРА

Лекция

Информатика, кибернетика и программирование

Лекция №4 рЕЛЯЦИОННАЯ АЛГЕБРА Операционная спецификация из O см. модель данных M = {D R O} определяет набор операций для обеспечения доступа к данным. Манипулирование реляционными данными осуществляется при помощи реляционной алгебры или эквивалентного ему реляци

Русский

2013-06-30

216 KB

23 чел.

Лекция №4

рЕЛЯЦИОННАЯ АЛГЕБРА

Операционная спецификация из O (см. модель данных M = {D, R, O}) определяет набор операций для обеспечения доступа к данным. Манипулирование реляционными данными осуществляется при помощи реляционной алгебры или эквивалентного ему реляционного исчисления.

В реализациях конкретных реляционных СУБД не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SQL (Structured Query Language). Язык SQL представляет собой смесь операторов реляционной алгебры и выражений реляционного исчисления.

Язык доступа к данным называется реляционно-полным, если он по выразительной силе не уступает реляционной алгебре (или, что то же самое, реляционному исчислению), т.е. любой оператор реляционной алгебры может быть выражен средствами этого языка.

Язык SQL является реляционно-полным.

Замкнутость реляционной алгебры

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

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

 

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

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

Теоретико-множественные операции:

  •  Объединение
  •  Пересечение
  •  Вычитание
  •  Декартово произведение

Специальные реляционные операции:

  •  Селекция (Выборка)
  •  Проекция
  •  Соединение
  •  Деление

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

Некоторые реляционные операторы (такие как объединение, пересечение, вычитание) требуют, чтобы отношения имели одинаковые схемы. Операция объединения двух отношений представляет собой объединение двух множеств кортежей, взятых из экземпляров соответствующих отношений.

Определяют три свойства, когда не выполняются теоретико-множественных операций.

Во-первых, если исходные отношения имеют разное количество атрибутов.

Во-вторых, если отношения имеют одинаковое количество атрибутов, но атрибуты имеют различные имена.

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

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

Математическая точность требует соблюдения строгого соответствия требованиям совместимости по типу, хотя на практике свойство соответствия имен атрибутов может не выполняться. Этот недостаток всегда можно устранить не уровни представления, т.е. переименовать имя атрибута при отображении его пользователю, при этом физически (в схеме) имена будут различны.

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

Оператор переименования атрибутов имеет следующий синтаксис:

R(a1 AS a1, a2 AS a2,…an AS an)

где R - отношение, a1, a2 … - исходные имена атрибутов,

a1, a2 - новые имена атрибутов.

Оператор AS, в нотации SQL, может применяться и для имен отношений, что дает возможность альтернативные имена для формирования запросов.

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

Проекция

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

Синтаксис операции проекции:

 или R =  X,Y,…,Z(A) 

Операция проекции является унарной операцией и дает "вертикальный срез" отношения, в котором удалены все возникшие при таком срезе дубликаты кортежей.

Пример. Пусть дано отношение  с информацией о поставщиках, включающих наименование и месторасположение:

Таблица 11 Отношение A (Поставщики) 

Номер поставщика

Наименование поставщика

Город поставщика

1

Иванов

Уфа

2

Петров

Москва

3

Сидоров

Москва

4

Сидоров

Челябинск

Проекция  или R = Город поставщика(А) будет иметь вид:

Таблица 12 Отношение R = Город поставщика(А)

Город поставщика

Уфа

Москва

Челябинск

Синтаксическая конструкция на SQL таких запросов описывается следующим образом:

SELECT X, Y,…,Z FROM A

Для приведенного примера SQL – запрос соответствует структуре:

SELECT Город поставщика FROM A

Выборка (ограничение, селекция)

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

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

Синтаксис операции выборки:

,

или

или

R = XY(A)

Пример. Пусть дано отношение  с информацией о сотрудниках:

Таблица 9 Отношение A 

Табельный номер

Фамилия

Зарплата

1

Иванов

1000

2

Петров

2000

3

Сидоров

3000

Результат выборки  или R = Зарплата<300(A) будет иметь вид:

Таблица 10 Отношение R = Зарплата<300(A) 

Табельный номер

Фамилия

Зарплата

1

Иванов

1000

2

Петров

2000

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

Синтаксическая конструкция на SQL таких запросов описывается следующим образом:

SELECT X, Y,…,Z FROM A WHERE X  Y

Для приведенного примера SQL – запрос соответствует структуре:

SELECT Табельный номер, Фамилия, Зарплата FROM A 

WHERE Зарплата < 300

Соединение

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

Соединение является бинарной операцией и включает 4 вида соединения:

  •  Общая операция соединения
  •  -соединение (тэта - соединение)
  •  Экви - соединение
  •  Естественное соединение

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

Общая операция соединения

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

или R = A ><C B 

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

Другими словами, операция соединения представляет собой результат последовательного применения операций декартового произведения (см. следующую тему) и выборки.

Если в отношениях  и  имеются атрибуты с одинаковыми именами, то перед выполнением соединения такие атрибуты необходимо переименовать, или, как в SQL, к именам атрибутов приписывают имена отношения.

Тэта - соединение

Определение. Пусть отношение  содержит атрибут , отношение  содержит атрибут , а - один из операторов сравнения ( и т.д.). Тогда -соединением отношения  по атрибуту  с отношением  по атрибуту  называется отношение со схемой,   , и экземпляром, состоящим из кортежей, представляющих собой сцепление кортежей отношений  и  для которых выполняется условие XY.

или R = A ><XY B 

Иногда, для операции  - соединения применяют более короткое обозначение .

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

Таблица 13 Отношение A (Поставщики)

Номер поставщика

Наименование поставщика

X (Статус поставщика)

1

Иванов

4

2

Петров

1

3

Сидоров

2

Таблица 14 Отношение B (Детали)

Номер детали

Наименование детали

Y (Статус детали)

1

Болт

3

2

Гайка

2

3

Винт

1

Ответ на вопрос "какие поставщики имеют право поставлять какие детали?" дает -соединение  или R = A ><X  Y B:

Таблица 15 Отношение "Какие поставщики поставляют какие детали"

Номер поставщика

Имя поставщика

X (Статус поставщика)

Номер детали

Наименование детали

Y (Статус детали)

1

Иванов

4

1

Болт

3

1

Иванов

4

2

Гайка

2

1

Иванов

4

3

Винт

1

2

Петров

1

3

Винт

1

3

Сидоров

2

2

Гайка

2

3

Сидоров

2

3

Винт

1

Синтаксическая конструкция на SQL таких запросов описывается следующим образом:

SELECT X, Y,…,Z FROM A, B WHERE X  Y

Для приведенного примера SQL – запрос соответствует структуре:

SELECT Номер поставщика, Имя поставщика, X, Номер детали, Наименование детали, Y 

FROM A,B WHERE X  Y

Экви - соединение

Наиболее важным частным случаем  - соединения является случай, когда есть равенство.

Определение. Пусть отношение  содержит атрибут , отношение  содержит атрибут .Тогда экви - соединением отношения  по атрибуту  с отношением  по атрибуту  называется отношение со схемой,   , и экземпляром, состоящим из кортежей, представляющих собой сцепление кортежей отношений  и  для которых выполняется условие X=Y.

Обозначение экви  - соединения:

 или R = A ><Y B 

Пример. Пусть имеются отношения ,  и , хранящие информацию о поставщиках, деталях и поставках соответственно (для удобства введем краткие наименования атрибутов):

Таблица 16 Отношение P (Поставщики)

Номер поставщика

PNUM

Наименование поставщика

PNAME

1

Иванов

2

Петров

3

Сидоров

Таблица 17 Отношение D (Детали)

Номер детали

DNUM

Наименование детали

DNAME

1

Болт

2

Гайка

3

Винт

Таблица 18 Отношение PD (Поставки)

Номер поставщика

PNUM

Номер детали

DNUM

Поставляемое количество

VOLUME

1

1

100

1

2

200

1

3

300

2

1

150

2

2

250

3

1

1000

Ответ на вопрос, какие детали поставляются поставщиками, дает экви - соединение  или R = P ><PNUM = PNUM PD. На самом деле, т.к. в отношениях имеются одинаковые атрибуты, то требуется сначала переименовать атрибуты, а потом выполнить экви - соединение. Запись становится более громоздкой:

или R = P(PNUM AS PMUM_1)><PMUM_1 = PMUM_2 PD(PNUM AS PMUM_2)

Обычно, такой сложной формой записи не пользуются. Но как бы то ни было, в результате имеем отношение:

Таблица 19 Отношение "Какие детали поставляются какими поставщиками"

Номер поставщика

PNUM1

Наименование поставщика

PNAME

Номер поставщика

PNUM2

Номер детали

DNUM

Поставляемое количество

VOLUME

1

Иванов

1

1

100

1

Иванов

1

2

200

1

Иванов

1

3

300

2

Петров

2

1

150

2

Петров

2

2

250

3

Сидоров

3

1

1000

Недостатком экви - соединения является то, что если соединение происходит по атрибутам с одинаковыми именами (а так чаще всего и происходит!), то в результирующем отношении появляется два атрибута с одинаковыми значениями. В рассмотренном примере атрибуты PNUM_1 и PNUM_2 содержат дублирующие данные. Избавиться от этого недостатка можно, взяв проекцию по всем атрибутам, кроме одного из дублирующих. Именно так действует естественное соединение.

Синтаксическая конструкция на SQL таких запросов описывается следующим образом:

SELECT X, Y,…,Z FROM A, B WHERE X = Y

Для приведенного примера SQL – запрос соответствует структуре:

SELECT P.PNUM, PDUM, PD.PNUM, DNUM, VALUME 

FROM P, PD

WHERE P.PNUM = PD.PNUM

Естественное соединение

Определение. Пусть даны отношения  и , имеющие одинаковые атрибуты  (т.е. атрибуты с одинаковыми именами и определенные на одинаковых доменах).

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

Синтаксис естественного соединения описывается как:

 или R = A >< B 

Замечание. В синтаксисе естественного соединения не указываются, по каким атрибутам производится соединение. Естественное соединение производится по всем одинаковым атрибутам.

Замечание. Естественное соединение эквивалентно следующей последовательности реляционных операций:

  1.  Переименовать одинаковые атрибуты в отношениях
  2.  Выполнить декартово произведение отношений
  3.  Выполнить выборку по совпадающим значениям атрибутов, имевших одинаковые имена
  4.  Выполнить проекцию, удалив повторяющиеся атрибуты
  5.  Переименовать атрибуты, вернув им первоначальные имена

Замечание. Можно выполнять последовательное естественное соединение нескольких отношений. Нетрудно проверить, что естественное соединение (как, впрочем, и соединение общего вида) обладает свойством ассоциативности, т.е.

 или (A><B)><C = A><(B><C) 

поэтому такие соединения можно записывать, опуская скобки:

 или A >< B >< C

Пример. В предыдущем примере ответ на вопрос, "какие детали поставляются поставщиками", более просто записывается в виде естественного соединения трех отношений  или R = (P><PD><D) (для удобства просмотра порядок атрибутов изменен, это является допустимым по свойствам отношений):

Таблица 20 Отношение P JOIN PD JOIN D или R = (P><PD><D)

Номер поставщика

PNUM

Наименование поставщика

PNAME

Номер детали

DNUM

Наименование детали

DNAME

Поставляемое количество

VOLUME

1

Иванов

1

Болт

100

1

Иванов

2

Гайка

200

1

Иванов

3

Винт

300

2

Петров

1

Болт

150

2

Петров

2

Гайка

250

3

Сидоров

1

Болт

1000

Синтаксическая конструкция на SQL таких запросов описывается следующим образом:

SELECT X, Y,…,Z FROM A, B, C WHERE X = Y AND Y = Z

Для приведенного примера SQL – запрос соответствует структуре:

SELECT P.PNUM, PDUM, PD.PNUM, DNUM, VALUME FROM P, PD, D

WHERE P.PNUM = PD.PNUM AND D.DNAME = PD. DNAME

Деление

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

Отношение  выступает в роли делимого, отношение  выступает в роли делителя. Деление отношений аналогично делению чисел с остатком.

Синтаксис операции деления:

R = A / B

Замечание. Типичные запросы, реализуемые с помощью операции деления, обычно в своей формулировке имеют слово "все" - "какие поставщики поставляют все детали?".

Пример. В примере с поставщиками, деталями и поставками ответим на вопрос, "какие поставщики поставляют все детали?".

В качестве делимого возьмем проекцию X = PNUM, DNUM(PD), содержащую номера поставщиков и номера поставляемых ими деталей:

Таблица 21 Проекция X = PNUM, DNUM(PD)

Номер поставщика

PNUM

Номер детали

DNUM

1

1

1

2

1

3

2

1

2

2

3

1

В качестве делителя возьмем проекцию Y = DNUM(D), содержащую список номеров всех деталей (не обязательно поставляемых кем-либо):

Таблица 22 Проекция Y = DNUM(D)

Номер детали DNUM

1

2

3

Деление / Y дает список номеров поставщиков, поставляющих все детали:

Таблица 23 Отношение / Y

Номер поставщика

PNUM

1

Оказалось, что только поставщик с номером 1 поставляет все детали.


 

А также другие работы, которые могут Вас заинтересовать

31690. Форми переживання емоцій і почуттів 29.5 KB
  Настрій це загальний емоційний стан який своєрідно забарвлює на певний час діяльність людини характеризує її життєвий тонус. Афект як і настрій залежить певною мірою від індивідуальних особливостей людини: її темпераменту характеру вихованості. Афекти викликають глибокі зміни у психічному житті людини виснажують її.
31691. Мотиваційна сфера особистості. Потяги і бажання. Прагнення особистості. Ризик як вияв активності особистості 81.5 KB
  Здійснюючи цілеспрямовані дії людина зустрічається з різноманітними перешкодами. Тут і оцінка ситуації і вибір шляху для майбутньої дії відбір засобів потрібних для досягнення мети прийняття рішень і т.Якщо в людини відсутня актуальна потреба виконувати дію але при цьому необхідність виконання її вона усвідомлює то воля створює допоміжне спонукання змінюючи смисл дії робить його більш значущим. Довільні та вольові дії включаються в зміст вольової поведінки людини.
31692. Самоосвіта та самовиховання як умова успішної діяльності вчителя 31 KB
  Кількість часу й сил які вчитель витрачає на самоосвіту залежить від його мотивації. Ніхто не сперечатиметься з тезою що якщо вчитель хороший то й рівень знань учнів високий. Працювати над собою вчитель починає ще зі студентської лави. Якщо вчитель не вдосконалює себе не експериментує то перетворюється на ремісника який стоїть за верстатом і робить кожного дня одну й ту ж роботу.
31693. Розвиток і виховання дитини в сім'ї потребує безлічі діяльнісних ситуацій, в яких відбувається формування особистості заданої орієнтації 47 KB
  Головне навантаження щодо забезпечення реального звязку з сімєю лягає на плечі класного керівника. Свою діяльність він організовує через класний батьківський комітет, батьківські збори, а також через вчителів, які працюють в даному класі. Важливою частиною практичної діяльності класного керівника з підтримання контактів
31695. Тактики виховання дітей у сім’ї 27.5 KB
  Вдаючись до такої тактики, батьки намагаються відгородити дитину від життєвих реалій, випробувань, намагаються все вирішувати за неї, задовольняти її потреби і примхи. За таких умов дитина позбавлена змоги формувати в собі необхідні для подальшого життя психологічні, вольові якості, об'єктивно оцінювати себе, свої можливості й інших людей, цілеспрямовано працювати над собою. Усе це деформує її внутрішній світ, систему цінностей, різко занижує або завищує її вимоги до оточення, спонукає до девіантних форм задоволення своїх потреб
31696. Юнацький вік 59 KB
  У зв’язку з тенденцією до різкого омолодження шлюбу актуальною стає підготовка до одруження молоді. Все це викликає у них незадоволення розчарування невпевненість у собі небажання разом з партнером налагоджувати сімейні взаємини зниження мотивації шлюбу. Наскільки такі знання наприклад роблять молодь готовою до шлюбу [2; 8; 23; 25; 36; 40; 57; 77; 84] Певний вклад у її вивчення унесли М. Одначе недостатньо вивченими залишилися питання змісту структури готовності до шлюбу шляхів поліпшення підготовки молоді до сімейного життя.
31697. Досліджується вплив сімї на формування особистості дітей 58.5 KB
  Досліджується вплив сімї на формування особистості дітей. Психологія вивчає особистісні та соціально-психологічні чинники, що зміцнюють або дестабілізують шлюб. Багато уваги приділяється питанням статево-рольового виховання молоді, формуванню просімейної мотивації, психологічним аспектам сексуальних стосунків, взаємної адаптації шлюбної пари, їхній психологічній сумісності. Чільне місце відводиться дослідженню соціально-психологічних процесів, що відбуваються в сім'ї: сімейна комунікація ті інтеракція, міжособистісна перцепція, рольова диференціація у взаєминах подружжя.
31698. Становлення шлюбно-сімейних відносин 33 KB
  Для багатьох джерел національних правових систем характерним є уникнення законодавчого визначення поняття шлюбу. Договірна концепція шлюбу є найбільш поширеною. Розуміння шлюбу як союзу двох незалежних і рівноправних партнерів Східна Європа в т. Дещо іншим є поняття шлюбу як союзу чоловіка й жінки у мусульманських державах.