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 поставляет все детали.


 

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

71778. РЕАЛИЗАЦИЯ КОНСТИТУЦИОННЫХ ГАРАНТИЙ ПРАВ ЧЕЛОВЕКА В ПРАВОВОМ СТАТУСЕ АКЦИОНЕРА В АКЦИОНЕРНОМ ОБЩЕСТВЕ 134 KB
  Гражданский кодекс в части 1 статьи 96 дает такое определение: Акционерным обществом признается общество уставный капитал которого разделен на определенное число акций; участники акционерного общества акционеры не отвечают по его обязательствам и несут риск...
71779. ОТДЕЛЬНЫЕ ВОПРОСЫ ОБЕСПЕЧЕНИЯ НОТАРИАТОМ ГАРАНТИЙ ПРАВА НАСЛЕДОВАНИЯ В РОССИЙСКОЙ ФЕДЕРАЦИИ 110 KB
  Право наследования представляет собой одну из гарантий права собственности обеспечивая его стабильность и преемственность и гарантируется нормами различных законов и подзаконных актов системы отечественного законодательства раскрывающими и конкретизирующими конституционные нормы.
71780. ПРАВОВОЕ РЕГУЛИРОВАНИЕ ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ ПРОИЗВОДСТВА ПО ДЕЛАМ ОБ АДМИНИСТРАТИВНЫХ ПРАВОНАРУШЕНИЯХ 96 KB
  В Конституции предусмотрено что сбор хранение использование и распространение информации о частной жизни лица без его согласия не допускаются. Об информации информатизации и защите информации. В соответствии с Положением о Главном информационном центре Министерства...
71781. ОСОБЕННОСТИ УЧАСТИЯ ИНОСТРАННОГО ГРАЖДАНИНА В ПРОЦЕДУРЕ УСЫНОВЛЕНИЯ РОССИЙСКИХ ДЕТЕЙ ИНОСТРАННЫМИ ГРАЖДАНАМИ 130 KB
  Помимо законодательства указанных выше государств с учетом положений международного договора Российской Федерации о межгосударственном сотрудничестве в области усыновления детей должны соблюдаться правила российского законодательства а именно: правила о детях передаваемых на усыновление...
71782. ВОПРОСЫ РАЗВИТИЯ И ФИНАНСОВОГО ОБЕСПЕЧЕНИЯ ЭКОЛОГИЧЕСКОГО ТУРИЗМА В РОССИИ С УЧЕТОМ ОПЫТА США 237 KB
  Охрана окружающей природной среды это одна из функций государства требующая больших затрат со стороны и самого государства и его субъектов муниципальных образований юридических и физических лиц. Экологический туризм это любые виды туризма и рекреации в природе которые не наносят ущерба...
71783. БАНК РОССИИ И КОММЕРЧЕСКИЕ БАНКИ КАК ОСНОВА ИНФРАСТРУКТУРЫ ФИНАНСОВОГО ОБСЛУЖИВАНИЯ 89.5 KB
  Банк России и коммерческие банки значимая составная часть финансовой системы государства поскольку денежные средства аккумулируются в основном на счетах в банках. Банком России то это приведет к злоупотреблениям коммерческих банков.
71784. АДМИНИСТРАТИВНЫЕ ПРАВОНАРУШЕНИЯ В ОБЛАСТИ ПРЕДПРИНИМАТЕЛЬСКОЙ ДЕЯТЕЛЬНОСТИ: ПОНЯТИЕ И ОБЩАЯ ХАРАКТЕРИСТИКА 78 KB
  Понятие административного правонарушения сформулировано в Кодексе об административных правонарушениях: таковым признается противоправное виновное действие бездействие физического или юридического лица за которое Кодексом или законами субъектов Федерации об административных...
71785. ЦЕЛИ И СОДЕРЖАНИЕ АДМИНИСТРАТИВНОЙ РЕФОРМЫ В РОССИИ 83 KB
  Что было достигнуто за прошедшие четыре года: восстановлен конституционный правопорядок укреплена а по сути отстроена заново вертикаль федеральной исполнительной власти восстановлено единое правовое пространство страны пресечены опасные процессы деградации государственной власти...
71786. ПОНЯТИЕ И ПРИЗНАКИ НОРМАТИВНОГО ПРАВОВОГО АКТА ФЕДЕРАЛЬНОГО ОРГАНА ИСПОЛНИТЕЛЬНОЙ ВЛАСТИ И ЕГО РОЛЬ В МЕХАНИЗМЕ АДМИНИСТРАТИВНО-ПРАВОВОГО РЕГУЛИРОВАНИЯ 146.5 KB
  Административно-правовое регулирование общественных отношений в сфере публичного управления проводится в определенных формах и с помощью методов административно-правового регулирования. В связи с этим повышенный интерес правоведов вызывает концепция нормативного правового акта...