Модели организации баз данных. Операции над базой данных
Реляционная алгебра базируется на теории множеств и является основой логики работы баз данных.
Когда я только изучал устройство баз данных и SQL, предварительное ознакомление с реляционной алгеброй очень помогло дальнейшим знаниям правильно уложиться в голове, и я постараюсь что бы эта статья произвела подобный эффект.
Так что если вы собираетесь начать свое обучение в этой области или вам просто стало интересно, прошу под кат.
Реляционная база данных
Для начала введем понятие реляцинной базы данных, в которой будем выполнять все действия.
Реляционной базой данных называется совокупность отношений, содержащих всю информацию, которая должна хранится в базе. В данном определении нам интересен термин отношение, но пока оставим его без строго определения.
Лучше представим себе таблицу продуктов.
Таблица PRODUCTS
| ID | NAME | COMPANY | PRICE |
| 123 | Печеньки | ООО ”Темная сторона” | 190 |
| 156 | Чай | ООО ”Темная сторона” | 60 |
| 235 | Ананасы | ОАО ”Фрукты” | 100 |
| 623 | Томаты | ООО ”Овощи” | 130 |
Таблица состоит из 4х строк, строка в таблице является кортежем в реляционной теории. Множество упорядоченных кортежей называется отношением.
Перед тем как дать определение отношения, введем еще один термин - домен. Домены применительно к таблице это столбцы.
Для ясности, теперь введем строгое определение отношения.
Пусть даны N множеств D1,D2, …. Dn (домены), отношением R над этими множествами называется множество упорядоченных N-кортежей вида
Каждый элемент кортежа представляет собой значение одного из атрибутов, соответствующего одному из доменов.
Ключи в отношениях
В отношении требованием является то, что все кортежи должны различаться. Для однозначной идентификации кортежа существует первичный ключ. Первичный ключ это атрибут или набор из минимального числа атрибутов, который однозначно идентифицирует конкретный кортеж и не содержит дополнительных атрибутов.Подразумевается, что все атрибуты в первичном ключе должны быть необходимыми и достаточными для идентификации конкретного кортежа, и исключение любого из атрибутов в ключе сделает его недостаточным для идентификации.
Например, в такой таблице ключом будет сочетание атрибутов из первого и второго столбца.
Таблица DRIVERS
Видно, что в организации может быть несколько водителей, и чтобы однозначно идентифицировать водителя необходимо и значение из столбца “Название организации” и из “Имя водителя”. Такой ключ называется составным.
В реляционной БД таблицы взаимосвязаны и соотносятся друг с другом как главные и подчиненные. Связь главной и подчиненнной таблицы осуществляется через первичный ключ (primary key) главной таблицы и внешний ключ (foreign key) подчиненной таблицы.
Внешний ключ это атрибут или набор атрибутов, который в главной таблице является первичным ключем.
Этой подготовительной теории будет достаточно для знакомства с основными операциями реляционной алгебры.
Операции реляционной алгебры
Основные восемь операций реляционной алгебры были предложены Э.Коддом .- Объединение
- Пересечение
- Вычитание
- Декартово произведение
- Выборка
- Проекция
- Соединение
- Деление
Для понимания важно запомнить, что результатом любой операции алгебры над отношениями является еще одно отношение, которое можно потом так же использовать в других операциях.
Создадим еще одну таблицу, которая нам пригодится в примерах.
Таблица SELLERS
| ID | SELLER |
| 123 | OOO “Дарт” |
| 156 | ОАО ”Ведро” |
| 235 | ЗАО “Овоще База” |
| 623 | ОАО ”Фирма” |
Условимся, что в этой таблице ID это внешний ключ, связанный с первичным ключом таблицы PRODUCTS.
Для начала рассмотрим самую простую операцию - имя отношения. Её результатом будет такое же отношение, то есть выполнив операцию PRODUCTS, мы получим копию отношения PRODUCTS.
Проекция
Проекция является операцией, при которой из отношения выделяются атрибуты только из указанных доменов, то есть из таблицы выбираются только нужные столбцы, при этом, если получится несколько одинаковых кортежей, то в результирующем отношении остается только по одному экземпляру подобного кортежа.Для примера сделаем проекцию на таблице PRODUCTS выбрав из нее ID и PRICE.
Синтаксис операции:
π
(ID, PRICE) PRODUCTS
В условии выборки мы можем использовать любое логическое выражение. Сделаем еще одну выборку с ценой больше 90 и ID товара меньше 300:
σ (PRICE>90 ^ ID<300) PRODUCTS
Умножение
Умножение или декартово произведение является операцией, производимой над двумя отношениями, в результате которой мы получаем отношение со всеми доменами из двух начальных отношений. Кортежи в этих доменах будут представлять из себя все возможные сочетания кортежей из начальных отношений. На примере будет понятнее.Получим декартово произведения таблиц PRODUCTS и SELLERS.
Синтаксис операции:
PRODUCTS × SELLERS
Можно заметить, что у двух этих таблиц есть одинаковый домен ID. В подобной ситуации домены с одинаковыми названиями получают префикс в виде названия соответствующего отношения, как показано ниже.
Для краткости перемножим не полные отношения, а выборки с условием ID<235
(цветом выделены одни и те же кортежи)
| PRODUCTS.ID | NAME | COMPANY | PRICE | SELLERS.ID | SELLER |
| 123 | Печеньки | ООО ”Темная сторона” | 190 | 123 | OOO “Дарт” |
| 156 | Чай | ООО ”Темная сторона” | 60 | 156 | ОАО ”Ведро” |
| 123 | Печеньки | ООО ”Темная сторона” | 190 | 156 | ОАО ”Ведро” |
| 156 | Чай | ООО ”Темная сторона” | 60 | 123 | OOO “Дарт” |
Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90. Без произведения необходимо было бы сначала получить ID продуктов из первой таблицы, потом по этим ID из второй таблицы получить нужные имена SELLER, а с использованием произведения будет такой запрос:
π (SELLER) σ (RODUCTS.ID=SELLERS.ID ^ PRICE<90) PRODUCTS × SELLERS
В результате этой операции получим отношение:
| SELLER |
| ОАО ”Ведро” |
Соединение и естественное соединение
Операция соединения обратна операции проекции и создает новое отношение из двух уже существующих. Новое отношение получается конкатенацией кортежей первого и второго отношений, при этом конкатенации подвергаются отношения, в которых совпадают значения заданных атрибутов. В частности, если соединить отношения PRODUCTS и SELLERS, этими атрибутами будут атрибуты доменов ID.Также для понятности можно представить соеднинение как результат двух операций. Сначала берется произведение исходных таблиц, а потом из полученного отношения мы делаем выборку с условием равенства атрибутов из одинаковых доменов. В данном случае условием явлется равенство PRODUCTS.ID и SELLERS.ID.
Попробуем соединить отношения PRODUCTS и SELLERS и получим отношение.
| PRODUCTS.ID | NAME | COMPANY | PRICE | SELLERS.ID | SELLER |
| 123 | Печеньки | ООО ”Темная сторона” | 190 | 123 | OOO “Дарт” |
| 156 | Чай | ООО ”Темная сторона” | 60 | 156 | ОАО ”Ведро” |
| 235 | Ананасы | ОАО ”Фрукты” | 100 | 235 | ЗАО “Овоще База” |
| 623 | Томаты | ООО ”Овощи” | 130 | 623 | ОАО ”Фирма” |
Натуральное соединение получает схожее отношение, но в случае, если у нас корректно настроена схема в базе (в данном случае первичный ключ таблицы PRODUCTS ID связан с внешним ключем таблицы SELLERS ID), то в результирующем отношении остается один домен ID.
Синтаксис операции:
PRODUCTS ⋈ SELLERS;
Получится такое отношение:
| PRODUCTS.ID | NAME | COMPANY | PRICE | SELLER |
| 123 | Печеньки | ООО ”Темная сторона” | 190 | OOO “Дарт” |
| 156 | Чай | ООО ”Темная сторона” | 60 | ОАО ”Ведро” |
| 235 | Ананасы | ОАО ”Фрукты” | 100 | ЗАО “Овоще База” |
| 623 | Томаты | ООО ”Овощи” | 130 | ОАО ”Фирма” |
Пересечение и вычитание.
Результатом операции пересечения будет отношение, состоящее из кортежей, полностью входящих в состав обоих отношений.Результатом вычитания будет отношение, состоящее из кортежей, которые являются кортежами первого отношения и не являются кортежами второго отношения.
Данные операции аналогичны таким же операциям над множествам, так что, я думаю, нет необходимости подробно их расписывать.
Источники информации
- Основы использования и проектирования баз данных - В. М. Илюшечкин
- курс лекций Introduction to Databases - Jennifer Widom, Stanford University
Буду благодарен за аргументированные замечания
Начинать изучать SQL лучше всего с азов реляционных баз данных. Я дам пояснение что такое реляционная база данных, что такое отношение и какие операции над ними можно производить.
Поехали …
Что такое SQL?
SQL (Structured Query Language)
– структурированный язык запросов, универсальный компьютерный язык, применяемый для создания, модификации и управление данными в реляционных базах данных
Что такое реляционная база данных?
Это совокупность взаимосвязанных данных хранящихся в виде отношений
Что такое отношения?
Отношение это некое множество картежей
Что такое кортеж?
Картеж это определенный набор элементов, причем каждый элемент набора принадлежит некоторому множеству (можно сказать типу элемента). Если говорить проще, то кортеж это список элементов, между которыми есть связь или как говорят, есть отношение . Представить кортеж можно с помощью графа или таблицы состоящий из одной строки.
Продемонстрирую кортеж из двух элементов с помощью графа:
Вершины графа это элементы их некоторого множества, в данном случае, это элемент а1 из множества А и элемент b1 из множества B . Ребро между вершинами обозначает связь между элементами или как говорят элемент а1 находится в отношение с b1 .
Продемонстрирую этот же кортеж с помощью таблицы:
Номер 1 у а1 и b1 , был выбран произвольно.
Итак, мы добрались до элементарного кирпичика, т.е. до кортежа , начнем разматывать нашу логику обратно, что бы понять, что такое реляционная база данных и SQL .
Как я сказал, отношение это множество кортежей , причем ограниченное (если отойти от теории). Представить отношения можно в виде матрицы, графа, таблицы.
Продемонстрирую, как представить отношение в виде графа:
На графике видно, что есть несколько кортежей, причем какой кортеж первый, а какой второй и третий не важно , это просто множество кортежей. В множестве нет такого понятия «первый», «второй» и «третий», это всё сразу и очередность не важна.
Продемонстрирую, как представить отношение в виде таблицы:
Последовательность строк или кортежей в таблице не важна , из графа я их взял в произвольном порядке.
Также важно заметить, что последовательность столбцов тоже не важна , если мы поменяем их местами, то с точки зрения теории множеств, отношение останется не низменным . В этом как раз и заключается отрицательная сторона таблицы, как способа визуализации отношения, ведь нам психологически трудно будет назвать таблицы равными, если у них в разной последовательности следуют столбы и строки.
Как было сказано в самом начале, что реляционная база данных это совокупность взаимосвязанных данных хранящихся в виде отношений . Если представлять отношения в виде таблиц, то реляционная БД это некий набор взаимосвязанных таблиц . Выходит SQL это язык создания, модификации и управление таблицами в реляционной БД .
Итак, с логической цепочкой мы разобрались: SQL, реляционная БД, отношения, кортеж..Теперь мы затронем язык SQL, т.е. тему манипулирования с отношениями, важно разобраться какие операции мы можем проводить над отношениями .
Все операции продемонстрировать не возможно, в связи с их большим количеством, приведу только базовые:
1. Селекция (другие имена операции — выборка, ограничение)
Операция «селекция» или «выборка» выполняется над одним отношением , смысл его заключается в том, что по заданному условию осуществляется выборка подмножества кортежей . Результат операции – отношение отличающиеся от исходного меньшим числом кортежей . Пример:
Пусть есть отношение, назовем его «исходная таблица №1»:
Результат «выборки» из исходной таблицу №1, при условии что А=а3
На языке SQL:
синтаксис — SELECT * FROM имя_таблицы WHERE имя_столбца=значение
SELECT * FROM исходная_таблица WHERE А=a3
2. Проекция
Операция «проекция» выполняется над одним отношением , в результате неё формируется новое отношение с указанными столбцами таблицы .
Например, есть отношение, назовем ее «исходная таблица №2»:
Произведем над данным отношением операцию «проекция» по атрибутам А и С , результат:
В результате мы получили два одинаковых картежа, в отношение такого быть не может, поэтому сократим их (в СУБД сокращения происходят автоматически):
Выходит, при проекции у нас может сокращаться число кортежей , это бывает, за ошибку это считать не надо .
На языке SQL:
синтаксис — SELECT список_столбцов FROM имя_таблицы
реализация для данного случая — SELECT А,С FROM исходная_таблица_№2
3. Естественное соединение
Операция «естественное соединение » выполняется над двумя логическими связанными отношениями , в результате неё формируется новое отношение со столбцами первого и второго отношения и с кортежами, которые получаются в результате соединения каждого кортежа первого и второго отношения . На примере должно быть более понятно, пусть есть два отношения, назовем их исходная таблица №3.1 и исходная таблица №3.2:
Исходная таблица №3_1
Исходная таблица №3_2
Проведем операцию «соединения» первого и второго отношения, результат:
Интересно заметить, что мы получили исходное отношение из раздела «2. Проекция», последовательность столбцов в отношение значения не имеет.
На языке SQL:
реализация для данного случая — SELECT исходная_таблица_№3_1.*, исходная таблица №3_2.В FROM исходная_таблица_№3_1, исходная таблица №3_2 WHERE исходная таблица №3_1.A= исходная таблица №3_2.A
4. Объединение
Операция «объединение» выполняется над двумя отношениями имеющих одинаковый набор столбцов и тип данных в этих столбцах , результат операции новое отношение, которое включает в себя все кортежи «первого» и «второго» отношения (повторяющиеся сокращаются).
Исходная таблица №4_1
Исходная таблица №4_2
Произведем операцию «объединения» отношения №4.1 и отношения №4.2 , результат:
На языке SQL:
синтаксис — SELECT список_столбцов_таблицы1 FROM таблица1 UNION SELECT список_столбцов_таблицы2 FROM таблица2
реализация для данного случая — SELECT А,В FROM исходная_таблица_№4_1 UNION SELECT А,В FROM исходная_таблица_№4_2
5. Пересечение
Операция «пересечение» выполняется , результат операции новое отношение, которое включает в себя одинаковые кортежи «первого» и «второго» отношения .
Пример, пусть есть два отношения:
Исходная таблица №5_1
Исходная таблица №5_2
Произведем операцию «пересечения» с данными отношениями, результат:
Т.е. в результирующее отношение, попали повторяющиеся кортежи из «первого» и «второго» отношения.
На языке SQL:
синтаксис — SELECT одна_из_таблиц.столбец1, одна_из_таблиц.столбец2, … FROM таблица1,таблица2 WHERE таблица1.столбец1=таблица2.столбец1 AND таблица1.столбец2= таблица2.столбец2 AND …
реализация для данного случая –
SELECT исходная_таблица_№5_1.А, исходная_таблица_№5_1.В FROM исходная_таблица_№5_1, исходная_таблица_№5_2 WHERE исходная_таблица_№5_1.А = исходная_таблица_№5_2.А AND исходная_таблица_№5_1.В = исходная_таблица_№5_2.В
6. Вычитание (разность)
Операция «вычитание» выполняется над двумя отношениями имеющими одинаковый набор столбцов и тип данных в этих столбцах , результат операции новое отношение, которое включает в себя кортежи «первого» отношения отличные от кортежей «второго» отношения , на примере думаю должно быть более понятно.
Пример, пусть есть два отношения:
Исходная таблица №6_1
Исходная таблица №6_2
Произведем операцию «разность» , т.е. от исходной таблицы №6_1 отнимем исходную таблицу №6_2, результат:
Т.е. результирующее отношение, это «первое» отношение без повторяющихся кортежей «второго» отношения.
На языке SQL:
реализация для данного случая – SELECT исходная_таблица_№6_1.А, исходная_таблица_№6_1.В FROM исходная_таблица_№6_1 WHERE NOT EXISTS (SELECT исходная_таблица_№6_2.А, исходная_таблица_№6_2.В FROM исходная_таблица_№6_2
WHERE исходная_таблица_№6_2.А= исходная_таблица_№6_1.А AND исходная_таблица_№6_2.В= исходная_таблица_№6_1.В)
7. Декартово произведение
Декартово произведение выполняется над двумя произвольными отношениями, результат операции новое отношение с количество столбцов равному сумме количества столбцов «первого» и «второго» отношения, а количество строк равному произведение количеству строк «первого» и «второго» отношения . Кортежи результирующего отношение, если говорить по-простому, получаются путем комбинации каждого кортежа «первого» отношения с кортежами «второго» отношения.
Пример, пусть есть два произвольных отношения:
Исходная таблица №7_1
Исходная таблица №7_2
Произведем «декартово произведение» данных двух отношений, результат:
На языке SQL:
реализация для данного случая – SELECT исходная_таблица_№7_1.А, исходная_таблица_№7_1.В, исходная_таблица_№7_2.А, исходная_таблица_№7_2.В FROM исходная_таблица_№7_1, исходная_таблица_№7_2
Мы разобрались с основными операции над отношениями и напоследок теоретической части поста разберемся что такое ключ.
Что такое ключ?
Ключ – это один или не сколько столбцов таблицы , которые однозначно определяют запись (строку) . Пример, пусть есть отношение представленное в виде таблицы:
Ключом данного отношения может быть столбец А . Т.к. значения только данного столбца в отношение , например: а3 определяет запись «а3 b1 d3» , a2 определят запись «a2 b2 d3» , a1 определяет запись «a1 b2 d1» . Другие столбцы данную функцию нести не могут.
Если ключ состоит из одного столбца , то его называют простым , если из нескольких его называют составным . В данной таблице, помимо простого ключа, есть еще один – составной, состоящий из столбцов B и D . Значения этих столбцов однозначной определят запись (строки), пример: b1 и d3 однозначно определяет запись «a3 b1 d3» , b2 и d3 однозначной определяет запись «a2 b2 d3» , b2 и d1 однозначно определяет запись «a1 b2 d1» .
На практике обычно выбирают один ключ , причем самый простой , в данном случае это столбец А . Такой ключ также называют «первичный ключ ».
Вам будет интересно:
Реляционная алгебра - это язык операций, выполняемых над отношениями - таблицами реляционной базы данных. Операции реляционной алгебры позволяют на основе одного или нескольких отношений создавать другое отношение без изменения самих исходных отношений. Полученное другое отношение обычно не записывается в базу данных, а существует в результате выполнения SQL-запроса - массиве, создаваемом функциями для работы с базами данных в языках программирования. Для каждой операции реляционной алгебры будет дана её реализация в виде запросов на языке SQL.
Рассмотрим операции реляционной алгебры. Чтобы Вам не отвлекаться на содержание таблиц не Ваших баз данных, таких как "Продукты", "Водители", "сливы", "груши", "чай", "кофе", Владимиры, Сергеи и т.п. будем выполнять операции над отношениями (таблицами) с абстрактными данными, такими как R1, R2 (названия таблиц - отношений) и т.д. и А1, А2, А3 (названия атрибутов - столбцов) и h15, w11 и т.п. (содержание записей таблиц базы данных).
Приоритеты выполнения операций реляционной алгебры (в порядке убывания пунктов списка, а в одном пункте - операции с равными приоритетами):
- селекция, проекция
- декартово произведение, соединение, пересечение, деление
- объединение, разность.
Операция выборки
Операция выборки работает с одним отношением и определяет результирующее отношение R , которое содержит только те кортежи (или строки, или записи), отношения , которые удовлетворяют заданному условию (предикату P ).
Таким образом, операция выборки - унарная операция - и записывается следующим образом:
где P - предикат (логическое условие).
Запрос SQL
Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. В таблице ниже дано одно отношение, с которым работает эта операция.
| R3 | |||
| A1 | A2 | A3 | A4 |
| 3 | hh | yl | ms |
| 4 | pp | a1 | sr |
| 1 | rr | yl | ms |
Просматриваем столбец А3 и устанавливаем, что предикату A3>"d0" удовлетворяют записи в первой и третьей строках исходного отношения (так как номер буквы y в алфавите больше номера буквы d). В результате получаем следующее новое отношение, в котором две строки:
| R | |||
| A1 | A2 | A3 | A4 |
| 3 | hh | yl | ms |
| 1 | rr | yl | ms |
Комбинировать всевозможные логические условия для выборок Вам поможет материал "Булева алгебра (алгебра логики)" .
Запрос SQL
SELECT A1, A2, A3 from R1 UNION SELECT A1, A2, A3 from R2
Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Теперь даны два отношения, так как операция объединения - бинарная операция:
| R1 | R2 | |||||
| A1 | A2 | A3 | A1 | A2 | A3 | |
| Z7 | aa | w11 | X8 | pp | k21 | |
| B7 | hh | h15 | Q2 | ee | h15 | |
| X8 | pp | w11 | X8 | pp | w11 | |
Объединяем строки первого и второго отношения и видим, что третья строка, которая является третьей и в первом, и во втором отношении - идентичны, поэтому её включаем в новое отношение только один раз. Получаем следующее отношение:
| R | ||
| A1 | A2 | A3 |
| Z7 | aa | w11 |
| B7 | hh | h15 |
| X8 | pp | w11 |
| X8 | pp | k21 |
| Q2 | ee | h15 |
Важно следующее: операция объединения может быть выполнена только тогда, когда два отношения обладают одинаковым числом и названиями атрибутов (столбцов), или, говоря формально, совместимы по объединению.
Операция пересечения
Результатом пересечения двух множеств (отношений) А и В () будет такое множество (отношение) С, которое включает в себя те и только те элементы, которые есть и во множестве А, и во множестве В. Операция пересечения реляционной алгебры идентична операции .
Запрос SQL
SELECT A1, A2, A3 from R1 INTERSECT SELECT A1, A2, A3 from R2
В некоторых диалектах SQL отсутствует ключевое слово INTERSECT. Его заменой, например, в MySQL и других, является INNER JOIN. О том, как работает оператор SQL JOIN вообще и его разновидности INNER JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN и FULL OUTER JOIN - на уроке SQL JOIN - соединение таблиц базы данных .
Запрос MySQL
Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:
| R1 | R2 | |||||
| A1 | A2 | A3 | A1 | A2 | A3 | |
| Z7 | aa | w11 | X8 | pp | k21 | |
| B7 | hh | h15 | Q2 | ee | h15 | |
| X8 | pp | w11 | X8 | pp | w11 | |
Просматриваем все записи в двух отношениях, и обнаруживаем, что и в первом, и во втором отношении есть одна строка - та, которая является третьей и в первом, и во втором отношении. Получаем новое отношение:
| R | ||
| A1 | A2 | A3 |
| X8 | pp | w11 |
Операция разности
Разность двух отношений R1 и R2 () состоит из кортежей (или записей, или строк), которые имеются в отношении R1, но отсутствуют в отношении R2. Отношения R1 и R2 должны быть совместимы по объединению. Операция разности реляционной алгебры идентична операции .
Запрос SQL
SELECT
A1, A2, A3 from R2 EXCEPT
SELECT
A1, A2, A3 from R1
Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:
| R1 | R2 | |||||
| A1 | A2 | A3 | A1 | A2 | A3 | |
| Z7 | aa | w11 | X8 | pp | k21 | |
| B7 | hh | h15 | Q2 | ee | h15 | |
| X8 | pp | w11 | X8 | pp | w11 | |
Из отношения R2 исключаем строку, которая есть также в отношении R2 - третью - и получаем новое отношение:
| R | ||
| A1 | A2 | A3 |
| X8 | pp | w11 |
| Q2 | ee | h15 |
Операция декартова произведения
Операция декартова произведения () определяет новое отношение R, которое является результатом конкатенации каждого кортежа отношения R1 с каждым кортежем отношения R2.
Запрос SQL
SELECT * from R3, R4
Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R3 и R4:
| R3 | R4 | |||||
| A1 | A2 | A3 | A4 | A5 | A6 | |
| 3 | hh | yl | ms | 3 | hh | |
| 4 | pp | a1 | sr | 4 | pp | |
| 1 | rr | yl | ms | |||
В новом отношении должны присутствовать все атрибуты (столбцы) двух отношений. Сначала первая строка отношения R3 сцепляется с каждой из двух строк отношения R4, затем вторая строка отношения R3, затем третья. В результате должно получиться 3 Х 2 = 6 кортежей (строк). Получаем такое новое отношение:
| R | |||||
| A1 | A2 | A3 | A4 | A5 | A6 |
| 3 | hh | yl | ms | 3 | hh |
| 3 | hh | yl | ms | 4 | pp |
| 4 | pp | a1 | sr | 3 | hh |
| 4 | pp | a1 | sr | 4 | pp |
| 1 | rr | yl | ms | 3 | hh |
| 1 | rr | yl | ms | 4 | pp |
Операции над базой данных
Стандартным способом доступа к данным базы является вход по ассоциативному адресу {образцу), осуществляемый операцией "поиск по образцу". Аргумент операции "поиск по образцу" представляет собой структуру, характер которой может меняться в достаточно широком диапазоне в зависимости от функций, выполняемых базой данных. Результатом этой операции является множество (возможно, пустое - негативный результат) всех референтов образца-аргумента, т.е. фрагментов базы данных, каждый из которых представляет собой ответ на запрос, специфицированный в форме этого образца.
Можно выделить несколько типов образцов.
Простой образец - это фрагмент структуры того же типа, что и каркас. В вершинах простого образца компоненты могут указываться частично, например, только имя или только тип. Характер процедуры, реализуемой операцией "поиск по образцу", может быть двух видов:
Точное совпадение - референты изоморфны образцу с точностью до отсутствующих элементов в образце;
Покрытие - может выполняться в тех случаях, когда задается частичный порядок над символами, выступающими в качестве элементов образца. Референтами в этом случае являются фрагменты каркаса, покрываемые образцом, в том смысле, что графы образца и референта изоморфны, а элементы образца либо совпадают с соответствующим символом референта, либо находятся выше его по иерархии.
Разрывный образец - это совокупность простых образцов, связанных дугами специального вида, отсутствующими в каркасе. В этом случае графы образца и референта не являются изоморфными, поскольку в последнем отсутствуют специальные дуги. Можно сказать, что при разрывном образце поиск происходит не на самом каркасе, а на его транзитивном замыкании по одному или нескольким типам отношений. В. Образец с отрицательным контекстом представляет собой пару
< положительный образец, отрицательный образец >,
в которой каждый из образцов простой или разрывный. Процедура поиска для такого образца определяется следующим образом. Выполняется поиск по положительному образцу, найденному референту R определяются имена вершин, общих для положительного и отрицательного образцов. Эти имена подставляются на соответствующие позиции в отрицательный образец, по которому вновь осуществляется поиск. Если множество референтов в этом случае пусто, то R принимается в качестве референта поиска по образцу с отрицательным контекстом. В противном случае поиск не выдает результат.
Отсутствие связи между положительным и отрицательным образцами представляет собой частный случай описанной выше процедуры, при которой поиск по обоим образцам осуществляется независимо, а общий результат определяется так же.
Сложный образец - представляет собой совокупность видов образцов, перечисленных выше. Результатом поиска по сложному образцу является сочетание процедур поиска по каждому из образцов совокупности.
Будем делить операцию "поиск по образцу" на два основных вида: одновариантный и многовариантный поиск.
В случае одновариантного поиска в базе данных отыскивается единственный (первый подходящий) референт, в то время как при многовариантном поиске процесс продолжается до тех пор, пока не будут найдены все возможные фрагменты базы данных, которые могут быть референтами для данного образца.
Одним из существенных факторов, определяющих результат операции "поиск по образцу" при одновариантном поиске, является то, фиксируется или нет порядок сканирования каркаса при выполнении операции "поиск по образцу". Например, при каркасе-цепочке это может быть просмотр слева направо или справа налево, при дереве - от корня к листьям или в обратном направлении. В тех случаях, когда порядок просмотра является внешней характеристикой базы данных, он может быть фиксированным (встроенным) или изменяемым в процессе работы (настраиваемым).
Еще одной операцией над базой данных является добавление. Смысл этой операции - присоединение новых данных к данным, находящимся в базе. Аргумент этой операции состоит из двух частей: первая представляет собой тот фрагмент, который присоединяется к базе данных, и имеет ту же организацию, т.е. состоит из каркаса и набора компонент, сопоставленных его вершинам; вторая часть является, в общем случае, ассоциативным адресом, указывающим, к каким вершинам каркаса будет присоединяться новый фрагмент.
Связь между записью-владельцем и записью-членом также имеет вид 1:N.Основное различие этих моделей состоит в том, что в сетевой модели запись может быть членом более чем одного группового отношения. Согласно этой модели каждое групповое отношение именуется и проводится различие между его типом и экземпляром. Тип группового отношения задается его именем и определяет свойства общие для всех экземпляров данного типа. Экземпляр группового отношения представляется записью-владельцем и множеством (возможно пустым) подчиненных записей. При этом имеется следующее ограничение: экземпляр записи не может быть членом двух экземпляров групповых отношений одного типа (т.е. сотрудник из примера в п..1, например, не может работать в двух отделах).
- деревья (a) и (b), показанные на рис. 4.2 , заменяются одной сетевой структурой, в которой запись СОТРУДНИК входит в два групповых отношения;
- для отображения типа M:N вводится запись СОТРУДНИК_КОНТРАКТ, которая не имеет полей и служит только для связи записей КОНТРАКТ и СОТРУДНИК, (см. рис. 4.3). Отметим, что в этой записи может храниться и полезная информация, например, доля данного сотрудника в общем вознаграждении по данному контракту.
Рис.
4.3.
Каждый экземпляр группового отношения характеризуется следующими признаками:
Способ упорядочения подчиненных записей:
- произвольный,
- хронологический /очередь/,
- обратный хронологический /стек/,
- сортированный.
Если запись объявлена подчиненной в нескольких групповых отношениях, то в каждом из них может быть назначен свой способ упорядочивания.
Режим включения подчиненных записей:
- автоматический - невозможно занести в БД запись без того, чтобы она была сразу же закреплена за неким владельцем;
- ручной - позволяет запомнить в БД подчиненную запись и не включать ее немедленно в экземпляр группового отношения. Эта операция позже инициируется пользователем.
Режим исключения.
Принято выделять три класса членства подчиненных записей в групповых отношениях:
- Фиксированное. Подчиненная запись жестко связана с записью владельцем и ее можно исключить из группового отношения только удалив. При удалении записи -владельца все подчиненные записи автоматически тоже удаляются. В рассмотренном выше примере фиксированное членство предполагает групповое отношение "ЗАКЛЮЧАЕТ" между записями "КОНТРАКТ" и "ЗАКАЗЧИК", поскольку контракт не может существовать без заказчика.
- Обязательное. Допускается переключение подчиненной записи на другого владельца, но невозможно ее существование без владельца. Для удаления записи-владельца необходимо, чтобы она не имела подчиненных записей с обязательным членством. Таким отношением связаны записи "СОТРУДНИК" и "ОТДЕЛ". Если отдел расформировывается, все его сотрудники должны быть либо переведены в другие отделы, либо уволены.
- Необязательное. Можно исключить запись из группового отношения, но сохранить ее в базе данных не прикрепляя к другому владельцу. При удалении записи -владельца ее подчиненные записи - необязательные члены сохраняются в базе, не участвуя более в групповом отношении такого типа. Примером такого группового отношения может служить "ВЫПОЛНЯЕТ" между "СОТРУДНИКИ" и "КОНТРАКТ", поскольку в организации могут существовать работники, чья деятельность не связана с выполнением каких-либо договорных обязательств перед заказчиками.
Операции над данными в сетевой модели БД
| Добавить | - внести запись в БД и, в зависимости от режима включения, либо включить ее в групповое отношение, где она объявлена подчиненной, либо не включать ни в какое групповое отношение. |
| Включить в групповое отношение | - связать существующую подчиненную запись с записью-владельцем. |
| Переключить | - связать существующую подчиненную запись с другой записью-владельцем в том же групповом отношении. |
| Обновить | - изменить значение элементов предварительно извлеченной записи. |
| Извлечь | - извлечь записи последовательно по значению ключа, а также используя групповые отношения - от владельца можно перейти к записям - членам, а от подчиненной записи к владельцу набора. |
| Удалить | - убрать из БД запись. Если эта запись является владельцем группового отношения, то анализируется класс членства подчиненных записей. Обязательные члены должны быть предварительно исключены из группового отношения, фиксированные удалены вместе с владельцем, необязательные останутся в БД. |
| Исключить из группового отношения | - разорвать связь между записью-владельцем и записью-членом. |
Ограничения целостности
Как и в иерархической модели обеспечивается только поддержание целостности по ссылкам (владелец отношения - член отношения).
Достоинства и недостатки ранних СУБД
Достоинства ранних СУБД:
- развитые средства управления данными во внешней памяти на низком уровне;
- возможность построения вручную эффективных прикладных систем;
- возможность экономии памяти за счет разделения подобъектов (в сетевых системах)
Недостатки ранних СУБД:
- сложность использования;
- высокий уровень требований к знаниям о физической организации БД;
- зависимость прикладных систем от физической организации БД;
- перегруженность логики прикладных систем деталями организации доступа к БД.
Как иерархическая, так и сетевая модель данных предполагает наличие высококвалифицированных программистов. И даже в таких случаях реализация пользовательских запросов часто затягивается на длительный срок.
Объектно-ориентированные СУБД
Появление объектно-ориентированных СУБД вызвано потребностями программистов на ОО-языках, которым были необходимы средства для хранения объектов, не помещавшихся в оперативной памяти компьютера. Также важна была задача сохранения состояния объектов между повторными запусками прикладной программы. Поэтому, большинство ООСУБД представляют собой библиотеку, процедуры управления данными которой включаются в прикладную программу. Примеры реализации ООСУБД как выделеного сервера базы данных крайне редки.
Сразу же необходимо заметить, что общепринятого определения " объектно-ориентированной модели данных " не существует. Сейчас можно говорить лишь о неком "объектном" подходе к логическому представлению данных и о различных объектно-ориентированных способах его реализации.
Мы знаем, что любая модель данных должна включать три аспекта: структурный, целостный и манипуляционный. Посмотрим, как они реализуются на основе объектно-ориентированная парадигмы программирования .
Структура
Структура объектной модели описывается с помощью трех ключевых понятий:
| инкапсуляция | - каждый объект обладает некоторым внутренним состоянием (хранит внутри себя запись данных), а также набором методов - процедур, с помощью которых (и только таким образом) можно получить доступ к данным, определяющим внутреннее состояние объекта, или изменить их. Таким образом, объекты можно рассматривать как самостоятельные сущности, отделенные от внешнего мира; |
| наследование | - подразумевает возможность создавать из классов объектов новые классы объекты, которые наследуют структуру и методы своих предков, добавляя к ним черты, отражающие их собственную индивидуальность. Наследование может быть простым (один предок) и множественным (несколько предков); |
| полиморфизм | - различные объекты могут по разному реагировать на одинаковые внешние события в зависимости от того, как реализованы их методы. |
Целостность данных
Для поддержания целостности объектно-ориентированный подход предлагает использовать следующие средства:
- автоматическое поддержание отношений наследования возможность объявить некоторые поля данных и методы объекта как "скрытые", не видимые для других объектов; такие поля и методы используются только методами самого объекта создание процедур контроля целостности внутри объекта
Средства манипулирования данными
К сожалению, в объектно-ориентированном программировании отсутствуют общие средства манипулирования данными, такие как реляционная алгебра или реляционное счисление. Работа с данными ведется с помощью одного из объектно-ориентированных языков программирования общего назначения, обычно это SmallTalk, C++ или Java.
Подведем теперь некоторые итоги
В объектно-ориентированных базах данных, в отличие от реляционных, хранятся не записи, а объекты. ОО-подход представляет более совершенные средства для отображения реального мира, чем реляционная модель, естественное представление данных. В реляционной модели все отношения принадлежат одному уровню, именно это осложняет преобразование иерархических связей модели "сущность-связь" в реляционную модель. ОО - модель можно рассматривать послойно, на разных уровнях абстракции. Имеется возможность определения новых типов данных и операций с ними.
В то же время, ОО - модели присущ и ряд недостатков :
- отсутствуют мощные непроцедурные средства извлечения объектов из базы. Все запросы приходится писать на процедурных языках, проблема их оптимизации возлагается на программиста;
- вместо чисто декларативных ограничений целостности (типа явного объявления первичных и внешних ключей реляционных таблиц с помощью ключевых слов PRIMARY KEY и REFERENCES ) или полудекларативных триггеров для обеспечения внутренней целостности приходится писать процедурный код.
Очевидно, что оба эти недостатка связаны с отсутствием развитых средств манипулирования данными. Эта задача решается двумя способами - расширение ОО-языков в сторону управления данными (стандарт ODMG), либо добавление объектных свойств в реляционные СУБД (SQL-3, а также так называемые объектно-реляционных СУБД).
Статьи по теме
