Базы данных. Лекции БД. Лекция 5 Основные понятия информационных систем 5 История развития компьютеризации информационных процессов и систем. 5

• Название: Лекция 5 Основные понятия информационных систем 5 История развития компьютеризации информационных процессов и систем. 5
• Анкор: Базы данных
• Дата: 05.01.2022
• Размер: 1.07 Mb.
• Имя файла: Лекции БД.doc
• Тип: Лекция; #324711
• страница: 7 из 24

Лекция 4.

5.Обзор реляционной алгебры

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

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

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

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



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



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

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

5.2.Операции реляционной алгебры.

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

1. 
   Объединение
   
2. 
   Пересечение
   
3. 
   Вычитание
   
4. 
   Декартово произведение
   

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

• 
  Выборка
  

• 
  Проекция
  
• 
  Соединение
  
• 
  Деление
  

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

Отношения, совместимые по типу

Некоторые реляционные операции (например, объединение) требуют, чтобы отношения имели одинаковые заголовки.

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

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

• 
  Отношения имеют одно и то же множество имен атрибутов, т.е. для любого атрибута в одном отношении найдется атрибут с таким же наименованием в другом отношении,
  

• 
  Атрибуты с одинаковыми именами определены на одних и тех же доменах.
  

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

Операция переименования атрибутов

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



где

- отношение,

- исходные имена атрибутов,

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

В результате применения операции переименования атрибутов получаем новое отношение, с измененными именами атрибутов.

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

5.2.1.1.Объединение

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

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

Замечание. Объединение, как и любое отношение, не может содержать одинаковых кортежей. Поэтому, если некоторый кортеж входит и в отношение , и отношение , то в объединение он входит один раз.

5.2.1.2. Пересечение

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

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

5.2.1.3.Вычитание

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

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

5.2.1.4.Декартово произведение

Определение 5. Декартовым произведением двух отношений и называется отношение, заголовок которого является сцеплением заголовков отношений и :

,

а тело состоит из кортежей, являющихся сцеплением кортежей отношений и :

, таких, что , .

Синтаксис операции декартового произведения:

Замечание. Мощность произведения равна произведению мощностей отношений и , т.к. каждый кортеж отношения соединяется с каждым кортежем отношения .

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

Замечание. Перемножать можно любые два отношения, совместимость по типу при этом не требуется.

5.2.2.Специальные реляционные операторы

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

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

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

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

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

5.2.2.2.Проекция

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

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

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

5.2.2.3.Соединение

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

Обычно рассматривается несколько разновидностей операции соединения:

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

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

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

Определение 8. Соединением отношений и по условию называется отношение

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

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

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

Определение 9. Пусть отношение содержит атрибут , отношение содержит атрибут , а - один из операторов сравнения ( и т.д.). Тогда -соединением отношения по атрибуту с отношением по атрибуту называют отношение

Это частный случай операции общего соединения.

Иногда, для операции -соединения применяют следующий, более короткий синтаксис:

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

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

Синтаксис экви-соединения:

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

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

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

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

Естественное соединение настолько важно, что для него используют специальный синтаксис:

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

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

• 
  Переименовать одинаковые атрибуты в отношениях
  

• 
  Выполнить декартово произведение отношений
  

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

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

5.2.2.4.Деление

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

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

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

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

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

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

Номер поставщика PNUM	Номер детали DNUM
1	1
1	2
1	3
2	1
2	2
3	1

В качестве делителя отношение содержащее список номеров всех деталей :

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

1

2

3

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

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

1

5.2.3.Зависимые реляционные операторы

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

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

Операция соединения определяется через операторы декартового произведения и выборки. Для операции естественного соединения добавляется операция проекции.

Операция пересечения

Операция пересечения выражается через вычитание следующим образом:



Операция деления

Операция деления выражается через операторы вычитания, декартового произведения и проекции следующим образом:



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

5.2.4.Примитивные реляционные операторы

Оставшиеся реляционные операторы (объединение, вычитание, декартово произведение, выборка, проекция) являются примитивными операторами - их нельзя выразить друг через друга.

Операция декартового произведения

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

Операция проекции

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

Операция выборки

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

Операции объединения и вычитания

5.2.5.Запросы, невыразимые средствами реляционной алгебры

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

Невыразимость транзитивного замыкания реляционными операторами

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

Пример 5.2. Рассмотрим отношение, описывающее сотрудников некоего предприятия. Отношение содержит данные о табельном номере сотрудника, фамилии, должности и табельном номере руководителя сотрудника – СОТРУДНИКИ (ТАБ_НОМ, ФАМИЛИЯ, ДОЛЖНОСТЬ, ТАБ_НОМ_РУК):

ТАБ_НОМ	ФАМИЛИЯ	ДОЛЖНОСТЬ	ТАБ_НОМ_РУК
1	Иванов	Директор	1
2	Петров	Глав.бухгалтер	1
3	Сидоров	Бухгалтер	2
4	Васильев	Начальник цеха	1
5	Сухов	Мастер	4
6	Шарипов	Рабочий	5

Рассмотрим запрос "Перечислить всех руководителей (прямых и непрямых) данного сотрудника".

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

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

• 
  либо кортеж ,
  

• 
  либо найдется конечная последовательность элементов , такая, что все кортежи принадлежат отношению .
  

Очевидно, что .

Кросс-таблицы

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