30047

Древовидные (иерархические) структуры данных в реляционных базах данных

Курсовая

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

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

Русский

2013-08-22

1006.5 KB

25 чел.

Древовидные (иерархические) структуры данных в реляционных базах данных

Кузьменко Дмитрий, iBase.ru

Введение

замечание: документ был написан в 1997 г. С тех пор мало что изменилось в описываемой области. 

Сегодня большинство хранилищ данных, как простых так и сложных, построены на основе реляционных баз данных. В них используются либо файл-серверные системы (dBase, Paradox, Clipper, FoxPro, Access), либо SQL-серверы (Oracle, Informix, Sybase, Borland InterBase, MS SQL и т.д.). Реляционные базы данных в большинстве случаев удовлетворяют требования какой-либо предметной области данных, но часты и случаи когда требуется представление и хранение данных в иерархическом виде. Варианты построения таких представлений в реляционной модели и будут рассмотрены в данной статье.

Используемые инструменты

В качестве инструмента разработки клиентского приложения в данной статье применяется Delphi, а в качестве SQL-сервера – Borland InterBase SQL Server 4.x. На самом деле для теоретической части статьи это несущественно, а практическая часть содержит минимум специфики использования указанных инструментов.

Таблицы-объекты

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


Рис. 1

Таблица имеет структуру, т.е. состоит из полей, описывающих характеристики некоего объекта, например "Человек". Записи такой таблицы (можно назвать ее "Люди") представляют собой характеристики экземпляров объектов одного и того-же типа. Идентификатор позволяет найти среди множества экземпляров один экземпляр требуемого типа.

Однотипные связанные объекты

Предположим что мы действительно хотим создать таблицу "Люди", в которой нужно отслеживать родственные связи типа родитель-потомок. Для простоты представим себе что у потомков родитель может быть только один (например "Родитель"):


Рис. 2

Для того, чтобы хранить информацию о родителе экземпляра объекта, любой объект в таблице должен помимо идентификатора иметь атрибут "родитель". На рисунке видно, что все "Потомки" имеют родителя, кроме самого "Родитель1". Экземпляр "Родитель1" может в принципе вообще отсутствовать – можно принять что у потомков первого уровня всегда один и тот-же родитель, поэтому хранить информацию о нем необязательно (в каких случаях это необходимо мы рассмотрим дальше).

Читатель может заметить - а как же множественное наследование? А никак. В природе такового не существует - все объекты реального мира являются или цельными, или составными. Множественное наследование было создано только как методика проектирования классов, когда разработчик не обладает полной информацией о самих классах. Автор статьи считает, что множественное наследование только запутывает реализацию прикладной области. Например, в ряде книг приводится случай, когда объект "тесто" получается множественным наследованием объектов "вода" и "мука". На самом деле это не так - даже при диффузии отдельные материалы все равно остаются сами собой, т.е. в данном случае мы имеем совершенно новый объект "тесто", который имеет среди атрибутов указатели на два класса - "тесто" и "вода" (или список составляющих "тесто" классов, как угодно). Характеристики "теста" при этом зависят не только от состава "воды" и "муки", но и от их процентного соотношения.
То же самое относится и к биологическому "рождению" - ребенок наследует свойства родителей, т.е. их наборы хромосом, и представляет собой типичный составной объект при отсутствии какого бы то ни было множественного наследования.
Конечно, множественное наследование в редких случаях облегчает программирование, однако это не значит что оно отражает суть реальных вещей, которые можно описать в программе.
 

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


Рис. 3

Поле "Родитель" всегда ссылается на значение поля "Идентификатор". Здесь нас поджидает подводный камень – если-бы мы решили что "…ссылается на существующее значение поля…", и в соответствии с реляционными правилами объявили-бы связь конструкцией SQL "alter table … add constraint … foreign key", то попали-бы в замкнутый круг "курица и яйцо". Как создать экземпляр объекта если родителя нет? Действительно, может-ли существовать экземпляр объекта без указания родителя? Чтобы избавиться на начальном этапе хотя-бы от первого вопроса, нужно отказаться от декларации связи Родитель->Идентификатор на уровне сервера. Это снизит защищенность данных, но избавит нас от долгих раздумий в самом начале пути. На второй вопрос (может-ли существовать экземпляр без родителя) можно безболезненно ответить "нет", установив ограничение целостности для поля "Родитель" как "значение обязательно" (NOT NULL).

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

Давайте теперь посмотрим, как будет выглядеть таблица, заполненная экземплярами объектов с рисунка 2:

Идентификатор

Родитель

Остальные атрибуты …

Родитель1

???

Потомок1

Родитель1

Потомок2

Родитель1

Потомок3

Потомок1

Из таблицы видно, что Потомок1 одновременно является и потомком элемента "Родитель1", и родителем элемента "Потомок3".

Такую таблицу можно создать конструкцией SQL:

CREATE TABLE OBJECTS( 

 ID INTEGER NOT NULL,

 PARENT INTEGER NOT NULL,

 NAME VARCHAR(30),

 constraint PK_OBJECTS primary key (ID)) 

Пусть идентификаторы экземпляров объектов будут начинаться с номера 1. Тогда родителем экземпляра "Родитель1" можно принять значение 0 (корневой элемент). Фактически экземпляров с родителем = 0 может быть сколько угодно, и именно они будут представлять "корень" нашего дерева. Названия экземпляров пусть находятся в поле "NAME". Пронумеруем идентификаторы экземпляров объектов. В этом случае таблица будет иметь вид

ID

PARENT

NAME

1

0

Родитель1

2

1

Потомок1

3

1

Потомок2

4

2

Потомок3

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

SELECT * FROM OBJECTS 

  WHERE PARENT = 0

Ответ на этот запрос будет выглядеть так

1

0

Родитель1

Теперь, для того чтобы получить всех потомков например экземпляра "Родитель1", нужно использовать его ID в том-же самом запросе как идентификатор родителя:

SELECT * FROM OBJECTS 

  WHERE PARENT = 1

Ответ на этот запрос будет выглядеть так

2

1

Потомок1

3

1

Потомок2

Таким образом получить список записей любого уровня можно одним и тем-же запросом:

ВЫБРАТЬ ВСЕ_ПОЛЯ ИЗ ТАБЛИЦЫ 

ГДЕ РОДИТЕЛЬ = ИДЕНТИФИКАТОР 

Представить такую информацию можно в виде "каталогов" и "файлов", например как в Windows Explorer. Щелчок мыши по каталогу приводит к "проваливанию" на более глубокий уровень, и т.д.

Конечно, для того чтобы иметь возможность вернуться назад по дереву нужно в приложении хранить "список возврата", т.е. список элементов, по которым мы углубились внутрь, с идентификаторами их владельцев (своеобразный "стек"). С другой стороны, нужно иметь возможность выбрать весь путь вплоть до корня начиная с произвольного элемента. Это можно сделать написав хранимую процедуру (если ваш SQL-сервер поддерживает стандарт ANSI SQL 3 в части хранимых процедур (PSM) и позволяет из хранимых процедур возвращать наборы записей). Вот как выглядит такая процедура для InterBase

CREATE PROCEDURE GETPARENTS (ID INTEGER) 

RETURNS (DID INTEGER, OID INTEGER, NAME VARCHAR(30))

AS

BEGIN

  WHILE (:ID > 0) DO /* ищем до корня */

    BEGIN

      SELECT O.ID, O.PARENT, O.NAME

      FROM OBJECTS O

      WHERE O.ID = :ID

      INTO :DID, :OID, :NAME;

      ID = :OID; /* код родителя для следующей выборки */

      SUSPEND;

    END

END

В процедуру передается идентификатор, с которого нужно подниматься “вверх” по дереву. В цикле, пока идентификатор не стал равным 0 (не поднялись выше корневого элемента) происходит выборка записи с указанным идентификатором, затем идентификатор меняется на идентификатор родителя.

Выполнение этой процедуры для наших данных привело-бы к следующему результату:

(запрос SELECT * FROM GETPARENTS 4)  

4

3

Потомок3

3

1

Потомок2

1

0

Родитель1

Соединяя поля "NAME" справа налево мы получим полный "путь" от текущего элемента до корня: “Родитель1/Потомок2/Потомок3”. Этот путь можно использовать либо для показа пользователю, либо для внутренних целей приложения.

Визуализация древовидной структуры

Для визуализации подобной структуры можно воспользоваться компонентом, поставляемым в Delphi 2.0 и 3.0, - TTreeView. Этот компонент формирует представление типа "outline" при помощи объектов TTreeNode. К сожалению, с этим типом объекта работать не очень удобно, поскольку он произведен от стандартного элемента GUI и при разработке нельзя использовать наследование. Для хранения дополнительных данных узла дерева приходится использовать поле TTreeNode.Data, представляющее собой указатель на произвольный объект или структуру данных.


Рис. 4

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

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

procedure TMainForm.NodeViewExpanding(Sender: TObject; Node: TTreeNode; 

var AllowExpansion: Boolean);

begin

  GetExpandingItems(Node);

end; 

Допустим, что у нас на форме есть компонент Query1, который содержит запрос

SELECT * FROM OBJECTS 

WHERE PARENT = :Parent

Процедура GetExpandingItems может быть реализована следующим образом:

procedure TMainForm.GetExpandingItems(var Node: TTreeNode) 

var NewNode: TTreeNode;

begin

  { если не передан "раскрываемый" узел, то это самый первый узел.

  иначе нужно в качестве Parent передать в запрос идентификатор

  элемента, который мы не совсем корректно будем хранить в

  Node.Data

  как целое число а не как указатель на структуру данных)}

  if Node = nil then

    Query1.ParamByName('Parent').asInteger:=0

  else

    begin

      Query1.ParamByName('Parent').asInteger:=integer(Node.Data);

      Node.DeleteChildren; { удалить "подэлементы" если они были }

    end;

  Query1.Open;

  Query1.First;

  while not Query1.EOF do

    begin

      NewNode:=TreeView1.Items.AddChildObject(Query1.FieldByName('NAME').asString);

      integer(NewNode.Data):=Query1.FieldByName('ID').asInteger;

      Query1.Next;

    end;

  Query.Close;

end; 

После выполнения этой функции создаются элементы, дочерние для указанного Node, или корневые элементы если Node=nil.

Однако в этом случае структура данных таблицы OBJECTS не дает нам возможности узнать (без дополнительного запроса) есть-ли у элемента его "подэлементы". И TreeView для всех элементов не будет показывать признак “раскрываемости” или значок “+”.

Для этих целей без расширения нашей структуры данных не обойтись. Очевидо необходимо добавить в таблицу OBJECTS поле, которое будет содержать количество дочерних элементов (0 или больше). Такое поле можно добавить 

ALTER TABLE OBJECTS ADD CCOUNT INTEGER DEFAULT 0; 

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

Триггер по вставке записи должен увеличить количество "детей" у своего родителя.

CREATE TRIGGER TBI_OBJECTS FOR OBJECTS 

ACTIVE BEFORE INSERT POSITION 0

AS

BEGIN

  UPDATE OBJECTS O

  SET O.CCOUNT = O.CCOUNT + 1

  WHERE O.ID = new.PARENT;

END 

Триггер по изменению проверяет, не меняется-ли родитель элемента. Если да, то значит элемент перемещается от одного родителя к другому и нужно соответственно уменьшить CCOUNT у старого и увеличить у нового.

CREATE TRIGGER TBU_OBJECTS FOR OBJECTS 

ACTIVE BEFORE UPDATE POSITION 0

AS

BEGIN

  if (old.PARENT <> new.PARENT) then

    begin

      UPDATE OBJECTS O SET O.CCOUNT = O.CCOUNT - 1

      WHERE O.ID = old.PARENT;

      UPDATE OBJECTS O SET O.CCOUNT = O.CCOUNT + 1

      WHERE O.ID = new.PARENT;

    end

END 

При удалении нужно уменьшить количество “детей” у владельца.

CREATE TRIGGER TBD_OBJECTS FOR OBJECTS 

ACTIVE BEFORE DELETE POSITION 0

AS

BEGIN

  UPDATE OBJECTS O

  SET O.CCOUNT = O.CCOUNT - 1

  WHERE O.ID = old.PARENT;

END 

(обратите внимание что во всех триггерах при обращении к таблице используетс псевдоним O, а для полей в триггере используется уточнитель new. или old. Это сделано для того, чтобы SQL-сервер не перепутал изменяемые поля в UPDATE и поля таблицы в контексте триггера)

Теперь таблица OBJECTS полностью автоматически отслеживает количество "детей" у каждого элемента.

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

Для того чтобы TTreeNode "знал" о наличии у него детей, поле Data должно уже указывать на некую структуру данных. Нам нужно хранить идентификатор узла, на всякий случай идентификатор родителя, и количество дочерних записей, а текст (NAME) можно хранить в TTreeNode, как это сделано в приведенном выше примере. Итак, создадим дополнительную структуру:

type 

  PItemRec = ^ItemRec;

  ItemRec = record

  Id : integer;

  Parent: integer;

  CСount: integer;

  end; 

При создании нового TreeNode нам придется теперь распределять память для ItemRec

...

var R: PItemRec;

  ...

  NewNode:=TreeView1.Items.AddChildObject(Query1.FieldByName('NAME').asString);    

  New(R); NewNode.Data:=R;

  R^.Id:=Query1.FieldByName('ID').asInteger;

  R^.Parent:=Query1.FieldByName('PARENT').asInteger;

  R^.CCount:=Query1.FieldByName('CCOUNT').asInteger;

  NewNode.HasChildren:=R^.CCount > 0;

  ... 

(для того чтобы правильно освобождать память, занимаемую операцией New(R), необходимо в методе TTreeView.OnDeletion написать одну строку – Dispose(PItemRec(Node.Data); Это освободит занятую память при удалении любого элемента TTreeNode или группы элементов)

Свойство HasChildren приведет к автоматической прорисовке значка "+" в TreeView у элемента, который имеет дочерние элементы. Таким образом мы получаем представление дерева без необходимости считывать все его элементы сразу.

Продолжение - Часть 2 

(c) KDV, www.ibase.ru 

Древовидные (иерархические) структуры данных в реляционных базах данных,
часть 2

Кузьменко Дмитрий, iBase.ru

Некоторые комментарии по поводу первой части статьи

Много времени прошло с момента опубликования первой части статьи, а ситуация в этой области никак не изменилась. Я получил много писем с просьбой продолжения, два полезных комментария, которые можно считать дополнением к этой статье (Registry в базе данных и комментарий), и несколько писем с указанием на ошибки в коде первой части статьи. Кроме этого вышла отличная статья Владимира Котляревского по реализации ООП в РСУБД.
Ошибки я исправлять не буду, пусть остается как есть. Тем более что код (по крайней мере Pascal), приведен из тестового примера, который уже давно удален. К этой части статьи приложен архив, в котором есть и пример на Delphi и база данных, так что реально работающий код берите оттуда.

Единственным пока заслуживающим внимания замечанием к первой части статьи является уточнение по поводу вторичного ключа, создаваемого по полю PARENT. Здесь возможно два варианта

  1.  убрать в объявлении столбца OBJECTS.PARENT ограничение NOT NULL, и построить Foreign Key как ссылка с PARENT на ID этой же таблицы. Корневые элементы тогда будут иметь PARENT = null.
  2.  Не создавать FK, создать индекс по PARENT вручную, для корневых элементов устанавливать PARENT = 0. При этом контролировать ссылку PARENT на существующего родителя (ID) придется в приложении (или триггерами).

Оба способа имеют свои достоинства (или удобства) и недостатки. Для варианта 1 (с FK) при выборе корневых элементов придется явно писать select * from objects where parent is null, т.к. условие where parent = :param, подходящее для всех остальных уровней дерева, не вернет нам ничего если с клиента параметр :param установить в null. Вариант 2, в свою очередь, допускает создание дочерних элементов для удаляемых в других транзакциях узлов дерева, поскольку ничем кроме FK (индекс которого "видит" все версии записей независимо от транзакций) гарантировать невозможность нарушения целостности связи PARENT и ID нельзя.

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

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

история изменений:

02.04.2004 добавлен "Перенос элементов дерева" 

"Один ребенок у двух родителей" или использование ссылок

В рассмотренном в первой части статье способе хранения информации о "родословной" объектов есть существенный пробел. Если говорить о наследовании в смысле родителей и детей, то наша структура БД такого не позволяет. Т.е. у родителя может быть несколько детей, но двух родителей у одного объекта быть не может - родитель объекта однозначно определяется полем PARENT.

Разумеется, если-бы нам потребовалось хранить в базе данных генеалогическую информацию, то мы сделали-бы совершенно другую структуру БД. Просто завели-бы список "людей" и во второй таблице организовали между ними "родственные отношения".

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

Насколько мне известно, популярной литературы по рассматриваемому вопросу не существует. Поэтому и предлагаемая реализация - частная. Почему я завел об этом речь? Дело в том, что достаточно интересная реализация связей между объектами реальной системы существует в файловых системах OS/2 и UNIX. В OS/2 - Shadow, в UNIX - HARDLINK и SOFTLINK. Именно эти реализации мы и попытаемся применить к нашей базе данных.

Добавим к нашей таблице OBJECTS поле REALID:

ALTER TABLE OBJECTS ADD REALID INTEGER NOT NULL DEFAULT -1 

Лично я не люблю связываться со значением NULL, когда речь идет о ссылках. Это касается и поля PARENT. Значение -1 в поле REALID будет означать, что эта запись представляет реальный объект. А любое, которое > 0 (т.е. равно какому-то существующему ID) будет означать, что запись представляет собой ссылку на реальный объект. Причем такой вариант ссылок реализует SOFTLINK или Shadow OS/2.
Примечание: чтобы не возбуждать повторно дискуссий о возможности null в foreign key, отошлю вас к Дейту. Конкретно к книге "Введение в системы баз данных". Таким образом, если вы хотите поспорить на эту тему - спорьте с Дейтом :-)

Правда, при однотипности "родителей" и "детей" в нашей БД не совсем ясно, как можно использовать подобные ссылки. Поэтому придется ввести разделение объектов, хранимых в таблице OBJECTS, на подтипы

"Каталог" и "файл"

Действительно. А почему-бы не имитировать хранение в базе данных каталогов и файлов? Ведь в основном информация, используемая в организациях, структурирована подобным образом. Файлы или документы - все хранится в каталогах или папках. Каталоги - в еще больших "шкафах" и т.д.
В связи с этим придется добавить еще одно поле в таблице OBJECTS:

ALTER TABLE OBJECTS ADD ISNODE INTEGER

Поле ISNODE будет являться индикатором: если запись является "каталогом", то ISNODE=1. Если запись является "файлом", то ISNODE=0.

Уфф. Вот теперь можно продолжить про ссылки на реальные объекты. Пример из жизни - сотрудник работает в одной организации, и устроен на полставки в другую. Т.е. сам объект "сотрудник" один и тот-же - с ФИО, паспортом и адресом, а работает в разных организациях. Наличие ссылок на объекты позволяет в каталоге первой организации создать объект "сотрудник", а в каталоге второй организации - ссылку на объект "сотрудник". Это нужно для того, чтобы иметь возможность модифицировать данные о сотруднике независимо от расположения ссылок.

Итак, данные представлены в виде:

ID

PARENT

REALID

ISNODE

NAME

1

0

-1

1

ACME Inc

2

1

-1

1

Сотрудники

3

2

-1

0

Иванов И.И.

4

0

-1

1

Total Intl.

5

4

-1

1

Полставочники

6

5

3

0

X

Эту-же информацию можно представить более наглядно:

ACME Inc.

      Сотрудники

          Иванов И.И.

  Total Intl            ^

      Полставочники  !

          X-----------------!

Запись с ID=6 при помощи REALID ссылается на запись с ID=3. При этом совершенно неважно, какого типа эта запись (ISNODE) и какие у нее значения остальных полей (в нашем случае только NAME). Почему? Да потому, что когда мы возьмем запись ID=6, то увидев REALID>=0 должны тут-же считать настоящую запись с ID=REALID и рассматривать в качестве данных только ее поля. Разумеется, в поля записи-ссылки можно (и нужно) занести информацию, идентичную реальной записи, с тем чтобы видеть содержимое нужных полей сразу при просмотре данных. Если такая запись содержит кроме текстовых и числовых полей еще и BLOB, то эти поля уже нет необходимости дублировать в записи-ссылке. Это существенно сэкономит дисковое пространство, занимаемое базой данных.

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

примечание: оригинальный id ссылки все-таки нужно "помнить" в приложении. Дело в том, что ссылки могут иметь другие имена (Name), в отличие от имен объектов. Например, как Shortcut-ы в Windows. Поэтому при обновлении "ссылки" нужно определять, что именно меняется - если имя, то его можно сменить у "ссылки", а если другие атрибуты, то их нужно менять у оригинальной записи.

Перенос элементов дерева

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

Например, нам требуется переместить папку Sub из одной папки в другую. То есть, папка Sub должна поменять идентификатор своего "родителя". Примерный запрос может выглядеть так:

UPDATE OBJECTS

SET PARENT_ID=:OWID

 WHERE ID = :DID;

Однако, элемент Sub является "конечным" в конкретной ветке "дерева", т.е. его можно перенести в любую другую папку. А что если попытаться перенести целиком вышестоящую папку? Тоже никаких проблем - все дочерние элементы автоматически "переместятся" вместе со своим родителем. Но вот что будет, если попытаться перенести папку "Test directory ..." в папку Sub?
Ничего хорошего, конечно, не получится. Даже если PARENT_ID проверяется на соответствие ID при помощи FK, зацикливание дерева FK проверить не сможет. Поэтому проверять такие ситуации нужно самостоятельно.
Надо сказать, что в конкретной реализации, которую вы видите на картинке, дерево объектов перерисовывается не из БД, а просто модифицируется при успешном выполнении любой операции (перенос, создание элемента и т.п.). Собственно, нет никакой необходимости перечитывать информацию, если операция по изменению дерева прошла в базе успешно. Возразить здесь можно, только если речь идет об узлах дерева, которые активно модифицируются в многопользовательской среде. Однако, такие операции относительно редки, не у всех пользователей могут быть права на выполнение таких действий, и, в конце-концов, при операции перемещения элемента из базы данных (или промежуточного сервера) можно выдать событие, чтобы клиентские места перерисовали нужную ветку дерева или все дерево целиком (
правда, тут надо предусмотреть последствия такой перерисовки, если пользователь в это время работает с деревом - часто компоненты или не делают expand для открытых узлов, или делают expand для всего отображаемого дерева).

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

 // DestNode, SourceNode = TTreeNode

 // не пытаемся ли сделать "зацикливание" дерева

 if DestNode.HasAsParent(SourceNode) then

   begin

     // нельзя перемещать или копировать объект сам в себя

     MessageDlg('Can not move or copy folder into itself.', mtError, [mbCancel], 0);

     Exit;

   end;

При этом до обращения к базе данных дело даже не доходит. Если же проверять такую ситуацию в базе, то получается, что клиентская часть безусловно выдает команду вроде ChangeParent(Id, NewParent), после чего процедура или триггер должны будут проверить зацикливание например при помощи уже описанной ранее процедуры GETPARENTS или ее модификации, и в случае зацикливания выдать Exception. Т.е. мы явно обращаемся к БД, даже в случае неуспешного выполнения такой операции.
Разумеется, гарантии целостности данных в самой БД, без такого контроля, остаются под вопросом - программист может забыть делать проверку на зацикливание в приложении. Поэтому вы сами должны определиться, что для вас важнее - либо исключить лишние обращения к базе данных, либо максимально обезопасить данные в случае прямого их изменения (
могу добавить, что никто не запрещает создать свой класс над TTreeView и внедрить туда метод перемещения элементов дерева, который сам будет контролировать зацикливание. т.е. защититься можно разными способами).

Обновление родителя

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

Вернемся теперь к самому первому абзацу - триггеры автоматически отслеживают изменение количества элементов у узла дерева. Это означает, что как при создании так при удалении выдается update, в котором обновляется конкретный элемент дерева, причем не тот, который создается или удаляется. Поскольку речь идет о родительском элементе, высока вероятность, что два или более пользователей попытаются одновременно создать дочерние элементы для одного и того же родителя. Это безусловно может привести к конфликтам блокировки, даже если процесс создания (перемещения, удаления) оформить в максимально короткой транзакции.
Что делать? Контролировать блокировки программно - пытаться повторить операцию в случае ошибки (deadlock, а не иной другой) или использовать режим транзакций wait (и тоже повторять неуспешную операцию).

Разграничение доступа

Самый больной вопрос в РСУБД, потому что стандарт не предусматривает разделение доступа к конкретным записям. Права можно дать на выборку из таблицы, ее обновление и т.п., но не на операции с записью. Знатоки Oracle или Linter могут меня поправить - в этих СУБД используется схема разграничения доступа к записям (мандатная защита), однако это реализация требований к защите информации для сертификации, и реально такая схема может иметь массу недостатков для применения в большинстве прикладных областей.

примечание: по Oracle см. также статью.

(Позже, или прямо сейчас, можете прочитать статью www.delphiplus.org/articles/ib/only_for_your_eyes/index.html о варианте разграничения доступа для IB/FB)

Второй недостаток РСУБД - отсутствие в стандарте понятия "группа пользователей". Конечно, в Interbase/Firebird есть роли (ROLE), но опять же, в соответствии со стандартом пользователь при коннекте не может получить права, выданные ему в двух или более ролях. Он получает только права одной, конкретно указанной при коннекте роли, плюс те права, которые ему были выданы явно (см. документ).

Далее я приведу два примера реализации разграничения прав доступа на уровне записи - схемы ACL и стандартная RWD.

! рекомендуется предварительно хотя бы просмотреть раздел "Права доступа" 

Группы пользователей и идентификация

В SQL аналогом "группы" может быть только "роль". Но, как говорилось выше, права разных ролей не "складываются" между собой. В большинстве задач, наоборот, надо чтобы человек мог входить в несколько групп, и автоматически получать права, данные всем этим группам сразу.
Раз таких групп, которые нам нужны, в SQL нет, придется отказываться от стандартной системы авторизации. Делается это следующим образом - создается пользователь системы, не SYSDBA, которому выдаются все нужные права для работы с системой. Далее, в базе данных создаются три таблицы: USERS, GROUPS, и USER_GROUPS.

примечание: модели выполнены в PowerDesigner 9.5 с использованием шаблона (использовать необязательно) intrbas6d3.xdb (поместите его в подкаталог DBMS установки PD9.5, перед тем как открывать модели, приведенные далее в качестве примеров).

соответственно, USERS хранит информацию (любую) о пользователях, GROUPS - это справочник групп, существующих в системе, а USER_GROUPS хранит информацию, какой пользователь включен в какую группу.

Проверка прав по маске

Удобнее всего права доступа хранить в одном поле в виде битов, установленных в 0 или 1. При этом потребуется подключение стандартных (или своих) функций логического AND.

При этом проверка конкретного бита будет выглядеть как условие
(
вместо L_AND можно использовать UDF из любого набора, в том числе ib_udf. Функция должна выполнять операцию логического AND)

L_AND(FIELD, флаг) <> 0

где "флаг" - число, соответствующее выставленному биту. Например 4, если выставлен бит 3. При этом можно проверять наличие сразу нескольких прав одновременно, указывая соответствующее значение "флага". Но как правило, в этом нет необходимости, поскольку операции обычно выполняются поодиночке.

Набор прав

Зависит от конкретной прикладной области. Где то хватит стандартных Read, Modify, Delete, где то будет нужно еще право Create, и т.п. И тут есть интересный момент.
В обычных файловых системах, для того, чтобы получить доступ к файлу, нужно сначала обратиться в каталог. Если есть право чтения каталога, то выдается список файлов, даже в том случае, если нет права на чтение самих файлов! А ведь имя файла, и особенно имя объекта (или документа) может сказать пользователю очень многое. Представтье себе внутрифирменный документ, который виден всем, но читать его может только администрация, с названием "Убытки за 2-ой квартал"?

Поэтому имеет смысл под правом "чтение" понимать не только право открытия объекта для просмотра его содержимого, но и право видеть его как объект вообще. В конкретной системе, в которой была реализована подобная схема, потребовалось чтобы пользователь мог иметь право создавать объекты в "каталогах", не видя их содержимого. Поэтому право Create имело номер меньший, чем право Read (см. далее раздел RWD). Для примера привожу список констант-прав доступа.

   0 none

   1 Create

   2 Read

   4 Modify

   8 Delete

  16 Move

  32 Copy

  64 Create shortcut

 128 Change access righs

 256 Change owner

 512 Login

1024 Add to group

2048 Delete from group

4096 Change group

8192 External event

16384 Create group

32768 Modify group

Как видно из списка, если потребуется более расширенный набор прав доступа, то битов в поле типа smallint может не хватить. Используйте INTEGER.

ACL

Это Access Control List, т.е. список элементов контроля доступа. Раз у нас есть пользователи, группы и объекты, то с каждым объектом должен быть связан список прав доступа для группы и пользователя. Эта схема используется во многих операционных системах, но чаще всего ее видно в Windows.

Таблица OBJECTS содержит объекты. USERS_ACL - список прав доступа к объекту для пользователей. GROUPS_ACL - список прав доступа к объекту для групп.

Исходя из схемы видно, что проверить права пользователя на доступ к объекту можно так:

1. выбрать список групп, в которые включен пользователь

 SELECT GID FROM USER_GROUPS WHERE UID = :user

2. Выбрать права из USERS_ACL

SELECT UR FROM USERS_ACL

WHERE UID = :user AND OID = :object

3. Выбрать права из GROUPS_ACL (объединяем с выборкой пункта 1)

 SELECT GR FROM GROUPS_ACL GA, USER_GROUPS UG

WHERE UG.GID = GA.GID AND UG.UID = :user AND GA.OID = :object

4. объединить права доступа UR и GR, полученные пунктами 2 и 3.

замечание: сразу скажу, что GR и UR я изначально принял как битовые маски для прав доступа. А теперь представьте себе, как усложнится приведенная выше схема, если использовать не битовые маски, а отдельные записи со значениями конкретных прав! (кто готов поспорить, пусть пришлет мне модель и пример запросов на email).

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

примечание: поскольку прав доступа может не быть объявлено для группы или пользователя, мы вынуждены использовать outer join для объединения запросов. Итоговый запрос будет выглядеть следующим образом:

SELECT O.OID, O.OBJECT_NAME, O.OBJECT_DATA, GA.GR, UA.UR

FROM

USER_GROUPS UG

JOIN

GROUPS_ACL GA

 ON UG.GID = GA.GID AND UG.UID = :user

RIGHT JOIN OBJECTS O

 ON GA.OID = O.OID

LEFT JOIN USERS_ACL UA

 ON UA.OID = O.OID AND UA.UID = :user

запрос будет выбирать все объекты, на которые пользователь user имеет любые права. Если нужно выбрать конкретный объект и его права, то к запросу следует добавить WHERE O.OID = :object.

Для примера приведу результат такой выборки (для всех записей)

OID

OBJECT_NAME

OBJECT_DATA

GR

UR

1

Object1

 

modify

modify

1

Object1

 

read

modify

2

Object2

 

null

null

3

Object3

 

modify

null

Представим себе что есть пользователи 1 и 2, группы 1 и 2. Пользователь 1 включен в группы 1 и 2, пользователь 2 - только в группу 1. На объект 1 даны права пользователю 1 (изменение), группе 1 (изменение), группе 2 (чтение). На объект 3 даны права пользователю 2 на изменение.

Первая запись в списке содержит права группы 1 и пользователя 1
Вторая запись в списке содержит права группы 2 и пользователя 1

Чем больше будет дано прав на объект 1, тем больше записей с этим идентификатором может появиться. Мы не можем использовать distinct для "схлопывания" повторяющихся идентификаторов, т.к. права пользователя и группы могут быть разные, могут иметь разный приоритет, и в любом случае должны быть "просуммированы". Например, пользователь 1 включен в группы 1 и 2, которые имеют право изменения и чтения, соответственно. Максимальным правом получается "изменение". Типов прав может быть много, если это не битовая маска, то допустимо выполнение агрегатной операции SUM(GR) (если битовая маска, то сложение бита 4 и 4 приведет к результату равному 8. А в случае битовых масок сложение должно быть по логическому OR. Такой агрегатной функции, к сожалению, нет). Однако у нас и так запрос имеет план не очень красивый, а если еще добавить агрегаты, то скорость выполнения такого запроса будет весьма низкой. Кроме того, как правило, на один объект накладывают несколько прав доступа. Если даже в среднем один объект будет иметь 4-5 прав доступа, то это означает, что в таблицах X_ACL в сумме будет записей в 4-5 раз больше, чем в таблице объектов.

В общем, схему ACL можно считать для РСУБД неподходящей. Кроме того, ее весьма сложно администрировать.

примечание: может возникнуть вопрос - если эта схема такая неудобная, то почему она нормально работает в файловых системах? В файловых системах не возникает таких запросов (и так часто), как в РСУБД. Поэтому затраты на "сборку" прав доступа для объекта можно считать несущественными.

файл: acl.pdm для PowerDesigner 9.5

RWD

Стандартная схема предполагает хранение прав доступа в привязке к конкретному объекту, причем всего в трех полях - права пользователя (UR), права группы (GR), права всех (AR). Т.е. в этом случае достаточно изменить структуру таблицы объектов следующим образом:

ALTER TABLE OBJECTS

  ADD UID INT NOT NULL REFERENCES USERS,

  ADD UR  INT DEFAULT 255,

  ADD GID INT NOT NULL REFERENCES GROUPS,

  ADD GR  INT DEFAULT 255,

  ADD AR  INT DEFAULT 0

В данном случае default указаны как битовые маски, включающие в себя все права по умолчанию для создателя документа и его группы. References для лучшей читаемости структуры БД лучше заменить на явно создаваемый constraint xxx foreign key (здесь references приведено только для наглядности).

Т.е. при выборке объектов мы сразу получаем информацию о "владельце" объекта и его правах (UID и UR), группе объекта и ее правах (GID и GR), и правах для всех (AR).

Такая схема позволяет практически мгновенно при выборе объекта определить, имеет пользователь права соответствующего доступа к этому объекту, или нет. Выражаясь более простым языком - такая проверка очень легко помещается в конструкцию where.
Единственной проблемой может казаться здесь проверка присутствия пользователя в конкретной группе, если нет доступа для всех и пользователь не является "владельцем" объекта. Однако это тоже легко решается вложенным подзапросом. Итак, при выборке мы проверяем следующие условия:

(права_всех) OR
((пользователь = владелец) AND (права_пользователя)) OR
((группа_пользователя = группа) AND (права группы))

Данная схема не совсем соответствует проверке прав на Unix - там если идентификатор пользователя (владельца) совпадает, то проверка дальше не производится. В IB используется проверка всех условий OR во время выполнения оператора, так что если пользователь - владелец записи, то права группы все равно будут проверяться.

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

При чтении объектов:

SELECT O.OID, O.OBJECT_NAME, O.OBJECT_DATA

FROM OBJECTS O

WHERE

(O.OWNER_ID = :OID) AND

((O.AR >= 2) OR

((O.UID = :UID) AND (O.UR >= 2)) OR

((O.GR >= 2) AND

(O.GID IN

(SELECT UG.GID FROM USER_GROUPS UG

 WHERE

 (UG.UID = :UID)))))

Если не нравится конструкция IN, то ее можно заменить на

 (EXISTS  

(SELECT UG.GID FROM USER_GROUPS UG

 WHERE

 (UG.UID = :UID)))))

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

При проверке прав "вообще" можно использовать процедуру вида:
Входные параметры - пользователь, группа, идентификатор объекта, действие (право)

CREATE PROCEDURE CHECKRIGHTS(

  UID INT, GID INT, OID INTEGER, ACT INTEGER)

  RETURNS (CANDO INTEGER)

AS

DECLARE VARIABLE UI INTEGER;

DECLARE VARIABLE GI INTEGER;

DECLARE VARIABLE URR INTEGER;

DECLARE VARIABLE GRR INTEGER;

DECLARE VARIABLE ARR INTEGER;

DECLARE VARIABLE RC INTEGER;

BEGIN

 CANDO=0; UI=NULL; GI=NULL; URR=NULL; GRR=NULL; ARR=NULL;

 SELECT O.UID, O.GID, O.UR, O.GR, O.AR

  FROM OBJECTS O

  WHERE O.OID=:OID

  INTO :UI, :GI, :URR, :GRR, :ARR;

 /* no such document - do what you want */

 if ((:UI IS NULL) or (:GI IS NULL)) then

   begin

     CANDO=1;

     SUSPEND;

   end

 /* check rights: all, user's, group's */

 if ((L_AND(:ARR, :ACT) <> 0) or

    ((:UID = :UI) and (LAND(:URR, :ACT) <> 0)) or

    ((:GID = :GI) and (LAND(:GRR, :ACT) <> 0))) then

   CANDO=1;

 else

 /* check if user in any group that have same gid */

   if (:GID <> :GI) then

     begin

       rc=0;

       select count(*) from user_groups ug

       where (ug.uid = :UID) and (ug.gid = :GI)

       into :RC;

       if ((:RC <> 0) and (L_AND(:GRR, :ACT) <> 0)) then

         CANDO=1;

     end

 SUSPEND;

END

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

файл: rwd.pdm для PowerDesigner 9.5

Иерархия групп

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

Вот два примера иерархии

1. права снизу-вверх

разработчики

  ПроектА

  ПроектБ

В этом случае есть группа "Разработчики", в которую включены все разработчики компании. Документы для группы "Разработчики" могут быть самыми разнообразными - конференции, примеры кода, правила оформления исходных текстов и т.п. Т.е. все разработчики компании должны иметь к ним доступ. Однако на уровне конкретных проектов в группы включаются только те разработчики, которые непосредственно участвуют в этих проектах.
Например, Иванов. М.Е. - разработчик, включен в группу "Разработчики" и "ПроектА". В этом случае он не может работать с записями, принадлежащими группе "ПроектБ".

2. права сверху вниз

администрация

   бухгалтерия

   плановый отдел

В этом случае директор Сидоров П.А., входящий в группу "администрация", должен автоматически быть включен в группы "плановый отдел" и "бухгалтерия". Наоборот, бухгалтер Иванова М.И. не должна быть включена в группу "администрация".

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

Реализация дерева групп

Напрасно надеетесь увидеть здесь конкретный пример. Дерево групп организуется тем же самым способом, что и обычное "дерево", о котором рассказано в первой части статьи. Более того, в случае реально работавшей системы, древовидное отображение групп было добавлено намного позже (изначально группы были линейными, просто у таблицы и так был столбец id, а добавление столбца parent_id просто позволило выстраивать группы древовидно), что никак не отразилось на остальной части БД (были дописаны процедуры и триггеры для обработки USER_GROUPS).

 

Администрирование прав RWD

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

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

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

Таким образом, если пользователь А создает объект (документ), и хочет чтобы пользователи B и C также имели к нему доступ, мы должны создать группу X, включить туда пользователей A, B и C, и при создании объекта указать в GroupId идентификатор группы X, а в правах группы указать как минимум право на чтение.

Теперь, если появляется новый пользователь, который должен получить доступ к объекту, мы должны его включить в группу X.
Однако, при этом такой пользователь получит доступ ко всем объектам (документам_, созданным с GroupId = X. А если нужно дать доступ только к одному или нескольким конкретным объектам?

В этом случае придется сделать следующее:

  1.  создать новую группу, например Z
  2.  включить в группу Z тех, кто публикует объект (документ)
  3.  включить в группу Z тех, кто должен получить доступ к объекту

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

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

Соответственно выглядеть это может как

  •  Каталог группы А
    •  документ 1
    •  документ 2
  •  Каталог группы Б
    •  документ 3
    •  документ 4
  •  Общий каталог группы Z
    •  копия (или ссылка) документа 1
    •  копия (или ссылка) документа 3

Здесь есть потенциальная дыра в безопасности, особенно если использовать разные права на доступ к самому документу и его ссылке (shortcut). Дело в том, что один документ как таковой (т.е. с одним содержимым) виден разным группам пользователей с разными правами. И на определенном этапе пользователи группы Б могут "забыть", что документ 3 "опубликован" для группы Z. В частности, необходимо не давать возможности для документов, принадлежащих группе Z, изменять права доступа.

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

Указание прав при создании объекта

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

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

Наследование прав

 

Продолжение следует!

Далее будут: объединение схем RWD и ACL...

Литература:

  •  ООП в РСУБД 
  •  Применение XML для хранения сложных объектов. 
  •  Представление объектов в реляционных базах данных (eng)
  •  Комментарий к этой статье "Древовидные ..." 
  •  Письмо по поводу древовидных структур
  •  Компонент IBX для работы с древовидными структурами по статье
  •  "Registry" в базе данных 
  •  Моделирование квазиструктурированных данных 
  •  Деревья в SQL, часть 1. Joe Celko.
  •  Деревья в SQL, часть 2. Joe Celko.
  •  Деревья в SQL, часть 3. Joe Celko.
  •  Еще раз про деревья, Joe Celko
  •  Все три части "Деревья в SQL" на русском языке.
  •  Вариант решения некоторых проблем деревьев.
  •  Компонент для работы с деревьями через IBX 
  •  Применение деревьев в системах бухучета 
  •  Суммирование в деревьях 

Спасибо:

Дмитрию Попову за дополнения и указания на неточности.

(с) KDV, www.ibase.ru 

 

 

Глава 3. Реляционный подход

3.1. Реляционная структура данных

В конце 60-х годов появились работы, в которых обсуждались возможности применения различных табличных даталогических моделей данных, т.е. возможности использования привычных и естественных способов представления данных. Наиболее значительной из них была статья сотрудника фирмы IBM д-ра Э.Кодда (Codd E.F., A Relational Model of Data for Large Shared Data Banks. CACM 13: 6, June 1970), где, вероятно, впервые был применен термин "реляционная модель данных".

Будучи математиком по образованию Э.Кодд предложил использовать для обработки данных аппарат теории множеств (объединение, пересечение, разность, декартово произведение). Он показал, что любое представление данных сводится к совокупности двумерных таблиц особого вида, известного в математике как отношение – relation (англ.) [3, 7, 9].

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

Доменом называется множество атомарных значений одного и того же типа. Так, на рис. 1.1 домен пунктов отправления (назначения) – множество названий населенных пунктов, а домен номеров рейса – множество целых положительных чисел.

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

Отношение на доменах D1, D2, ..., Dn (не обязательно, чтобы все они были различны) состоит из заголовка и тела. На рис. 3.1 приведен пример отношения для расписания движения самолетов (рис. 1.1).

Заголовок (на рис. 1.1 он назывался интерпретацией) состоит из такого фиксированного множества атрибутов A1, A2, ..., An, что существует взаимно однозначное соответствие между этими атрибутами Ai и определяющими их доменами Di (i=1,2,...,n).

Рис. 3.1. Отношение с математической точки зрения (Ai - атрибуты, Vi - значения атрибутов)

Тело состоит из меняющегося во времени множества кортежей, где каждый кортеж состоит в свою очередь из множества пар атрибут-значение (Ai:Vi), (i=1,2,...,n), по одной такой паре для каждого атрибута Ai в заголовке. Для любой заданной пары атрибут-значение (Ai:Vi) Vi является значением из единственного домена Di, который связан с атрибутом Ai.

Степень отношения – это число его атрибутов. Отношение степени один называют унарным, степени два – бинарным, степени три – тернарным, ..., а степени n – n-арным. Степень отношения "Рейс" (рис. 1.1) – 8.

Кардинальное число или мощность отношения – это число его кортежей. Мощность отношения "Рейс" равна 10. Кардинальное число отношения изменяется во времени в отличие от его степени.

Поскольку отношение – это множество, а множества по определению не содержат совпадающих элементов, то никакие два кортежа отношения не могут быть дубликатами друг друга в любой произвольно-заданный момент времени. Пусть R – отношение с атрибутами A1, A2, ..., An. Говорят, что множество атрибутов K=(Ai, Aj, ..., Ak) отношения R является возможным ключом R тогда и только тогда, когда удовлетворяются два независимых от времени условия:

  1.  Уникальность: в произвольный заданный момент времени никакие два различных кортежа R не имеют одного и того же значения для Ai, Aj, ..., Ak.
  2.  Минимальность: ни один из атрибутов Ai, Aj, ..., Ak не может быть исключен из K без нарушения уникальности.

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

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

Отношение – Таблица (иногда Файл),
Кортеж –
Строка (иногда Запись),
Атрибут –
Столбец, Поле.

При этом принимается, что "запись" означает "экземпляр записи", а "поле" означает "имя и тип поля".

[Назад] [Содержание] [Вперед]

3.2. Реляционная база данных

Реляционная база данных – это совокупность отношений, содержащих всю информацию, которая должна храниться в БД. Однако пользователи могут воспринимать такую базу данных как совокупность таблиц. Так на рис. 3.2 показаны таблицы базы данных, построенные по инфологической модели базы данных "Питание" рис. 2.4.

Блюда

БЛ

Блюдо

Вид

1

Лобио

Закуска

2

Харчо

Суп

3

Шашлык

Горячее

4

Кофе

Десерт


Расход

БЛ

Порций

Дата_Р

1

158

1/9/94

2

144

1/9/94

3

207

1/9/94

4

235

1/9/94

...

...

...

Продукты

ПР

Продукт

Калор.

1

Фасоль

3070

2

Лук

450

3

Масло

7420

4

Зелень

180

5

Мясо

1660

6

Томаты

240

7

Рис

3340

8

Кофе

2750


Рецепты

БЛ

Рецепт

1

Ломаную очищ

...

...

Состав

БЛ

ПР

Веc (г)

1

1

200

1

2

40

1

3

30

1

4

10

2

5

80

2

2

30

2

6

40

2

7

50

2

3

15

2

4

15

3

5

180

3

6

100

3

2

40

3

4

20

4

8

8

Поставщики

ПОС

Поставщик

Город

1

"Полесье"

Киев

2

"Наталка"

Киев

3

"Хуанхэ"

Пекин

4

"Лайма"

Рига

5

"Юрмала"

Рига

6

"Даугава"

Рига


Города

Город

Страна

Киев

Украина

Пекин

Китай

Рига

Латвия

Поставки

ПОС

ПР

Вес (кг)

Цена

Дата_П

1

6

120

0.45

27/8/94

1

3

50

1.82

27/8/94

1

2

50

0.61

27/8/94

2

2

100

0.52

27/8/94

2

5

100

2.18

27/8/94

2

4

10

0.88

27/8/94

3

1

250

0.37

24/8/94

3

7

75

0.44

24/8/94

3

8

40

2.87

24/8/94

4

3

70

1.56

30/8/94

5

5

200

2.05

30/8/94

6

6

15

0.99

30/8/94

Рис. 3.2. База данных "Питание" (см. п. 2.3)

1. Каждая таблица состоит из однотипных строк и имеет уникальное имя.

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

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

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

5. Полное информационное содержание базы данных представляется в виде явных значений данных и такой метод представления является единственным. В частности, не существует каких-либо специальных "связей" или указателей, соединяющих одну таблицу с другой. Так, связи между строкой с БЛ = 2 таблицы "Блюда" на рис. 3.2 и строкой с ПР = 7 таблицы продукты (для приготовления Харчо нужен Рис), представляется не с помощью указателей, а благодаря существованию в таблице "Состав" строки, в которой номер блюда равен 2, а номер продукта – 7.

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

[Назад] [Содержание] [Впере

3.3. Манипулирование реляционными данными

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

Предложив реляционную модель данных, Э.Ф.Кодд создал и инструмент для удобной работы с отношениями – реляционную алгебру. Каждая операция этой алгебры использует одну или несколько таблиц (отношений) в качестве ее операндов и продуцирует в результате новую таблицу, т.е. позволяет "разрезать" или "склеивать" таблицы (рис. 3.3).

Рис. 3.3. Некоторые операции реляционной алгебры

Созданы языки манипулирования данными, позволяющие реализовать все операции реляционной алгебры и практически любые их сочетания. Среди них наиболее распространены SQL (Structured Query Language – структуризованный язык запросов) и QBE (Quere-By-Example – запросы по образцу) [3, 5]. Оба относятся к языкам очень высокого уровня, с помощью которых пользователь указывает, какие данные необходимо получить, не уточняя процедуру их получения.

С помощью единственного запроса на любом из этих языков можно соединить несколько таблиц во временную таблицу и вырезать из нее требуемые строки и столбцы (селекция и проекция).

Реляционные базы данных

Оглавление 

Входы 

Базы данных >

Данные >

Информационные продукты >

Системы управления базами данных >

Структуры баз данных >

 

§ Информационные технологии

Реляционная база данных (РБД)

База данных реляционного типа

Relational database

Реляционная база данных - база данных, построенная на основе реляционной модели. В реляционной базе каждый объект задается записью (строкой) в таблице.

Реляционная база создается и затем управляется с помощью реляционной системы управления базами данных.

 
Новая функция:  
Формула глоссария
 

 Выходы

 >> Реляционная модель данных

 

    Тематическая группировка  • Раcширить глоссарий  • Основные темы 

Реляционная база данных (РБД)

База данных реляционного типа

Relational database

Реляционная база данных - база данных, построенная на основе реляционной модели. В реляционной базе каждый объект задается записью (строкой) в таблице.

Реляционная база создается и затем управляется с помощью реляционной системы управления базами данных.

Начало формы

Переход   Яndex Верх Google Низ 

Конец формы

База данных (БД)

Database; Data base (DB)

фр.Base de donnees

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

Начало формы

Переход   Яndex Верх Google Низ 

Конец формы

 >> Реляционная модель данных 

От англ.Relation - отношение

Реляционная модель данных - разработанная Э.Коддом в 1970г. логическая модель данных, описывающая:
- структуры данных в виде (изменяющихся во времени) наборов отношений;
- теоретико-множественные операции над данными: объединение, пересечение, разность и декартово произведение;
- специальные реляционные операции: селекция, проекция, соединение и деление; а также
- специальные правила, обеспечивающие целостность данных.

Начало формы

Переход   Яndex Верх Google Низ 

Конец формы

Реляционная система управления базой данных (РСУБД)

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

Начало формы

Переход   Яndex Верх Google Низ 

Конец формы

Структурированный язык запросов

Structured query language (SQL)

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

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

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

1. Базовые понятия реляционных баз данных

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

Для начала покажем смысл этих понятий на примере отношения СОТРУДНИКИ, содержащего информацию о сотрудниках некоторой организации:

1.1. Тип данных

Понятие тип данных в реляционной модели данных полностью адекватно понятию типа данных в языках программирования. Обычно в современных реляционных базах данных допускается хранение символьных, числовых данных, битовых строк, специализированных числовых данных (таких как "деньги"), а также специальных "темпоральных" данных (дата, время, временной интервал). Достаточно активно развивается подход к расширению возможностей реляционных систем абстрактными типами данных (соответствующими возможностями обладают, например, системы семейства Ingres/Postgres). В нашем примере мы имеем дело с данными трех типов: строки символов, целые числа и "деньги".

1.2. Домен

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

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

Следует отметить также семантическую нагрузку понятия домена: данные считаются сравнимыми только в том случае, когда они относятся к одному домену. В нашем примере значения доменов "Номера пропусков" и "Номера групп" относятся к типу целых чисел, но не являются сравнимыми. Заметим, что в большинстве реляционных СУБД понятие домена не используется, хотя в Oracle V.7 оно уже поддерживается.

1.3. Схема отношения, схема базы данных

Схема отношения базы данных - это именованное множество пар {имя атрибута, имя домена (или типа, если понятие домена не поддерживается)}. Степень или "арность" схемы отношения - мощность этого множества. Степень отношения СОТРУДНИКИ равна четырем, то есть оно является 4-арным. Если все атрибуты одного отношения определены на разных доменах, осмысленно использовать для именования атрибутов имена соответствующих доменов (не забывая, конечно, о том, что это является всего лишь удобным способом именования и не устраняет различия между понятиями домена и атрибута).

Схема базы данных (в структурном смысле) - это набор именованных схем отношений.

1.4. Кортеж, отношение

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

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

Однако в реляционных базах данных это не принято. Имя схемы отношения в таких базах данных всегда совпадает с именем соответствующего отношения-экземпляра. В классических реляционных базах данных после определения схемы базы данных изменяются только отношения-экземпляры. В них могут появляться новые и удаляться или модифицироваться существующие кортежи. Однако во многих реализациях допускается и изменение схемы базы данных: определение новых и изменение существующих схем отношения. Это принято называть эволюцией схемы базы данных.

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

Реляционная база данных - это набор отношений, имена которых совпадают с именами схем отношений в схеме базы данных.

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

2. Фундаментальные свойства отношений

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

2.1. Отсутствие кортежей-дубликатов

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

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

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

2.2. Отсутствие упорядоченности кортежей

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

2.3. Отсутствие упорядоченности атрибутов

Атрибуты отношений не упорядочены, поскольку по определению схема отношения есть множество пар {имя атрибута, имя домена}. Для ссылки на значение атрибута в кортеже отношения всегда используется имя атрибута. Это свойство теоретически позволяет, например, модифицировать схемы существующих отношений в базе данных не только путем добавления новых атрибутов, но и путем удаления существующих атрибутов. Однако в большинстве существующих систем такая возможность не допускается, и хотя упорядоченность набора атрибутов отношения явно не требуется, часто в качестве неявного порядка атрибутов используется их порядок в линейной форме определения схемы отношения базы данных.

2.4. Атомарность значений атрибутов

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

Можно сказать, что здесь мы имеем бинарное отношение, значениями атрибута ОТДЕЛЫ которого являются отношения. Заметим, что исходное отношение СОТРУДНИКИ является нормализованным вариантом отношения ОТДЕЛЫ:

СОТР_НОМЕР

СОТР_ИМЯ

СОТР_ЗАРП

СОТР_ОТД_НОМЕР

2934

Иванов

112,000

310

2935

Петров

144,000

310

2936

Сидоров

92,000

313

2937

Федоров

110,000

310

2938

Иванова

112,000

315

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

Зачислить сотрудника Кузнецова (пропуск номер 3000, зарплата 115,000) в отдел номер 320 и

Зачислить сотрудника Кузнецова (пропуск номер 3000, зарплата 115,000) в отдел номер 310.

Если информация о сотрудниках представлена в виде отношения СОТРУДНИКИ, оба оператора будут выполняться одинаково (вставить кортеж в отношение СОТРУДНИКИ). Если же работать с ненормализованным отношением ОТДЕЛЫ, то первый оператор выразится в занесение кортежа, а второй - в добавление информации о Кузнецове в множественное значение атрибута ОТДЕЛ кортежа с первичным ключом 310.

3. Реляционная модель данных

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

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

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

3.1. Общая характеристика

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

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

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

3.2. Целостность сущности и ссылок

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

Второе требование называется требованием целостности по ссылкам и является несколько более сложным. Очевидно, что при соблюдении нормализованности отношений сложные сущности реального мира представляются в реляционной базе данных в виде нескольких кортежей нескольких отношений. Например, представим, что нам требуется представить в реляционной базе данных сущность ОТДЕЛ с атрибутами ОТД_НОМЕР (номер отдела), ОТД_КОЛ (количество сотрудников) и ОТД_СОТР (набор сотрудников отдела). Для каждого сотрудника нужно хранить СОТР_НОМЕР (номер сотрудника), СОТР_ИМЯ (имя сотрудника) и СОТР_ЗАРП (заработная плата сотрудника). Как мы вскоре увидим, при правильном проектировании соответствующей БД в ней появятся два отношения: ОТДЕЛЫ ( ОТД_НОМЕР, ОТД_КОЛ ) (первичный ключ - ОТД_НОМЕР) и СОТРУДНИКИ ( СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРП, СОТР_ОТД_НОМ ) (первичный ключ - СОТР_НОМЕР).

Как видно, атрибут СОТР_ОТД_НОМ появляется в отношении СОТРУДНИКИ не потому, что номер отдела является собственным свойством сотрудника, а лишь для того, чтобы иметь возможность восстановить при необходимости полную сущность ОТДЕЛ. Значение атрибута СОТР_ОТД_НОМ в любом кортеже отношения СОТРУДНИКИ должно соответствовать значению атрибута ОТД_НОМ в некотором кортеже отношения ОТДЕЛЫ. Атрибут такого рода называется внешним ключом, поскольку его значения однозначно характеризуют сущности, представленные кортежами некоторого другого отношения (т.е. задают значения их первичного ключа). Говорят, что отношение, в котором определен внешний ключ, ссылается на соответствующее отношение, в котором такой же атрибут является первичным ключом.

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

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

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

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

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

Базисные средства манипулирования реляционными базами данных

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

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

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

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

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

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

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

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

1. Реляционная алгебра

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

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

  •  объединения отношений;
  •  пересечения отношений;
  •  взятия разности отношений;
  •  прямого произведения отношений.

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

  •  ограничение отношения;
  •  проекцию отношения;
  •  соединение отношений;
  •  деление отношений.

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

1.1. Общая интерпретация реляционных операций

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

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

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

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

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

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

Например, представим себе, что у отношений-операндов операции прямого произведения имеются одноименные атрибуты с одинаковыми доменами. Каким был бы заголовок результирующего отношения? Поскольку это множество, в нем не должны содержаться одинаковые элементы. Но и потерять атрибут в результате недопустимо. А это значит, что в этом случае вообще невозможно корректно выполнить операцию прямого произведения.

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

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

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

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

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

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

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

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

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

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

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

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

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

По поводу теоретико-множественных операций реляционной алгебры баз данных следует еще заметить, что все четыре операции являются ассоциативными. Т. е., если обозначить через OP любую из четырех операций, то (A OP B) OP C = A (B OP C), и следовательно, без введения двусмысленности можно писать A OP B OP C (A, B и C - отношения, обладающие свойствами, требуемыми для корректного выполнения соответствующей операции). Все операции, кроме взятия разности, являются коммутативными, т.е. A OP B = B OP A.

1.4. Специальные реляционные операции баз данных

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

Операция ограничения

Операция ограничения требует наличия двух операндов: ограничиваемого отношения и простого условия ограничения. Простое условие ограничения может иметь либо вид (a comp-op b), где а и b - имена атрибутов ограничиваемого отношения, для которых осмысленна операция сравнения comp-op, либо вид (a comp-op const), где a - имя атрибута ограничиваемого отношения, а const - литерально заданная константа.

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

Пусть UNION обозначает операцию объединения, INTERSECT - операцию пересечения, а MINUS - операцию взятия разности. Для обозначения в базе данных операции ограничения будем использовать конструкцию A WHERE comp, где A - ограничиваемое отношение, а comp - простое условие сравнения. Пусть comp1 и comp2 - два простых условия ограничения. Тогда по определению:

  •  A WHERE comp1 AND comp2 обозначает то же самое, что и (A WHERE comp1) INTERSECT (A WHERE comp2)
  •  A WHERE comp1 OR comp2 обозначает то же самое, что и (A WHERE comp1) UNION (A WHERE comp2)
  •  A WHERE NOT comp1 обозначает то же самое, что и A MINUS (A WHERE comp1)

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

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

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

Операция взятия проекции также требует наличия двух операндов - проецируемого отношения A и списка имен атрибутов, входящих в заголовок отношения A.

Результатом проекции отношения A по списку атрибутов a1, a2, ..., an является отношение, с заголовком, определяемым множеством атрибутов a1, a2, ..., an, и с телом, состоящим из кортежей вида <a1:v1, a2:v2, ..., an:vn> таких, что в отношении A имеется кортеж, атрибут a1 которого имеет значение v1, атрибут a2 имеет значение v2, ..., атрибут an имеет значение vn. Тем самым, при выполнении операции проекции выделяется "вертикальная" вырезка отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов баз данных.

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

Общая операция соединения в базе данных (называемая также соединением по условию) требует наличия двух операндов - соединяемых отношений и третьего операнда - простого условия. Пусть соединяются отношения A и B. Как и в случае операции ограничения, условие соединения comp имеет вид либо (a comp-op b), либо (a comp-op const), где a и b - имена атрибутов отношений A и B, const - литерально заданная константа, а comp-op - допустимая в данном контексте операция сравнения.

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

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

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

Имеется важный частный случай соединения - эквисоединение и простое, но важное расширение операции эквисоединения - естественное соединение. Операция соединения называется операцией эквисоединения, если условие соединения в базе данных имеет вид (a = b), где a и b - атрибуты разных операндов соединения. Этот случай важен потому, что (a) он часто встречается на практике, и (b) для него существуют эффективные алгоритмы реализации.

Операция естественного соединения применяется к паре отношений A и B, обладающих (возможно составным) общим атрибутом c (т.е. атрибутом с одним и тем же именем и определенным на одном и том же домене). Пусть ab обозначает объединение заголовков отношений A и B. Тогда естественное соединение A и B - это спроектированный на ab результат эквисоединения A и B по A/c и BBC. Если вспомнить введенное нами в конце предыдущей главы определение внешнего ключа отношения базы данных, то должно стать понятно, что основной смысл операции естественного соединения - возможность восстановления сложной сущности, декомпозированной по причине требования первой нормальной формы. Операция естественного соединения не включается прямо в состав набора операций реляционной алгебры, но она имеет очень важное практическое значение для реализации баз данных.

Операция деления отношений

Эта операция базы данных наименее очевидна из всех операций реляционной алгебры и поэтому нуждается в более подробном объяснении. Пусть заданы два отношения - A с заголовком {a1, a2, ..., an, b1, b2, ..., bm} и B с заголовком {b1, b2, ..., bm}. Будем считать, что атрибут bi отношения A и атрибут bi отношения B не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {aj} составным атрибутом a, а множество атрибутов {bj} - составным атрибутом b. После этого будем говорить о реляционном делении бинарного отношения A(a,b) на унарное отношение B(b).

В базе данных результатом деления A на B является унарное отношение C(a), состоящее из кортежей v таких, что в отношении A имеются кортежи <v, w> такие, что множество значений {w} включает множество значений атрибута b в отношении B.

Предположим, что в базе данных сотрудников поддерживаются два отношения: СОТРУДНИКИ ( ИМЯ, ОТД_НОМЕР ) и ИМЕНА ( ИМЯ ), причем унарное отношение ИМЕНА содержит все фамилии, которыми обладают сотрудники организации. Тогда после выполнения операции реляционного деления отношения СОТРУДНИКИ на отношение ИМЕНА в базе данных будет получено унарное отношение, содержащее номера отделов, сотрудники которых обладают всеми возможными в этой организации именами.

2. Реляционное исчисление

Предположим, что мы работаем с базой данных, обладающей схемой СОТРУДНИКИ (СОТР_НОМ, СОТР_ИМЯ, СОТР_ЗАРП, ОТД_НОМ) и ОТДЕЛЫ (ОТД_НОМ, ОТД_КОЛ, ОТД_НАЧ), и хотим узнать имена и номера сотрудников, являющихся начальниками отделов с количеством сотрудников больше 50.

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

  •  выполнить соединение отношений СОТРУДНИКИ и ОТДЕЛЫ по условию СОТР_НОМ = ОТД_НАЧ;
  •  ограничить полученное отношение по условию ОТД_КОЛ > 50;
  •  спроецировать результат предыдущей операции на атрибут СОТР_ИМЯ, СОТР_НОМ.

Мы четко сформулировали последовательность шагов выполнения запроса к базе данных, каждый из которых соответствует одной реляционной операции. Если же сформулировать тот же запрос с использованием реляционного исчисления, которому посвящается этот раздел, то мы получили бы формулу, которую можно было бы прочитать, например, следующим образом: Выдать СОТР_ИМЯ и СОТР_НОМ для сотрудников таких, что существует отдел с таким же значением ОТД_НАЧ и значением ОТД_КОЛ большим 50.

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

2.1. Кортежные переменные и правильно построенные формулы

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

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

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

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

   RANGE СОТРУДНИК IS СОТРУДНИКИ

Как мы уже говорили, из этого определения следует, что в любой момент времени переменная СОТРУДНИК, содержащаяся в бвзе данных представляет некоторый кортеж отношения СОТРУДНИКИ. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной (это аналогично тому, как, например, при программировании на языке Си можно сослаться на значение поля структурной переменной). Например, для того, чтобы сослаться на значение атрибута СОТР_ИМЯ переменной СОТРУДНИК, нужно употребить конструкцию СОТРУДНИК.СОТР_ИМЯ.

Правильно построенные формулы (WFF - Well-Formed Formula) служат для выражения условий, накладываемых на кортежные переменные. Основой WFF являются простые сравнения (comparison), представляющие собой операции сравнения скалярных значений (значений атрибутов переменных или литерально заданных констант). Например, конструкция "СОТРУДНИК.СОТР_НОМ = 140" является простым сравнением. По определению, простое сравнение является WFF, а WFF, заключенная в круглые скобки, является простым сравнением.

Более сложные варианты WFF строятся с помощью логических связок NOT, AND, OR и IF ... THEN. Так, если form - WFF, а comp - простое сравнение, то NOT form, comp AND form, comp OR form и IF comp THEN form являются WFF.

Наконец, в базе данных допускается построение WFF с помощью кванторов. Если form - это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) и FORALL var (form) представляют wff.

Переменные, входящие в WFF, могут быть свободными или связанными. Все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении WFF вида EXISTS var (form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием, var - это связанная переменная. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся ее область определения.

Пусть СОТР1 и СОТР2 - две кортежные переменные, определенные на отношении СОТРУДНИКИ. Тогда, WFF EXISTS СОТР2 (СОТР1.СОТР_ЗАРП > СОТР2.СОТР_ЗАРП) для текущего кортежа переменной СОТР1 принимает значение true в том и только в том случае, если во всем отношении СОТРУДНИКИ найдется кортеж (связанный с переменной СОТР2) такой, что значение его атрибута СОТР_ЗАРП удовлетворяет внутреннему условию сравнения. WFF FORALL СОТР2 (СОТР1.СОТР_ЗАРП > СОТР2.СОТР_ЗАРП) для текущего кортежа переменной СОТР1 принимает значение true в том и только в том случае, если для всех кортежей отношения СОТРУДНИКИ (связанных с переменной СОТР2) значения атрибута СОТР_ЗАРП удовлетворяют условию сравнения.

На самом деле, имея в виду отношения в базе данных правильнее говорить не о свободных и связанных переменных, а о свободных и связанных вхождениях переменных. Легко видеть, что если переменная var является связанной в WFF form, то во всех WFF, включающих данную, может использоваться имя переменной var, которая может быть свободной или связанной, но в любом случае не имеет никакого отношения к вхождению переменной var в WFF form. Вот пример:

  EXISTS СОТР2 (СОТР1.СОТР_ОТД_НОМ = СОТР2.СОТР_ОТД_НОМ) AND

    FORALL СОТР2 (СОТР1.СОТР_ЗАРП > СОТР2.СОТР_ЗАРП)

Здесь мы имеем два связанных вхождения переменной СОТР2 с совершенно разным смыслом.

2.2. Целевые списки и выражения реляционного исчисления

Итак, WFF обеспечивают средства формулировки условия выборки из отношений базы данных. Чтобы можно было использовать исчисление для реальной работы с базой данных, требуется еще один компонент, который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком (target_list).

Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:

  •  var.attr, где var - имя свободной переменной соответствующей WFF, а attr - имя атрибута отношения, на котором определена переменная var;
  •  var, что эквивалентно наличию подсписка var.attr1, var.attr2, ..., var.attrn, где attr1, attr2, ..., attrn включает имена всех атрибутов определяющего отношения;
  •  new_name = var.attr; new_name - новое имя соответствующего атрибута результирующего отношения.

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

Выражением реляционного исчисления кортежей в базе данных называется конструкция вида target_list WHERE wff. Значением выражения является отношение, тело которого определяется WFF, а набор атрибутов и их имена - целевым списком.

2.3. Реляционное исчисление доменов баз данных

В исчислении доменов областью определения переменных являются не отношения баз данных, а домены. Применительно к базе данных СОТРУДНИКИ-ОТДЕЛЫ можно говорить, например, о доменных переменных ИМЯ (значения - допустимые имена) или НОСОТР (значения - допустимые номера сотрудников).

Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства. Если R - это n-арное отношение с атрибутами a1, a2, ..., an, то условие членства имеет вид

  R (ai1:vi1, ai2:vi2, ..., aim:vim) (m <= n),

где vij - это либо литерально задаваемая константа, либо имя кортежной переменной. Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов. Если vij - константа, то на атрибут aij задается жесткое условие, не зависящее от текущих значений доменных переменных; если же vij - имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной.

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

Для примера сформулируем с использованием исчисления доменов запрос к базе данных "Выдать номера и имена сотрудников, не получающих минимальную заработную плату" (будем считать для простоты, что мы определили доменные переменные, имена которых совпадают с именами атрибутов отношения СОТРУДНИКИ, а в случае, когда требуется несколько доменных переменных, определенных на одном домене, мы будем добавлять в конце имени цифры):

   СОТР_НОМ, СОТР_ИМЯ WHERE EXISTS СОТР_ЗАРП1

     (СОТРУДНИКИ (СОТР_ЗАРП1) AND

      СОТРУДНИКИ (СОТР_НОМ, СОТР_ИМЯ, СОТР_ЗАРП) AND

      СОТР_ЗАРП > СОТР_ЗАРП1)

Реляционное исчисление доменов является основой большинства языков запросов, основанных на использовании форм. В частности, на этом исчислении базировался известный язык Query-by-Example, который был первым (и наиболее интересным) языком в семействе языков, основанных на табличных формах.




4.1.Реляционная модель данных

Реляционная модель предложена сотрудником компании IBM Е.Ф.Коддом в 1970 г. (русский перевод статьи, в которой она впервые описана опубликован в журнале "СУБД" N 1 за 1995 г.). В настоящее время эта модель является фактическим стандартом, на который ориентируются практически все современные коммерческие СУБД.

4.1.1.Структура данных.

В реляционной модели достигается гораздо более высокий уровень абстракции данных, чем в иерархической или сетевой. В упомянутой статье Е.Ф.Кодда утверждается, что "реляционная модель предоставляет средства описания данных на основе только их естественной структуры, т.е. без потребности введения какой-либо дополнительной структуры для целей машинного представления". Другими словами, представление данных не зависит от способа их физической организации. Это обеспечивается за счет использования математической теории отношений (само название "реляционная" происходит от английского relation - "отношение").

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

Определения: 

  •   Декартово произведение: Для заданных конечных множеств (не обязательно различных) декартовым произведением называется множество произведений вида: , где

Пример: если даны два множества A (a1,a2,a3) и B (b1,b2), их декартово произведение будет иметь вид С=A*B (a1*b1, a2*b1, a3*b1, a1*b2, a2*b2, a3*b2) 

  •   Отношение: Отношением R, определенным на множествах называется подмножество декартова произведения . При этом:
    •  множества называются доменами отношения
    •  элементы декартова произведения называются кортежами 
    •  число n определяет степень отношения ( n=1 - унарное, n=2 - бинарное, ..., n-арное)
    •  количество кортежей называется мощностью отношения 

Пример: на множестве С из предыдущего примера могут быть определены отношения R1 (a1*b1, a3*b2) или R2 (a1*b1, a2*b1, a1*b2) 

Отношения удобно представлять в виде таблиц. На рис. 4.1 представлена таблица (отношение степени 5), содержащая некоторые сведения о работниках гипотетического предприятия. Строки таблицы соответствуют кортежам. Каждая строка фактически представляет собой описание одного объекта реального мира (в данном случае работника), характеристики которого содержатся в столбцах. Можно провести аналогию между элементами реляционной модели данных и элементами модели "сущность-связь". Реляционные отношения соответствуют наборам сущностей, а кортежи - сущностям. Поэтому, также как и в модели "сущность-связь" столбцы в таблице, представляющей реляционное отношение, называют атрибутами.

Рис.4.1 Основные компоненты реляционного отношения.

 

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

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

Именнованное множество пар "имя атрибута - имя домена" называется схемой отношения. Мощность этого множества - называют степенью или "арностью" отношения. Набор именованных схем отношений представляет из себя схему базы данных.

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

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

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

Рис.4.2. База данных о подразделениях и сотрудниках предприятия.

 
 

Например, связь между отношениями ОТДЕЛ и СОТРУДНИК создается путем копирования первичного ключа "Номер_отдела" из первого отношения во второе. Таким образом:

  •  для того, чтобы получить список работников данного подразделения, необходимо
    1.  из таблицы ОТДЕЛ установить значение атрибута "Номер_отдела", соответствующее данному "Наименованию_отдела"
    2.  выбрать из таблицы СОТРУДНИК все записи, значение атрибута "Номер_отдела" которых равно полученному на предыдушем шаге.
  •  для того, чтобы узнать в каком отделе работает сотрудник, нужно выполнить обратную операцию:
    1.  определяем "Номер_отдела" из таблицы СОТРУДНИК
    2.  по полученному значению находим запись в таблице ОТДЕЛ.

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

4.1.2.Свойства отношений.

  1.  Отсутствие кортежей-дубликатов. Из этого свойства вытекает наличие у каждого кортежа первичного ключа. Для каждого отношения, по крайней мере, полный набор его атрибутов является первичным ключом. Однако, при определении первичного ключа должно соблюдаться требование "минимальности", т.е. в него не должны входить те атрибуты, которые можно отбросить без ущерба для основного свойства первичного ключа - однозначно определять кортеж. 
  2.  Отсутствие упорядоченности кортежей.
  3.  Отсутствие упордоченности атрибутов. Для ссылки на значение атрибута всегда используется имя атрибута.
  4.  Атомарность значений атрибутов, т.е. среди значений домена не могут содержаться множества значений (отношения).

Более подробно о фундаментальных свойствах отношений можно прочитать в "Введении в СУБД" С.Д.Кузнецова.


Следующая глава:
4.2.Теория нормальных форм 

    

Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

4.2.Теория нормальных форм.

4.2.1.Функциональные зависимости.

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

Определение: 

Если даны два атрибута X и Y некоторого отношения, то говорят, что Y функционально зависит от X, если в любой момент времени каждому значению X соответствует ровно одно значение Y. 

Функциональная зависимость обозначается X -> Y. Отметим, что X и Y могут представлять собой не только единичные атрибуты, но и группы, составленные из нескольких атрибутов одного отношения.

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

Некоторые функциональные зависимости могут быть нежелательны.

Определение: 

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

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

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

  •  не должны появляться ранее отсутствовавшие кортежи;
  •  на отношениях новой схемы должно выполняться исходное множество функциональных зависимостей.

4.2.2. 1NF - первая нормальная форма.

Для обсуждения первой нормальной формы необходимо дать два определения:

Простой атрибут - атрибут, значения которого атомарны (неделимы). 

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

Теперь можно дать

Определение первой нормальной формы: 

отношение находится в 1NF если значения всех его атрибутов атомарны. 

Рассмотрим пример, заимствованный из уже упоминавшейся статьи Е.Ф.Кодда:

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

СЛУЖАЩИЙ(НОМЕР_СЛУЖАЩЕГО, ИМЯ, ДАТА_РОЖДЕНИЯ, ИСТОРИЯ_РАБОТЫ, ДЕТИ).

Из внимательного рассмотрения этого отношения следует, что атрибуты "история_работы" и "дети" являются сложными, более того, атрибут "история_работы"  включает еще один сложный атрибут "история_зарплаты".
Данные агрегаты выглядят следующим образом:
 

  ИСТОРИЯ_РАБОТЫ (ДАТА_ПРИЕМА, НАЗВАНИЕ, ИСТОРИЯ_ЗАРПЛАТЫ), 

  ИСТОРИЯ_ЗАРПЛАТЫ (ДАТА_НАЗНАЧЕНИЯ, ЗАРПЛАТА), 

  ДЕТИ (ИМЯ_РЕБЕНКА, ГОД_РОЖДЕНИЯ). 

Их связь представлена на рис. 4.3.

Рис.4.3. Исходное отношение.

 
Для приведения исходного отношения СЛУЖАЩИЙ к первой нормальной форме необходимо декомпозировать его на четыре отношения, так как это показано на следующем рисунке:

Рис.4.4. Нормализованное множество отношений.

 

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

Алгоритм нормализации описан Е.Ф.Коддом следующим образом:

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

4.2.3. 2NF - вторая нормальная форма.

Очень часто первичный ключ отношения включает несколько атрибутов (в таком случае его называют составным) - см., например, отношение ДЕТИ, показанное на рис. 4.4. При этом вводится понятие полной функциональной зависимости.

Определение: 

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

Пусть имеется отношение ПОСТАВКИ (N_ПОСТАВЩИКА, ТОВАР,  ЦЕНА).
Поставщик может поставлять различные товары, а один и тот же товар может поставляться разными поставщиками. Тогда ключ отношения -
"N_поставщика + товар". Пусть все поставщики поставляют товар по одной и той же цене. Тогда имеем следующие функциональные зависимости:

  •  N_поставщика, товар -> цена 
  •  товар -> цена 

Неполная функциональная зависимость атрибута "цена" от ключа приводит к следующей аномалии: при изменении цены товара необходим полный просмотр отношения для того, чтобы изменить все записи о его поставщиках. Данная аномалия является следствием того факта, что в одной структуре данных объединены два семантических факта. Следующее разложение дает отношения во 2НФ:

  •  ПОСТАВКИ (N_ПОСТАВЩИКА, ТОВАР)
  •  ЦЕНА_ТОВАРА (ТОВАР, ЦЕНА)

Таким образом, можно дать

Определение второй нормальной формы: 

Отношение находится во 2НФ, если оно находится в 1НФ и каждый неключевой атрибут функционально полно зависит от ключа. 

4.2.4. 3NF - третья нормальная форма.

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

Определение: 

Пусть X, Y, Z - три атрибута некоторого отношения. При этом X --> Y и Y --> Z, но обратное
соответствие отсутствует, т.е. Z -/-> Y и Y -/-> X. Тогда  Z транзитивно зависит от X.
 
Пусть имеется отношение ХРАНЕНИЕ (
ФИРМА, СКЛАД, ОБЪЕМ), которое содержит информацию о фирмах, получающих товары со складов, и объемах этих складов. Ключевой атрибут - "фирма". Если каждая фирма может получать товар только с одного склада, то в данном отношении имеются следующие функциональные зависимости:

  •  фирма -> склад 
  •  склад -> объем 

При этом возникают аномалии:

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

Для устранения этих аномалий необходимо декомпозировать исходное отношение на два:

  •  ХРАНЕНИЕ (ФИРМА, СКЛАД)
  •  ОБЪЕМ_СКЛАДА (СКЛАД, ОБЪЕМ)

Определение третьей нормальной формы: 

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

4.2.5. BCNF - нормальная форма Бойса-Кодда.

Эта нормальная форма вводит дополнительное ограничение по сравнению с 3НФ.

Определение нормальной формы Бойса-Кодда: 

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

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

4.2.6. Многозначные зависимости и четвертая нормальная форма (4NF).

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

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

В качестве примера рассмотрим отношение ПРЕПОДАВАТЕЛЬ (ИМЯ, КУРС, УЧЕБНОЕ_ПОСОБИЕ), хранящее сведения о курсах, читаемых преодавателем, и написанных им учебниках. Пусть профессор N читает курсы "Теория упругости" и "Теория колебаний" и имеет соответствующие учебные пособия, а профессор K читает курс "Теория удара" и является автором учебников "Теория удара" и "Теоретическая механика". Тогда наше отношение будет иметь вид:

     ----------------------------------------------------

     | ИМЯ  |  КУРС            | УЧЕБНОЕ_ПОСОБИЕ        |

     ----------------------------------------------------

     |  N   | Теория упругости | Теория упругости       |

     |  N   | Теория колебаний | Теория упругости       |

     |  N   | Теория упругости | Теория колебаний       |

     |  N   | Теория колебаний | Теория колебаний       |

     |  K   | Теория удара     | Теория удара           |

     |  K   | Теория удара     | Теоретическая механика |

     ----------------------------------------------------

добавляем:

     ----------------------------------------------------

     |  K   | Теория упругости | Теория удара           |

     |  K   | Теория упругости | Теоретическая механика |

     ----------------------------------------------------

Это отношение имеет значительную избыточность и его использование приводит к возникновению аномалии обновления. Например, добавление информации о том, что профессор K будет также читать лекции по курсу "Теория упругости" приводит к необходимости добавить два кортежа (по одному для каждого написанного им учебника) вместо одного. Тем не менее, отношение ПРЕПОДАВАТЕЛЬ находится в NFBC (ключевой атрибут - ИМЯ).

Заметим, что указанные аномалии исчезают при замене отношения ПРЕПОДАВАТЕЛЬ его проекциями:

     ---------------------------      -------------------------------

     | ИМЯ  |  КУРС            |      | ИМЯ |   УЧЕБНОЕ_ПОСОБИЕ     |

     ---------------------------      -------------------------------

     |  N   | Теория упругости |      |  N  |Теория упругости       |

     |  N   | Теория колебаний |      |  N  |Теория колебаний       |

     |  K   | Теория удара     |      |  K  |Теоретическая механика |

     |  K   | Теория упругости |      |  K  |Теория удара           |

     ---------------------------      -------------------------------

Аномалия обновления возникает в данном случае потому, что в отношении ПРЕПОДАВАТЕЛЬ имеются:

  1.  зависимость множества значений атрибута КУРС от множества значений атрибута ИМЯ
  2.  зависимость множества значений атрибута УЧЕБНОЕ_ПОСОБИЕ от множества значений атрибута ИМЯ.

Такие зависимости и называются многозначными и обозначаются как

          ИМЯ ->> КУРС           ИМЯ ->> УЧЕБНОЕ_ПОСОБИЕ

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

            ИМЯ ->> КУРС | УЧЕБНОЕ_ПОСОБИЕ

Очевидно, что каждая функциональная зависимость является многозначной, но не каждая многозначная зависимость является функциональной.

Определение четвертой нормальной формы: 

Отношение находится в 4NF если оно находится в BCNF и в нем отстутсвуют многозначные зависимости, не являющиеся функциональными зависимостями. 

4.2.7. Зависимости по соединению и пятая нормальная форма (5NF).

До сих пор мы предполагали, что единственной операцией, необходимой для устранения избыточности в отношении, была декомпозиция его на две проекции. Однако, существуют отношения, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три (или более) проекций. Этот факт получил название зависимости по соединению, а такие отношения называют 3-декомпозируемые отношения (ясно, что любое отношение можно назвать "n-декомпозируемым", где n >= 2).

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

Определение пятой нормальной формы: 

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

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

Следующая глава: 4.3.Ограничения целостности. 




Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

4.3.Ограничения целостности

Целостность данных - это механизм поддержания соответствия базы данных предметной области. В реляционной модели данных определены два базовых требования обеспечения целостности:

  •  целостность ссылок
  •  целостность сущностей.

4.3.1.Целостность сущностей.

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

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

Вполне очевидно, что если данное требование не соблюдается (т.е. кортежи в рамках одного отношения не уникальны), то в базе данных может хранится противоречивая информация об одном и том же объекте.  Поддержание целостности сущностей обеспечивается средствами системы управления базой данных (СУБД). Это осуществляется с помощью двух ограничений:

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

4.3.2.Целостность ссылок

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

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

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

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

Пусть, например, даны отношения ОТДЕЛ (N_ОТДЕЛА, ИМЯ_ОТДЕЛА) и СОТРУДНИК (N_СОТРУДНИКА, N_ОТДЕЛА, ИМЯ_СОТРУДНИКА), в которых хранятся сведения о работниках предприятия и подразделениях, где они работают. Отношение ОТДЕЛ в данной паре является родительским, поэтому его первичный ключ "N_отдела" присутствует в дочернем отношении СОТРУДНИК. Требование целостности по ссылкам означает здесь, что в таблице СОТРУДНИК не может присутствовать кортеж со значением атрибута "N_отдела", которое не встречается в таблице ОТДЕЛ. Если такое значение в отношении ОТДЕЛ отсутствует,  значение внешнего ключа  в отношении СОТРУДНИК считается неопределенным.

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

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

Следующая глава: 4.4.Операции над данными (реляционная алгебра). 




Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

4.4.Операции над данными (реляционная алгебра).

4.4.0.Система управления базами данных LEAP

Для практического изучения команд реляционной алгебры здесь используется СУБД LEAP, разработанная Ричардом Лейтоном. Для того, чтобы закрепить свои знания: 

  1.  Изучите команды обработки отношений, которые описаны ниже на данной странице. Описание каждой команды приводится как в виде формального определения, так и в виде, поддерживаемом LEAP. 
  2.  Здесь находится более подробное описание возможностей СУБД LEAP. 
  3.  Здесь находится www-интерфейс к СУБД LEAP, посредством которого можно получить доступ к базе данных по печатным и электронным публикациям, касающихся темы данного курса. 
  4.  Здесь лежит список заданий, которые предлагается выполнить как средствами реляционной алгебры, так и средствами языка SQL. 

4.4.1.Операции обработки кортежей.

Эти операции связаны с изменением состава кортежей в каком-либо отношении.

  •  ДОБАВИТЬ - необходимо задать имя отношения и ключ кортежа.
  •  УДАЛИТЬ - необходимо указать имя отношения, а также идентифицировать кортеж или группу кортежей, подлежащих удалению.
  •  ИЗМЕНИТЬ - выполняется для названного отношения и может корректировать как один, так и несколько кортежей.

4.4.2.Операции обработки отношений.

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

В рассмотренных ниже примерах (которые заимствованы из книги Э.Озкарахан "Машины баз данных и управление базами данных" -М: "Мир", 1989) используются следующие отношения:

P(D1,D2,D3)  Q(D4,D5)   R(M,P,Q,T)     S(A,B)

1 11 x         x 1      x 101 5 a       5 a

2 11 y         x 2      y 105 3 a      10 b

3 11 z         y 1      z 500 9 a      15 c

 4 12 x                  w  50 1 b       2 d

                        w  10 2 b       6 a

                        w 300 4 b       1 b

В реляционной алгебре определены следующие операций обработки отношений:

  •  ПРОЕКЦИЯ (ВЕРТИКАЛЬНОЕ ПОДМНОЖЕСТВО).
    Операция проекции представляет из себя выборку из каждого кортежа отношения значений атрибутов, входящих в список A, и удаление из полученного отношения повторяющихся строк.

 

  •  ВЫБОРКА (ОГРАНИЧЕНИЕ, ГОРИЗОНТАЛЬНОЕ ПОДМНОЖЕСТВО).
    На входе используется одно отношение, результат - новое отношение, построенное по той же схеме, содержащее подмножество кортежей исходного отношения, удовлетворяющих условию выборки.

 

  •  ОБЪЕДИНЕНИЕ.
    Отношения-операнды в этом случае должны быть определены по одной схеме. Результирующее отношение содержит все строки операндов за исключением повторяющихся.

 

  •  ПЕРЕСЕЧЕНИЕ.
    На входе операции два отношения,  определенные по одной схеме. На выходе - отношение, содержащие кортежи, которые присутствуют в обоих исходных отношениях.

 

  •  РАЗНОСТЬ.
    Операция во многом похожая на ПЕРЕСЕЧЕНИЕ, за исключением того, что в результирующем отношении содержатся кортежи, присутствующие в первом и отсутствующие во втором исходных отношениях.

 

  •  ДЕКАРТОВО ПРОИЗВЕДЕНИЕ
    Входные отношения могут быть определены по разным схемам. Схема результирующего отношения включает все атрибуты исходных. Кроме того:
    •  степень результирующего отношения равна сумме степеней исходных отношений
    •  мощность результирующего отношения равна произведению мощностей исходных отношений.

 

  •  СОЕДИНЕНИЕ
    Данная операция имеет сходство с ДЕКАРТОВЫМ ПРОИЗВЕДЕНИЕМ. Однако, здесь добавлено условие, согласно которому вместо полного произведения всех строк в результирующее отношение включаются только строки, удовлетворяющие опредленному соотношению между атрибутами соединения
    1,A2) соответствующих отношений.

 

  •  ДЕЛЕНИЕ
    Пусть отношение
    R , называемое делимым, содержит атрибуты (A1,A2,...,An). Отношение S - делитель содержит подмножество атрибутов A: (A1,A2,...,Ak) (k<n). Результирующее отношение C определено на атрибутах отношения R, которых нет в S, т.е. Ak+1,Ak+2,...,An. Кортежи включаются в результирующее отношение C только в том случае, если его декартово произведение с отношением S содержится в делимом R.

Следующая глава: 4.5.Реляционное исчисление. 


   

Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

4.5.Реляционное исчисление.

В реляционной модели определяются два базовых механизма манипулирования данными:

  •  основанная на теории множеств реляционная алгебра
  •  основанное на математической логике реляционное исчисление.

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

Эти механизмы манипулирования данными различаются уровнем процедурности:

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


Пример:        Пусть даны два отношения: 

СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРПЛ, ОТД_НОМЕР)
ОТДЕЛЫ(ОТД_НОМЕР, ОТД_КОЛ, ОТД_НАЧ) 

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

(1).выполнить соединение отношений СОТРУДНИКИ и ОТДЕЛЫ по условию СОТР_НОМ = ОТДЕЛ_НАЧ. 


С1 = СОТРУДНИКИ [СОТР_НОМ = ОТД_НАЧ] ОТДЕЛЫ

(2).из полученного отношения произвести выборку по условию ОТД_КОЛ > 10 

С2 = С1 [ОТД_КОЛ > 10].

(3).спроецировать результаты предыдущей операции на атрибуты СОТР_ИМЯ, СОТР_НОМЕР 

С3 = С2 [СОТР_ИМЯ, СОТР_НОМЕР]

Заметим, что порядок выполнения шагов может повлиять на эффективность выполнения запроса. Так,  время выполнения приведенного выше запроса можно сократить, если поменять местами этапы (1) и (2). В этом случае сначала из отношения СОТРУДНИКИ будет сделана выборка всех кортежей со значением атрибута ОТДЕЛ_КОЛ > 10, а затем выполнено соединение результирующего отношения с отношением ОТДЕЛЫ. Машинное время экономится за счет того, что в операции соединения участвуют меньшие отношения.

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

Выдать СОТР_ИМЯ и СОТР_НОМ для СОТРУДНИКИ таких, что

существует ОТДЕЛ с таким же, что и СОТР_НОМ значением ОТД_НАЧ

и значением ОТД_КОЛ большим 50.

Здесь мы указываем лишь характеристики результирующего отношения, но не говорим о способе его формирования. СУБД сама должна решить какие операции и в каком порядке надо выполнить над отношениями СОТРУДНИКИ и ОТДЕЛЫ. Задача оптимизации выполнения запроса в этом случае также ложится на СУБД. 

Следующая глава: 4.6.Язык SQL. 


   

Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

4.6.Язык SQL

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

Язык SQL (эта аббревиатура должна произноситься как "сикуель", однако все чаще говорят "эс-ку-эль") в настоящее время является промышленным стандартом, который в большей или меньшей степени поддерживает любая СУБД, претендующая на звание "реляционной". В то же время SQL подвергается суровой критике как раз за недостаточное соответствие реляционным принципам (см. например, статью Х. Дарвина и К.Дейта Третий манифест, опубликованную в журнале СУБД N 1 за 1996 год).

Из истории SQL: 

В начале 70-х годов в компании IBM была разработана экспериментальная СУБД System R на основе языка SEQUEL (Structured English Qeury Language - структурированный английский язык запросов), который можно считать непосредственным предшественником SQL. Целью разработки было создание простого непроцедурного языка, которым мог воспользоваться любой пользователь, даже не имеющий навыков программирования. В 1981 году IBM объявила о своем первом, основанном на SQL программном продукте, SQL/DS. Чуть позже к ней присоединились Oracle и другие производители. Первый стандарт языка SQL был принят Американским национальным институтом стандартизации (ANSI) в 1987 (так называемый SQL level /уровень/ 1) и несколько уточнен в 1989 году (SQL level 2). Дальнейшее развитие языка поставщиками СУБД потребовало принятия в 1992 нового расширенного стандарта (ANSI SQL-92 или просто SQL-2). В настоящее время ведется работа по подготовке третьего стандарта SQL, который должен включать элементы объекто-ориентрованного доступа к данным.

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

В SQL определены два подмножества языка:

  •  SQL-DDL (Data Definition Language) - язык определения структур и ограничений целостности баз данных. Сюда относятся команды создания и удаления баз данных; создания, изменения и удаления таблиц; управления пользователями и т.д.
  •  SQL-DML (Data Manipulation Language) - язык манипулирования данными: добавление, изменение, удаление и извлечение данных, управления транзакциями

Здесь не дается строгое описание всех возможностей SQL-92. Во-первых, ни одна СУБД не поддерживает их в полной мере, а во-вторых, производители СУБД часто предлагают собственные расширения SQL, несовместимые друг с другом. Поэтому мы рассматриваем некое подмножество языка, которое дает общее представление о его специфике и возможностях. В то же время, этого подмножества достаточно, чтобы начать самостоятельную работу с любой СУБД. Более формальный (и более полный) обзор стандартов SQL сделан в статье С. Д. Кузнецова "Стандарты языка реляционных баз данных SQL: краткий обзор",журнал СУБД N 2, 1996 г. Ознакомится с русским переводом стандарта SQL можно на сервере Центра информационных технологий, сравнительное описание различных версий языка (для СУБД Sybase SQL Server, Sybase SQL Anywhere, Microsoft SQL Server, Informix, Oracle Server) приводится в книге Дж.Боуман, С.Эмерсон, М.Дарновски "Практическое руководство по SQL", Киев, Диалектика, 1997.

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

Все примеры построены применительно к базе данных publications, содержащей сведения о публикациях (как печатных, так и электронных), относящихся к теме данного курса. Структуру этой базы данных можно посмотреть здесь, ее проектирование описано в разделе 5.4, доступ к ней для практических занятий можно получить через Internet посредством СУБД Leap (реляционная алгебра) или СУБД PostgreSQL. (язык SQL).

4.6.1.Типы данных SQL.

  •  Символьные типы данных - содержат буквы, цифры и специальные символы.
    •  CHAR или CHAR(n) -символьные строки фиксированной длины. Длина строки определяется параметром n. CHAR без параметра соответсвует CHAR(1). Для хранения таких данных всегда отводится n байт вне зависимости от реальной длины строки.
    •  VARCHAR(n) - символьная строка переменной длины. Для хранения данных этого типа отводится число байт, соответствующее реальной длине строки.
  •  Целые типы данных - поддерживают только целые числа (дробные части и десятичные точки не допускаются). Над этими типами разрешается выполнять арифметические операции и применять к ним агрегирующие функции (определение максимального, минимального, среднего и суммарного значения столбца реляционной таблицы).
    •  INTEGER или INT- целое, для хранения которого отводится, как правило, 4 байта. (Замечание: число байт, отводимое для хранения того или иного числового типа данных зависит от используемой СУБД и аппаратной платформы, здесь приводятся наиболее "типичные" значения) Интервал значений от - 2147483647 до + 2147483648
    •  SMALLINT - короткое целое (2 байта), интервал значений от - 32767 до +32768
  •  Вещественные типы данных - описывают числа с дробной частью.
    •  FLOAT и SMALLFLOAT - числа с плавающей точкой (для хранения отводится обычно 8 и 4 байта соответсвенно).
    •  DECIMAL(p) - тип данных аналогичный FLOAT с числом значащих цифр p.
    •  DECIMAL(p,n) - аналогично предыдущему, p - общее количество десятичных цифр, n - количество цифр после десятичной запятой.
  •  Денежные типы данных - описывают, естественно, денежные величины. Если в ваша система такого типа данных не поддерживает, то используйте DECIMAL(p,n).
    •  MONEY(p,n) - все аналогично типу DECIMAL(p,n). Вводится только потому, что некоторые СУБД предусматривают для него специальные методы форматирования.
  •  Дата и время - используются для хранения даты, времени и их комбинаций. Большинство СУБД умеет определять интервал между двумя датами, а также уменьшать или увеличивать дату на определенное количество времени.
    •  DATE - тип данных для хранения даты.
    •  TIME - тип данных для хранения времени.
    •  INTERVAL - тип данных для хранения верменного интервала.
    •  DATETIME - тип данных для хранения моментов времени (год + месяц + день + часы + минуты + секунды + доли секунд).
  •  Двоичные типы данных - позволяют хранить данные любого объема в двоичном коде (оцифрованные изображения, исполняемые файлы и т.д.). Определения этих типов наиболее сильно различаются от системы к системе, часто используются ключевые слова:
    •  BINARY 
    •  BYTE 
    •  BLOB 
  •  Последовательные типы данных - используются для представления возрастающих числовых последовательностей.
    •  SERIAL - тип данных на основе INTEGER, позволяющий сформировать уникальное значение (например, для первичного ключа). При добавлении записи СУБД автоматически присваивает полю данного типа значение, получаемое из возрастающей последовательности целых чисел.

В заключение следует сказать, что для всех типов данных имеется общее значение NULL - "не определено". Это значение имеет каждый элемент столбца до тех пор, пока в него не будут введены данные. При создании таблицы можно явно указать СУБД могут ли элементы того или иного столбца иметь значения NULL (это не допустимо, например, для столбца, являющего первичным ключом).



Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

4.6.2.DDL: Операторы создания схемы базы данных.

При описании команд предполагается, что:

  •  текст, набранный строчными буквами (например, CREATE TABLE) является обязательным
  •  текст, набранный прописными буквами и заключенный в угловые скобки (например, <имя_базы_данных>) обозначает переменную, вводимую пользователем
  •  в квадратные скобки (например, [NOT NULL]) заключается необязательная часть команды
  •  взаимоисключающие элементы команды разделяются вертикальной чертой (например, [UNIQUE | PRIMARY KEY]).

Операторы базы данных

Команда

Описание

CREATE DATABASE <имя_базы_данных>

Создание базы данных.

DROP DATABASE <имя_базы_данных>

Удаление базы данных.

Создание и удаление таблиц


Создание таблицы:

 

  CREATE TABLE <имя_таблицы>

       (<имя_столбца> <тип_столбца>

                         [NOT NULL]

                         [UNIQUE | PRIMARY KEY]

                         [REFERENCES <имя_мастер_таблицы> [<имя_столбца>]]

         , ...)

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

  •  NOT NULL - в этом случае элементы столбца всегда должны иметь определенное значение (не NULL)
  •  один из взаимоисключающих параметров UNIQUE - значение каждого элемента столбца должно быть уникальным или PRIMARY KEY - столбец является первичным ключом.
  •  REFERNECES <имя_мастер_таблицы> [<имя_столбца>] - эта конструкция определяет, что данный столбец является внешним ключом и указывает на ключ какой мастер_таблицы он ссылается.

Контроль за выполнением указанных условий осуществляет СУБД.

Пример: создание базы данных publications: 

  CREATE DATABASE publications;

  CREATE TABLE authors (au_id INT PRIMARY KEY,

                        author VARCHAR(25) NOT NULL);

  CREATE TABLE publishers (pub_id INT PRIMARY KEY,

                           publisher VARCHAR(255) NOT NULL,url VARCHAR(255));

  CREATE TABLE titles (title_id INT PRIMARY KEY,

                       title VARCHAR(255) NOT NULL,

                       yearpub INT,

                       pub_id INT REFERENCES publishers(pub_id));

  CREATE TABLE titleautors (au_id INT REFERENCES authors(au_id),

                            title_id INT REFERENCES titles(title_id));

  CREATE TABLE wwwsites (site_id INT PRIMARY KEY,

                         site VARCHAR(255) NOT NULL,

                         url VARCHAR(255));

  CREATE TABLE wwwsiteauthors (au_id INT REFERENCES authors(au_id),

                               site_id INT REFERENCES wwwsites(site_id));

Удаление таблицы:
            DROP TABLE <имя_таблицы> 

Модификация таблицы: 

 

Добавить столбцы

ALTER TABLE <имя_таблицы> ADD   
           (<имя_столбца> <тип_столбца>   
                    [NOT NULL]   
                    [UNIQUE | PRIMARY KEY]  
                    [REFERENCES <имя_мастер_таблицы> [<имя_столбца>]]  
            ,...)

Удалить столбцы

ALTER TABLE <имя_таблицы> DROP (<имя_столбца>,...)

Модификация типа столбцов

ALTER TABLE <имя_таблицы> MODIFY  
           (<имя_столбца> <тип_столбца>  
                    [NOT NULL]  
                    [UNIQUE | PRIMARY KEY]  
                    [REFERENCES <имя_мастер_таблицы> <имя_столбца>]]  
            ,...)

 

4.6.3.DDL: Операторы создания индексов.

Создание индекса: 

   CREATE [UNIQUE] INDEX <имя_индекса> ON <имя_таблицы> (<имя_столбца>,...) 

Эта команда создает индекс с заданным именем для таблицы <имя_таблицы> по столбцам, входящим в список, указанный в скобках. Индекс часто представляет из себя структуру типа B-дерева (см. параграф 1.2), но могут использоваться и другие структуры. Создание индексов значительно ускоряет работу с таблицами. В случае указания необязательного параметра UNIQUE СУБД будет проверять каждое значение индекса на уникальность.

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

     CREATE INDEX au_names ON authors (author); 

Создание индексов для первичных ключей:

     CREATE INDEX au_index ON authors (au_id);
     CREATE INDEX title_index ON titles (title_id);
     CREATE INDEX pub_index ON publishers (pub_id);
     CREATE INDEX site_index ON wwwsites (site_id); 

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

Удаление индекса: 

       DROP INDEX <имя_индекса> 

4.6.4.DDL: Операторы управления правами доступа.

По соображениям безопасности не каждому пользователю прикладной системы может быть разрешено получать информацию из какой-либо таблицы, а тем более изменять в ней данные. Для определения прав пользователей относительно объектов базы данных (таблицы, представления, индексы) в SQL определена пара команд GRANT и REVOKE. Синтаксис операции передачи прав на таблицу:

   GRANT <тип_права_на_таблицу>

     ON  <имя_таблицы> [<список_столбцов>]

     TO  <имя_пользователя>

Права пользователя на уровне таблицы определяются следующими ключевыми словами (как мы увидим чуть позже эти ключевые слова совпадают с командами выборки и изменения данных):

  •  SELECT - получение информации из таблицы
  •  UPDATE - изменение информации в таблице
  •  INSERT - добавление записей в таблицу
  •  DELETE - удаление записей из таблицы
  •  INDEX - индексирование таблицы
  •  ALTER - изменение схемы определения таблицы
  •  ALL - все права

В поле <тип_права_на_таблицу> может быть указано либо ключевое слово ALL или любая комбинация других ключевых слов. Например, предоставим все права на таблицу publishers пользователю andy:

  GRANT ALL ON publishers TO andy;

Пользователю peter предоставим права на извлечение и дбавление записей на эту же таблицу:

  GRANT SELECT INSERT ON publishers TO peter;

В том случае, когда одинаковые права надо предоставить сразу всем пользователям, вместо выполнения команды GRANT для каждого из них, можно вместо имени пользователя указать ключевое слово PUBLIC:

  GRANT SELECT ON publishers TO PUBLIC;

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

  REVOKE <тип_права_на_таблицу>

     ON  <имя_таблицы> [<список_столбцов>]

     FROM  <имя_пользователя>

Все ключевые слова данной команды эквивалентны оператору GRANT.

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

   GRANT <тип_права_на_базу_данных>

     ON  <имя_базы данных>

     TO  <имя_пользователя>

К сожалению, способы задания прав на базу данных различны для разных СУБД, и точную их формулировку нужно уточнять в документации. В качестве примера приведем список прав на базу данных, поддерживаемых СУБД Informix:

  •  CONNECT - права на доступ к данным и их модификацию, если это разрешено на уровне таблицы;
  •  RESOURCE - права на управление ресурсами. Все перечисленное выше плюс права на создание новых объектов (таблиц, индексов и т.д.) и удаление и изменение тех объектов, которыми данный пользователь владеет;
  •  DBA - права на администрирование. Все права на управление ресурсами плюс права на удаление базы данных, удаление любых объектов, назначение и отмена прав других пользователей.

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

  REVOKE <тип_права_на_базу_данных> FROM  <имя_пользователя>



Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет

4.6.5.DML: Команды модификации данных.

К этой группе относятся операторы добавления, изменения и удаления записей.

Добавить новую запись в таблицу:

INSERT INTO <имя_таблицы> [ (<имя_столбца>,<имя_столбца>,...) ]

                               VALUES (<значение>,<значение>,..)

Список столбцов в данной команде не является обязательным параметром. В этом случае должны быть указаны значения для всех полей таблицы в том порядке, как эти столбцы были перечислены в команде CREATE TABLE, например:

     INSERT INTO publishers VALUES (16,"Microsoft Press","http://www.microsoft.com");

Пример с указанием списка столбцов:

     INSERT INTO publishers (publisher,pub_id) 

            VALUES ("Super Computer Publishing",17);

Модификация записей:

     UPDATE <имя_таблицы> SET <имя_столбца>=<значение>,...

         [WHERE <условие>]

Если задано ключевое слово WHERE и условие, то команда UPDATE применяется только к тем записям, для которых оно выполняется. Если условие не задано, UPDATE применяется ко всем записям. Пример:

     UPDATE publishers SET url="http://www.superpub.com" WHERE pub_id=17;

В качестве условия используются логические выражения над константами и полями. В условиях допускаются:

  •  операции сравнения: > , < , >= , <= , = , <> , != . В SQL эти операции могут применяться не только к числовым значениям, но и к строкам ( "<" означает раньше, а ">" позже в алфавитном порядке) и датам ( "<" раньше и ">" позже в хронологическом порядке).
  •  оперции проверки поля на значение NULL: IS NULL, IS NOT NULL 
  •  операции проверки на вхождение в диапазон: BETWEEN и NOT BETWEEN.
  •  операции проверки на вхождение в список: IN и NOT IN 
  •  операции проверки на вхождение подстроки: LIKE и NOT LIKE 
  •  отдельные операции соединяются связями AND, OR, NOT и группируются с помощью скобок.

Подробно все эти ключевые слова будут описаны и проиллюстрированы в параграфе, посвященном оператору SELECT. Здесь мы ограничимся приведением несложного примера:

     UPDATE publishers SET url="url not defined" WHERE url IS NULL;

Эта команда находит в таблице publishers все неопределенные значения столбца url и заменяет их строкой "url not defined".

Удаление записей

    DELETE FROM <имя_таблицы> [ WHERE <условие> ]

Удаляются все записи, удовлетворяющие указанному условию. Если ключевое слово WHERE и условие отстутствуют, из таблицы удаляются все записи. Пример:

    DELETE FROM publishers WHERE publisher = "Super Computer Publishing";

Эта команда удаляет запись об издательстве Super Computer Publishing.

4.6.6.DML: Выборка данных.

Для извлечения записей из таблиц в SQL определен оператор SELECT. С помощью этой команды осуществляется не только операция реляционной алгебры "выборка" (горизонтальное подмножество), но и предварительное соединение (join) двух и более таблиц. Это наиболее сложное и мощное средство SQL, полный синтаксис оператора SELECT имеет вид:

      SELECT [ALL | DISTINCT] <список_выбора>

           FROM <имя_таблицы>, ...

           [ WHERE <условие> ]

           [ GROUP BY <имя_столбца>,... ]

              [ HAVING <условие> ]

           [ORDER BY <имя_столбца> [ASC | DESC],... ]

Порядок предложений в операторе SELECT должен строго соблюдаться (например, GROUP BY должно всегда предшествовать ORDER BY), иначе это приведет к появлению ошибок.

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

Этот оператор всегда начинается с ключевого слова SELECT. В кострукции <список_выбора> определяется столбец или столбцы, включаемые в результат. Он может состоять из имен одного или нескольких столбцов, или из одного символа * (звездочка), определяющего все столбцы. Элементы списка разделяются запятыми.

Пример: получить список всех авторов

        SELECT author FROM authors;

получить список всех полей таблицы authors:

        SELECT * FROM authors;

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

        SELECT title FROM titles WHERE yearpub > 1996;

Допустим теперь, что нам надо найти все публикации за интервал 1995 - 1997 гг. Это условие можно записать в виде:

        SELECT title FROM titles WHERE yearpub>=1995 AND yearpub<=1997;

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

        SELECT title FROM titles WHERE yearpub BETWEEN 1995 AND 1997;

При использовании конструкции NOT BETWEEN находятся все строки, не входящие в указанный диапазон.

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

SELECT title FROM titles WHERE yearpub IN (1995,1996,1997);

Здесь мы задали в явном виде список интересующих нас значений. Конструкция NOT IN позволяет найти строки, не удовлетворяющие условиям, перечисленным в списке.

Наиболее полно преимущества ключевого слова IN проявляются во вложенных запросах, также называемых подзапросами. Предположим, нам нужно найти все издания, выпущенные компанией "Oracle Press". Наименования издательских компаний содержатся в таблице publishers, названия книг в таблице titles. Ключевое слово NOT IN позволяет объединить обе таблицы (без получения общего отношения) и извлечь при этом нужную информацию:

 SELECT title FROM titles WHERE pub_id IN

    (SELECT pub_id FROM publishers WHERE publisher='Oracle Press');

При выполнении этой команды СУБД вначале обрабатывает вложенный запрос по таблице publishers, а затем его результат передает на вход основного запроса по таблице titles.

Некоторые задачи нельзя решить с использованием только операторов сравнения. Например, мы хоти найти web-site издательтва "Wiley", но не знаем его точного наименования. Для решения этой задачи предназначено ключевое слово LIKE, его синтаксис имеет вид:

   WHERE <имя_столбца> LIKE <образец> [ ESCAPE <ключевой_символ> ]

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

  •  % (знак процента) - заменяет любое количество символов
  •  _ (подчеркивание) - заменяет одиночный символ.

Попробуем найти искомый web-site:

SELECT publiser, url FROM publishers WHERE publisher LIKE '%Wiley%';

В соотвествии с шаблоном СУБД найдет все строки включающие в себя подстроку "Wiley". Другой пример: найти все книги, название которых начинается со слова "SQL":

       SELECT title FROM titles WHERE title LIKE 'SQL%';

В том случае, когда надо найти значение, которое само содержит один из символов шаблона, используют ключевое слово ESCAPE и <ключевой_символ>. Литерал, следующий в шаблоне после ключевого символа, рассматривается как обычный символ, все последующие символы имеют обычное значение. Например, нам надо найти ссылку на web-страницу, о которой известно, что в ее url содержится подстрока "my_works":

      SELECT site, url FROM wwwsites WHERE url LIKE '%my@_works%' ESCAPE '@';

В заключение заметим, что при выполнении оператора SELECT результирующее отношение может иметь несколько записей с одинаковыми значениями всех полей. Чтобы исключить повторяющиеся записи из выборки используется ключевое слово DISTINCT. Ключевое слово ALL указывает, что в результат необходимо включать все строки.

4.6.7.DML: Выборка из нескольких таблиц.

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

------------------------------------------------

|название_книги | год_выпуска | издательство   |

------------------------------------------------

|               |             |                |

|               |             |                |

Для этого СУБД предварительно должна выполнить слияние таблиц titles и publishers, а только затем произвести выборку из полученного отношения.

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

    SELECT titles.title,titles.yearpub,publishers.publisher

        FROM titles,publishers

        WHERE titles.pub_id=publishers.pub_id;

А вот пример, где одновременно задаются условия и слияния, и выборки (результат предыдущего запроса ограничивается изданиями после 1996 года):

    SELECT titles.title,titles.yearpub,publishers.publisher

        FROM titles,publishers

        WHERE titles.pub_id=publishers.pub_id AND

              titles.yearpub>1996;

Следует обратить внимание на то, что когда в разных таблицах присутствуют одноименные поля, то для устранения неоднозначности перед именем поля указывается имя таблицы и знак "." (точка). (Хорошее правило: имя таблицы указывать всегда!)

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

 SELECT authors.author,titles.title,titles.yearpub,publishers.publisher

  FROM titles,publishers,titleauthors

  WHERE titleauthors.au_id=authors.au_id AND

        titleauthors.title_id=titles.title_id AND

        titles.pub_id=publishers.pub_id AND

        titles.yearpub > 1996;

4.6.8.DML: Вычисления внутри SELECT.

SQL позволяет выполнять различные арифметические операции над столбцами результирующего отношения. В конструкции <список_выбора> можно использовать константы, функции и их комбинации с арифметическими операциями и скобками. Например, чтобы узнать сколько лет прошло с 1992 года (год принятия стандарта SQL-92) до публикации той или иной книги можно выполнить команду:

     SELECT title, yearpub-1992 FROM titles WHERE yearpub > 1992;

В арифметических вражения допускаются операции сложения (+), вычитания (-), деления (/), умножения (*), а также различные функции (COS, SIN, ABS - абсолютное значение и т.д.). Также в запрос можно добавить строковую константу:

     SELECT 'the title of the book is', title, yearpub-1992 

            FROM titles WHERE yearpub > 1992;

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

  •  AVG(<имя поля>) - среднее по всем значениям данного поля
  •  COUNT(<имя поля>) или COUNT (*) - число записей
  •  MAX(<имя поля>) - максимальное из всех значений данного поля
  •  MIN(<имя поля>) - минимальное из всех значений данного поля
  •  SUM(<имя поля>) - сумма всех значений данного поля

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

          SELECT MIN(yearpub) FROM titles;

подсчитать количество книг в нашей базе данных:

          SELECT COUNT(*) FROM titles;

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

 SELECT COUNT(*) FROM titles WHERE title LIKE '%SQL%';

4.6.9.DML: Групировка данных.

Группировка данных в операторе SELECT осуществляется с помощью ключевого слова GROUP BY и ключевого слова HAVING, с помощью которого задаются условия разбиения записей на группы.

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

     SELECT publishers.publisher, count(titles.title)

         FROM titles,publishers

         WHERE titles.pub_id=publishers.pub_id

         GROUP BY publisher;

Kлючевое слово HAVING работает следующим образом: сначала GROUP BY разбивает строки на группы, затем на полученные наборы накладываются условия HAVING. Например, устраним из предыдущего запроса те издательства, которые имеют только одну книгу:

     SELECT publishers.publisher, count(titles.title)

        FROM titles,publishers

        WHERE titles.pub_id=publishers.pub_id

        GROUP BY publisher

          HAVING COUNT(*)>1;

Другой вариант использования HAVING - включить в результат только те издательтва, название которых оканчивается на подстроку "Press":

   SELECT publishers.publisher, count(titles.title)

        FROM titles,publishers

        WHERE titles.pub_id=publishers.pub_id

        GROUP BY publisher

           HAVING publisher LIKE '%Press';

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

4.6.10.DML: Cортировка данных.

Для сортировки данных, получаемых при помощи оператора SELECT служит ключевое слово ORDER BY. С его помощью можно сортировать результаты по любому столбцу или выражению, указанному в <списке_выбора>. Данные могут быть упорядочены как по возрастанию, так и по убыванию. Пример: сортировать список авторов по алфавиту:

SELECT author FROM authors ORDER BY author;

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

 SELECT authors.author,titles.title,titles.yearpub,publishers.publisher

      FROM authors,titles,publishers,titleauthors

      WHERE titleauthors.au_id=authors.au_id AND

            titleauthors.title_id=titles.title_id AND

             titles.pub_id=publishers.pub_id 

      ORDER BY authors.author ASC, titles.yearpub DESC;

Ключевое слово DESC задает здесь обратный порядок сортировки по полю yearpub, ключевое слов ASC (его можно опускать) - прямой порядок сортировки по полю author.

4.6.11.DML: Операция объединения.

В SQL предусмотрена возможность выполнения операции реляционной алгебры "ОБЪЕДИНЕНИЕ" (UNION) над отношениями, являющимися результатами оператора SELECT. Естественно, эти отношения должны быть определены по одной схеме.Пример: получить все Интеренет-ссылки, хранимые в базе данных publications. Эти ссылки хранятся в таблицах publishers и wwwsites. Для того, чтобы получить их в одной таблице, мы должны построить следующие запрос:

      SELECT publisher,url FROM publishers

      UNION

      SELECT site,url FROM wwwsites;

4.6.12.Использование представлений.

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

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

Когда содержимое базовых таблиц меняется, СУБД автоматически перевыполняет запросы, создающие view, что приводит к соответствующи изменениям в представлениях.

Представление определяется с помощью команды

     CREATE VIEW <имя_представления> [<имя_столбца>,...]

            AS <запрос>

При этом должны соблюдаться следующие ограничения:

  •  представление должно базироваться на единcтвенном запросе (UNION не допустимо)
  •  выходные данные запроса, формирующего представление, должны быть не упорядочены (ORDER BY не допустимо)

Создадим представление, хранящее информацию об авторах, их книгах и издателях этих книг:

 CREATE VIEW books AS

SELECT authors.author,titles.title,titles.yearpub,publishers.publisher

  FROM authors,titles,publishers,titleauthors

  WHERE titleauthors.au_id=authors.au_id AND

        titleauthors.title_id=titles.title_id AND

        titles.pub_id=publishers.pub_id

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

  SELECT titles FROM books WHERE author LIKE '%Date'

  SELECT author,count(title) FROM books GROUP BY author

(Права пользователей на доступ в представлениям назначаются также с помощью команд GRANT / REVOKE.)

Из приведенного выше примера достаточно ясен смысл использования представлений. Если запросы типа "выбрать все книги данного автора с указанием издательств" выполняются достаточно часто, то создание представляемой таблицы books значительно сократит накладные расходы на выполнение соединеия четырех базовых таблиц authors, titles, publishers и titleauthors. Кроме того, в представлении может быть представлена информация, явно не хранимая ни в одной из базовых таблиц. Например, один из столбцов представления может быть вычисляемым:

     CREATE VIEW amount (publisher, books_count) AS

     SELECT publishers.publisher, count(titles.title)

         FROM titles,publishers

         WHERE titles.pub_id=publishers.pub_id

         GROUP BY publisher;

Здесь использована еще одна, ранее не описанная, возможность SQL - присвоение новых имен столбцам представления. В приведенном примере число изданий, осуществленных каждым издатетлем, будет хранится в столбце с именем books_count. Заметим, что если мы хотим присвоить новые имена столбцам представления, нужно указывать имена для всех столбцов. Тип данных столбца представления и его нулевой статус всегда зависят от того, как он был определен в базовой таблице (таблицах).

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

  •  Если представление основано на одной таблице, изменения данных в нем допускаются. При этом изменяются данные в связанной с ним таблице.
  •  Если представление основано более чем на одной таблице, то изменения данных в нем не допускаются, т.к. в большинстве случаев СУБД не может правильно восстановить схему базовых таблиц из схемы представления.

Удаление представления производится с помощью оператора:

   DROP VIEW <имя_представления>

4.6.13.Другие возможности SQL.

Описываемые ниже возможности пока не стандартизованы, но представлены в той или иной мере практически во всех современных СУБД.

  •  Хранимые процедуры. Практический опыт создания приложений обработки данных показывает, что ряд операций над данными, реализующих общую для всех пользователей логику и не связанных с пользовательским интерфейсом, целесообразно вынести на сервер. Однако, для написания процедур, реализующих эти операции стандартных возможностей SQL не достаточно, поскольку здесь необходимы операторы обработки ветвлений, циклов и т.д. Поэтому многие поставщики СУБД предлагают собственные процедурные расширения SQL (PL/SQL компании Oracle и т.д.). Эти расширения содержат логические операторы (IF ... THEN ... ELSE), операторы перехода по условию (SWITCH ... CASE ...), операторы циклов (FOR, WHILE, UNTIL) и операторы предачи управления в процедуры (CALL, RETURN). С помощью этих средств создаются функциональные модули, которые хранятся на сервере вместе с базой данных. Обычно такие модули называют хранимые процедуры. Они могут быть вызваны с передачей параметров любым пользователем, имеющим на то соотвествующие права. В некоторых системах хранимые процедуры могут быть реализованы и в виде внешних по отношению к СУБД модулей на языках общего назначения, таких как C или Pascal. Пример для СУБД PostgreSQL:
  •  
  •            CREATE FUNCTION <имя_функции> ([<тип_параметра1>,...<тип_параметра2>])
  •                RETURNS <возвращаемые_типы>
  •                AS [ <SQL_оператор> | <имя_объектного_модуля> ]

             LANGUAGE 'SQL' | 'C' | 'internal'

Вызов созданной функции осуществялется из оператора SELECT (также, как вызываются функции агрегирования). Более подробно о хранимых процедурах см. статью Э.Айзенберга Новый стандарт хранимых процедур в языке SQL, СУБД N 5-6, 1996 г.

  •  Триггеры. Для каждой таблицы может быть назначена хранимая процедура без параметров, которая вызывается при выполнении оператора модификации этой таблицы (INSERT, UPDATE, DELETE). Такие хранимые процедуры получили название триггеров. Триггеры выполняются автоматически, независимо от того, что именно является причиной модификации данных - действия человека оператора или прикладной программы. "Усредненный" синтаксис оператора создания триггера:
  •  
  •             CREATE TRIGGER <имя_триггера>
  •                      ON <имя_таблицы>
  •                      FOR { INSERT | UPDATE | DELETE }
  •                           [, INSERT | UPDATE | DELETE ] ...

                   AS <SQL_оператор>

Ключевое слово ON задает имя таблицы, для которой определяется триггер, ключевое слово FOR указывает какая команда (команды) модификации данных активирует триггер. Операторы SQL после ключевого слова AS описывают действия, которые выполняет триггер и условия выполнения этих действий. Здесь может быть перечислено любое число операторов SQL, вызовов хранимых процедур и т.д. Использование триггеров очень удобно для выполнения операций контроля ограничений целостности (см. главу 4.3).

  •  Мониторы событий. Ряд СУБД допускает создание таких хранимых процедур, которые непрерывно сканируют одну или несколько таблиц на предмет обнаружения тех или иных событий (например, среднее значение какого-либо столбца достигает заданного предела). В случае наступления события может быть инициирован запуск триггера, хранимой процедуры, внешнего модуля и т.п. Пример: пусть наша база данных является частью автоматизированной системы управления технологическим процессом. В поле одной из таблиц заносятся показания датчика температуры, установленного на резце токарного станка. Когда это значение превышает заданный предел, запускается внешняя программа, изменяющая параметры работы станка.



Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет

4.7.Вопросы практического програмирования.

В этой главе рассматриваются некоторые способы создания приложений, работающих с базой данных при помощи языка SQL. Как правило, любой поставщик СУБД предоставляет вместе со своей системой внешнюю утилиту, которая позволяет вводить операторы SQL в режиме командной строки и выдает на консоль результаты их выполнения (так, как это сделано на этой страничке, предоставляющей интерактивный доступ к БД publications). Недостатки такого режима работы очевидны: необходимо знать SQL, необходимо помнить схему БД, отсутствует возможность удобного просмотра результатов выполнения запросов. Поэтому, подобные утилиты стали инструментами администраторов баз данных, а для создания пользовательских приложений используются универсальные и специализированные языки программирования. Приложения, написанные таким образом, позволяют пользователю сосредоточиться на решении собственных задач, а не на структурах данных.

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

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

При этом предполагется, что каждая часть приложения функционирует на отдельном компьютере, т.е. к выделенному серверу БД с помощью локальной сети подключены персональные компьютеры пользователей (клиенты). Это наиболее популярная сегодня схема организации вычислительной среды. Более подробно архитектура "клиент-сервер" и различные способы ее реализации будут обсуждаться в главе 7.

Язык SQL позволяет только манипулировать данными, но в нем отсутствуют средства создания экранного интерфейса, что необходимо для пользовательских приложений. Для создания этого интерфейса служат универсальные языки третьего поколения (C, C++, Pascal) или проблемно-ориентированные языки четвертого поколения (xBase, Informix 4Gl, Progress, Jam,...). Эти языки содержат необходимые операторы ввода / вывода на экран, а также операторы структурного программирования (цикла, ветвтеления и т.д.). Также эти языки допускают определение структур, соответствующих записям таблиц обрабатываемой базы данных. В исходный текст программы включаются операторы языка SQL, которые во время исполнения передаются серверу БД, который собственно и производит манипулирование данными. Отношения, полученные в результате выполнения сервером SQL-запросов, возвращаются прикладной программе, которая заполняет строками этих отношений заранее определенные структуры. Дальнейшая работа клиентской программы (отображение, корректировка записей) ведется с этими структурами.

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

4.7.1.Использование специализированных библиотек и встраиваемого SQL.

Каждая СУБД помимо интерактивной SQL-утилиты обязательно имеет библиотеку доступа и набор драйверов для различных операционных систем. Схема взаимодействия клиентского приложения с сервером базы данных в этом случае выглядит так:

Библиотека доступа - это, как правило, объектный файл, исходный код которого создан на универсальном языке типа C. Эта библиотека содержит набор функций, позволяющих пользовательскому приложению соединятся с базой данных, передавать запросы серверу и получать ответные данные. Типичный набор функций такой библиотеки (имена функций зависят от используемой библиотеки):

  •  DB_connect(char *имя_базы_данных, char *имя_пользователя, char *пароль) - устанавливает соединение с базой данной, возвращает указатель на структуру db, описывающую характеристики этого соединения
  •  DB_exec(db, char *запрос) - выполнить запрос к базе данных, определяемой структурой db. Применяется для любых запросов кроме SELECT. Возвращает код выполнения запроса (0 - удачно, либо код ошибки)
  •  DB_select(db, char *запрос) - выполнить запрос на извлечение данных (SELECT). Возвращает структуру result, содержащую результаты выполнения запроса (реляционное отношение).
  •  DB_fetch(result) - извлечь следующую запись из структуры result.
  •  DB_close(db) - закрыть соединение с базой данных.

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

   #include <dblib.h>     /* Файл, содержащий описание функций библиотеки */

   ........

   /* Организация интерфейса с пользователем, запрос его имени и пароля */

   /* Присвоение значений переменным:  dbname - имя базы данных         */

   /*                                  username - имя пользователя      */

   /*                                  password - пароль                */

   .........

   db=DB_connect(dbname,username,password); /* Установление соединения */

   if (db == NULL) {

        error_message();  /* Выдача сообщения об ошибке на монитор пользователя */

        exit(1);          /* Завершение работы */

   }

   ..........

   /* Ожидание запроса пользователя. Формирование строки s_query - запроса */

   /* на выборку данных                                                    */

   ..........

   result=DB_select(db,s_query);     /* Пересылка запроса на сервер */

   if (result==NULL) {

         error_message();  /* Ошибка выполнения запроса. Выдача сообщения */

         exit(2);          /* Завершение работы */

   }

   ..........

   /* Вывод результатов запроса на монитор пользователя. Ожидание следующего  */

   /* запроса. Подготовка строки u_query="UPDATE ... SET ...", содержащей     */

   /* запрос на изменение данных.                                             */

   ..........

   res=DB_exec(db,u_query);      /* Пересылка запроса на сервер */

   if (res != 0 ) {     

         error_message();  /* Ошибка выполнения запроса. Выдача сообщения */

         exit(2);          /* Завершение работы */

   }

   ..........

   ..........

   DB_close(db);        /*Завершение работы */

Данная программа, обеспечивающая взаимодействие пользователя с СУБД, компилируется совместно с библиотекой доступа. Библиотечные вызовы преобразуются драйвером базы данных в сетевые вызовы и передаются сетевым программным обеспечением на сервер.

На сервере происходит обратный процесс преобразования: сетевые пакеты -> функции библиотеки -> SQL-запросы, запросы обрабатываются, их результаты передаются клиенту.

Как видим, такой способ создания приложений чрезвычайно гибок, позволяет реализовать практически любое приложение, но в то же время имеет явные недостатки:

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

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

Некоторой модификацией данного способа является использование "встроенного" языка SQL. В этом случае в текст программы на языке третьего поколения включаются не вызовы библиотек, а непосредственно предложения SQL, которые предваряются ключевым выражением "EXEC SQL". Перед компиляцией в машинный код такая программа обрабатывается препроцессором, который транслирует смесь операторов "собственного" языка СУБД и операторов SQL в "чистый" исходный код. Затем коды SQL замещаются вызовами соответствующих процедур из библиотек исполняемых модулей, служащих для поддержки конкретного варианта СУБД.

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

4.7.2.CLI - интерфейс уровня вызовов.

Большим достижением явилось появление (1994 г.) в стандарте SQL интерфейса уровня вызова - CLI (Call Level Interface), в котором стандартизован общий набор рабочих процедур, обеспечивающий совместимость со всеми основными серверами баз данных. Ключевой элемент CLI - специальная библиотека для компьютера-клиента, в которой хранятся вызовы процедур и большинство часто используемых сетевых компонентов для организации связи с сервером. Это ПО поставляется разработчиком средств SQL, не является универсальным и поддерживает разнообразные транспортные протоколы.

Использование программных вызовов позволяет свести к минимуму операции на компьютере-клиенте. В общем случае клиент формирует оператор языка SQL в виде строки и пересылает ее на сервер посредством процедуры исполнения (execute). Когда же сервер в качестве ответа возвращает несколько строк данных, клиент считывает результат с помощью серии вызовов процедуры выборки данных. Далее информация из столбцов полученной таблицы может быть связана с соответствующими переменными приложения. Вызов специальной процедуры позволяет клиенту определить считанное число строк, столбцов и типы данных в каждом столбце.

Интерфейс CLI построен таким образом, что перед передачей запроса серверу клиент не должен заботиться о типе оператора SQL, будь то выборка, обновление, удаление или вставка.

4.7.3.ODBC - открытый интерфейс к базам данных на платформе MS WIndows.

Очень важный шаг к созданию переносимых приложений обработки данных сделала фирма Microsoft, опубликовавшая в 1992 году спецификацию ODBC (Open Database Connetcivity - открытого интерфейса к базам данных), предназначенную для унификации доступа к данным с персональных компьютеров работающих под управлением операционной системы Windows. (Заметим, что ODBC опирается на спецификации CLI). Структурная схема доступа к данным с использованием ODBC:

ODBC представляет из себя программный слой, унифицирующий интерфейс приложений с базами данных. За релизацию особенностей доступа к каждой отдельной СУБД отвечает специальный ODBC-драйвер. Пользовательское приложение этих особенностей не видит, т.к. взаимодействует с универсальным программным слоем более высокого уровня. Таким образом, приложение становится в значительной степени независимым от СУБД. Однако, этот способ также не лишен недостатков:

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

4.7.4.JDBC - мобильный интерфейс к базам данных на платформе Java.

JDBC (Java DataBase Connectivity) - это интерфейс прикладного программирования (API) для выполнения SQL-запросов к базам данных из программ, написанных на языке Java. Напомним, что язык Java, созданный компанией Sun, является платформенно - независимым и позволяет создавать как собственно приложения (standalone application), так и программы (апплеты), встраиваемые в web-страницы. Более подробная информация о Java и связанных с ним технологиях находится на серверах java.sun.ru.

JDBC во многом подобен ODBC (см. рисунок), также построен на основе спецификации CLI, однако имеет ряд замечательных отличий. Во-первых, приложение загружает JDBC-драйвер динамически, следовательно администрирование клиентов упрощается, более того, появляется возможность переключаться на работу с другой СУБД без перенастройки клиентского рабочего места. Во-вторых, JDBC, как и Java в целом, не привязан к конкретной аппаратной платформе, следовательно проблемы с переносимостью приложений практически снимаются. В-третьих, использование Java-приложений и связанной с ними идеологии "тонких клиентов" обещает снизить требования к оборудованию клиентских рабочих мест.

Более подробно спецификация JDBC рассмотрена а статье С.Орлика "Обзор спецификации JDBC", СУБД N 3, 1997 г. Полный текст спецификации (на английском языке) находится по адресу java.sun.com/jdbc/.

Литература:

  •  Мартин Грабер. Введение в SQL.-М.:Лори,1996.
  •  Дж.Боуман, С.Эмерсон, М.Дарновски. Практическое руководство по SQL.-Киев: Диалектика,1997.

Следующая глава: 4.8.Навигационный подход к манипулированию данными и персональные СУБД. 



Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет

4.8.Навигационный подход к манипулированию данными и персональные СУБД.

Обсуждая вопрос практического написания приложений, взаимодействующих с реляционными базами данных (см. раздел 4.7.1), мы обнаружили один любопытный факт: для пользовательского приложения очень важна обработка не реляционного отношения в целом, как множества неупорядоченных строк, а именно каждой отдельной строки. Для этого служат функции DB_next, DB_prev и прочие, позволяющие перемещаться по строкам. При этом возможен доступ к значениям полей только одной строки, той которая является "текущей". Такой подход к манипулированию данными, при котором пользователь (или его программа) явно различает "предыдущие" и "последующие" строки и может управлять перемещением указателя от одной строки к другой, получил название навигационного (напомним, что навигационный подход типичен для сетевых и иерархических СУБД).

Ясно, что без навигационного подхода при создании клиентского приложения обойтись невозможно, в то же время для взаимодействия с сервером базы данных предлагается язык SQL как более эффективный. Однако, существует ряд СУБД, в которых навигационный подход распространен и на манипулирование хранимыми данными. Такие системы (dBase, FoxPro, Paradox) появились в начале 80-х годов и были предназначены для создания небольших однопользовательских приложений.

Рассмотрим кратко язык xBase, который поддерживается такими СУБД как dBase, FoxPro, Clipper и, возможно, некоторыми другими. Помимо собственно процедурных операторов (цикл, условие и т.п.) он включает операторы создания пользовательского интерфейса (меню, окна, экранные формы,...). Для работы с данными служит следующий набор команд:

  •  USE <имя_таблицы> - открыть таблицу. При этом одна строка таблицы считается "текущей". К полям "текущей" строки можно обращаться по их именам.
  •  GO [ TOP | BOTTOM ] - сделать "текущей" первую / последнюю запись таблицы.
  •  SKIP - сделать текущей следующую запись.
  •  REPLACE <имя_столбца> WITH <значение> [,<имя_столбца> WITH <значение> ...] - изменить значения полей текущей записи

Существуют также команды экранного редактирования записей (EDIT, BROWSE), поиска данных в таблице (FIND) и другие. Приведем пример небольшой программы на языке xBase, которая распечатывает таблицу authors, а затем добаляет в нее новую строку:

USE AUTHORS                  /* Открыть таблицу authors */

GO TOP                       /* Перейти на первую запись */

DO WHILE .NOT.EOF()          /* Выполнять цикл пока не будет достигнут конец таблицы */

 PRINT AUTHOR                 /* Напечатать содержимое поля author */

 SKIP                         /* Перейти на следующую запись */

ENDDO                        /* Конец цикла */

APPEND BLANK        /* Добавить пустую запись. Она автоматически становится текущей */

REPLACE AU_ID WITH 90, AUTHOR WITH "L.Pinter" /* Изменить значения полей текущей записи */

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

С развитием компьютерных сетей персональные СУБД стали переходить в разряд многопользовательских. При этом файлы данных размещались на разделяемом сетевом диске. Однако, создание достаточно больших приложений (10-20 одновременно работаюших пользователей) показало, что в этом случае резко снижается производительность и возникают проблемы с поддержанием целостности (точнее с изоляцией пользователей, подробнее см. следующий параграф). Поэтому, в настоящее время практически все персональные СУБД дополнены средствами доступа к SQL-серверам (как правило, с использованием ODBC). Теперь они могут служить не только средством для создания небольших локальных приложений, но и для разработки клиентских рабочих мест в архитектуре "клиент-сервер".

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



Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

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

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

  •  В банковской системе производится перевод денежных средств с одного счета на другой. На языке SQL эта операция описывается последовательностью двух команд UPDATE:
  •                    UPDATE accounts SET summa=summa-1000 WHERE account="PC_1"

                 UPDATE accounts SET summa=summa+1000 WHERE account="PC_2"

Как видим, после выполнения первой команды и до завершения второй команды база данных не находится в целостном состоянии (искомая сумма списана с первого счета, но не зачислена на второй). Если в этот момент в системе произойдет сбой (например, выключение электропитания), то целостное состояние БД будет безвозвратно утеряно.

  •  Целостность БД может нарушаться и во время обработки одной команды SQL. Пусть выполняется операция увеличения зарплаты всех сотрудников фирмы на 20%:

                  UPDATE employers SET salary=salary*1.2

При этом СУБД последовательно обрабатывает все записи, подлежащие обновлению, т.е. существует временной интервал, когда часть записей содержит новые значения, а часть - старые.

Во избежание таких ситуаций в СУБД вводится понятие транзакции - атомарного действия над БД, переводящего ее из одного целостного состояния в другое целостное состояние. Другими словами, транзакция - это последовательность операций, которые должны быть или все выполнены или все не выполнены (все или ничего).

Методом контроля за транзакциями является ведение журнала, в котором фиксируются все изменения, совершаемые транзакцией в БД. Если во время обработки транзакции происходит сбой, транзакция откатывается - из журнала восстанавливаеться состояние БД на момент начала транзакции.

В СУБД различных поставщиков начало транзакции может задаваться явно (например, командой BEGIN TRANSACTION), либо предполагаться неявным (так определено в стандарте SQL), т.е. очередная транзакция открывается автоматически сразу же после удачного или неудачного завершения предыдущей. Для завершения транзакции обычно используют команды SQL:

  •  COMMIT - успешно завершить транзакцию
  •  ROLLBACK - откатить транзакцию, т.е. вернуть БД в состояние, в котором она находилась на момент начала транзакции.

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

  1.  оператор COMMIT означает успешное завершение транзакции, все изменения, внесненные в базу данных делаются постоянными
  2.  оператор ROLLBACK прерывает транзакцию и отменяет все внесенные ею изменения
  3.  успешное заверешение программы, инициировавшей транзакцию, означает успешное завершение транзакции (как использование COMMIT)
  4.  ошибочное завершение программы прерывает транзакцию (как ROLLBACK)

Пример явно заданной транзакции: 

        BEGIN TRANSACTION;              /* Начать транзакцию */

        DELETE ...;                     /* Изменения */

        UPDATE ...;                     /* данных    */

        if (обнаружена_ошибка) ROLLBACK;

        else COMMIT;                    /* Завершить транзакцию */

Пример неявно заданной транзакции: 

        СOMMIT;                    /* Окончание предыдущей транзакции */

        DELETE ...;                     /* Изменения */

        UPDATE ...;                     /* данных    */

        if (обнаружена_ошибка) ROLLBACK;

        else COMMIT;                    /* Завершить транзакцию */

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

  •  Грязное чтение (Dirty Read) - транзакция Т1 модифицировала некий элемент данных. После этого другая транзакция Т2 прочитала содержимое этого элемента данных до завершения транзакции Т1. Если Т1 заврешается операцией ROLLBACK, то получается, что транзакция Т2 прочитала не существующие данные.
  •  Неповторяемое (размытое) чтение (Non-repeatable or Fuzzy Read) - транзакция Т1 прочитала содержимое элемента данных. После этого другая транзакция Т2 модифицировала или удалила этот элемент. Если Т1 прочитает содержимое этого элемента занова, то она получит другое значение или обнаружит, что элемент данных больше не существует.
  •  Фантом (фиктивные элементы) (Phantom) - транзакция Т1 прочитала содержимое нескольких элементов данных, удовлетворяющих некому условию. После этого Т2 создала элемент данных, удовлетворяющий этому условию и зафиксировалась. Если Т1 повторит чтение с тем же условием, она получит другой набор данных.

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

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

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

  •  блокировка со взаимным доступом, называемая также S-блокировкой (от Shared locks) и блокировкой по чтению.
  •  монопольная блокировка (без взаимного доступа), называемая также X-блокировкой от (eXclusive locks) или блокировкой по записи. Этот режим используется при операциях изменения, добавления и удаления объектов.

При этом:

  •  если транзакция налагает на объект X-блокировку, то любой запрос другой транзакции с блокировкой этого объекта будет отвергнут.
  •  если транзакция налагает на объект S-блокировку, то
    •  запрос со стороны другой транзакции с X-блокировокй на этот объект будет отвергнут
    •  запрос со стороны другой транзакции с S-блокировокй этого объекта будет принят

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

Доказано, что сериализуемость транзакций (или, иначе, их изоляция) обеспечивается при использовании двухфазного протокола блокировок (2LP - Two-Phase Locks), согласно которому все блокировки, произведенные транзакцией, снимаются только при ее завершении. Т.е выполение транзакции разбивается на две фазы: (1) - накопление блокировок, (2) - освобождение блокировок в результате фиксации или отката.

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

  •  блокируется вся база данных - очевидно, этот вариант неприемлим, поскольку сводит многопользовательский режим работы к однопользовательскому
  •  блокируются отдельные таблицы
  •  блокируются страницы (страница - фрагмент таблицы размером обычно 2-4 Кб, единица выделения памяти для обработки данных системой)
  •  блокируются записи
  •  блокируются отдельные поля

Современные СУБД, как правило, могут осуществлять блокировку на уровне записей или страниц.

Язык SQL также предоставляет способ косвенного управления скоростью выполения транзакций с помощью указания уровня изоляции транзакции. Под уровнем изоляции транзакции понимается возможность возникновения одной из описанных выше ошибочных ситуаций. В стандарте SQL определены 4 уровня изоляции:

Уровень изоляции

Грязное чтение

Размытое чтение

Фантом

Незафиксированное чтение
(READ UNCOMMITTED)

возможно

возможно

возможно

Зафиксированное чтение
(READ COMMITED)

невозможно

возможно

возможно

Повторяемое чтение
(REPEATABLE READ)

невозможно

невозможно

возможно

Сериализуемость
(SERIALIZABLE)

невозможно

невозможно

невозможно

Для определения характеристик транзакции используется оператор 

  SET TRANSACTION <режим_доступа>, <уровень_изоляции>

Список уровней изоляции приведен в таблице. Режим доступа по умолчанию используется READ WRITE (чтение запись), если задан уровень изоляции READ UNCOMMITED, то режим доступа должен быть READ ONLY (только чтение).

Одним из наиболее серьезных недостатков метода сериализации транзакций на основе механизма блокировок является возможность возникновения тупиков (dead locks) между транзакциями. Пусть, например, транзакция Т1 наложила монопольную блокировку на объект О1 и претендует на доступ к объекту О2, который уже монопольно заблокирован транзакцией Т2, ожидающей доступа к объекту О1. В этом случае ни одна из транзакций продолжаться не может, следовательно, блокировки объектов О1 и О2 никогда не будут сняты. Естественного выхода из такой ситуации не существует, поэтому тупиковые ситуации обнаруживаются и устраняются искусственно. При этом СУБД откатывает одну из транзакций, попавших в тупик ("жертвует" ею), что дает возможность продолжить выполнение другой транзакции.

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

Литература:

  •  К.Дж.Дейт Введение в системы баз данных (6 изд.). Киев, Диалектика, 1998 (главы 13 и14)
  •  С.Д.Кузнецов Введение в СУБД (главы 9 и 10), СУБД N 3, 1996, с.136-144.

Следующая глава: 4.10.Как определить степень соответствия СУБД реляционной модели. 



Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

4.10.Как определить степень соответствия СУБД реляционной модели.

Заврешая обсуждение моделей данных подведем некоторые итоги. Преимущества реляционного подхода достаточно очевидны:

  1.  Предсказуемость результатов работы с данными. В основе реляционной модели лежит математическая модель, следовательно, любой запрос к базе данных, составленный на корректном языке влечет ответ, однозначно определяемый схемой БД и конкретными данными. При этом пользователю не требуется информация о физической организации данных.
  2.  Предметная область часто достаточно естественно описывается в терминах таблиц (к сожалению, в реляционной модели имеются проблемы с представлением иерархических структур, подробнее см. раздел 5.5.3.

По этим причинам идея создания реляционной СУБД стала популярна среди разработчиков вскоре после ее появления. Сейчас существует множество коммерческих и некоммерческих систем, создатели которых заявляют об их "реляционности". Для того, чтобы более определенно сформулировать цель, к которой разработчикам нужно стремится, Е.Кодд в конце 70-х годов опубликовал 12 правил соответствия реляционной модели, которые опираются на основное (подразумеваемое) правило:

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

Конкретные требования к реляционной СУБД раскрываются в следующих правилах (цитируется по статье В.Пржиялковский Модели, базы данных и СУБД в информационных системах):

  1.  Информационное правило. Вся информация, хранимая в базе данных, должна быть представлена единственным образом: в виде значений в реляционных таблицах.
  2.  Правило гарантированного логического доступа. К каждому имеющемуся в реляционной базе атомарному значению должне быть гарантирован доступ с помощью указания имени таблицы, значения первичного ключа и имени атрибута.
  3.  Правило наличия значения (missing information). В полностью реляционной СУБД должны иметься специальные индикаторы (отличные от пустой символьной строки или строки из одних пробелов и отличные от нуля или какого-то другого числового значения) для выражения (на логическом уровне, не зависимо от типа данных) того факта, что значение отсутствует по меньшей мере по двум различным причинам: его действительно нет, либо оно не применимо к данной позиции. СУБД должна не только отражать этот факт, но и распространять на такие индикаторы свои функции манипулирования данными не зависимо от типа данных.
  4.  Правило динамического диалогового реляционного какталога. Описание базы данных выглядит логически как обычные данные, так что авторизованные пользователи и прикладные программы могут употреблять для работы с этим описанием тот же реляционный язык, что и при работе с обычными данными.
  5.  Правило полноты языка работы с данными. Сколько бы много в СУБД ни поддерживалось языков и режимов работы с данными, должен иметься по крайней мере один язык, выразимый в виде командных строк в некотором удобном синтаксисе, который бы позволял формулировать:
    •  определение данных
    •  определение правил целостности
    •  манипулирование данными (в диалоге и из программы)
    •  определение таблиц-представлений (в том числе и возможности их модификации)
    •  определение правил авторизации
    •  границы транзакций
  6.  Правило модификации таблиц-представлений. В СУБД должен существовать корректный алгоритм, позволяющий автоматически для каждой таблицы-представления определять во время ее создания, может ли она использоваться для вставки и удаления строк и какие из столбцов допускают модификацию, и заносящий полученную таким образом информацию в системный каталог.
  7.  Правило множественности операций. Возможность оперирования базовыми таблицами или таблицами-представлениями распространяется полностью не только на выдачу информации из БД, но и на вставку, модификацию и удаление данных.
  8.  Правило физической независимости. Диалоговые операторы и прикладные программы на логическом уровне не должны страдать от каких-либо изменений во внутреннем хранении данных или методах доступа СУБД
  9.  Правило логической независимости. Диалоговые операторы и прикладные программы на логическом уровне не должны страдать от таких изменений в базовых таблицах, которые сохраняют информацию и теоретически допускают неизменность этих операторов и программ.
  10.  Правило сохранения целостности. Диалоговые операторы и прикладные программы не должны изменяться при изменении правил целостности в БД, задаваемых языком работы с данными и хранимых в системном каталоге.
  11.  Правило независимости от распределенности. Диалоговые операторы и прикладные программы на логическом уровне не должны зависеть от совершаемого физического разнесения данных (если первоначально СУБД работала с нераспределенными данными) или перераспределения (если СУБД распределенная).
  12.  Правило ненарушения реляционного языка. Если в реляционной СУБД имеется язык низкого уровня (для работы с отдельными строками), он не должен позволять нарушать или "обходить" правила, сформулированные на языке высокого уровня (множественном) и занесенные в системный каталог.

Следующая глава: 5.Проектирование реляционных баз данных. 



Введение в базы данных. (c) Зеленков Ю.А. (yz@yars.free.net) 1997 г.

(c) Центр Интернет ЯрГУ

Реляционные базы данных

Задача длительного хранения и обработки информации появилась практически сразу с появлением первых компьютеров. Для решения этой задачи в конце 60-х годов были разработаны специализированные программы, получившие название систем управления базами данных (СУБД). СУБД проделали длительный путь эволюции от системы управления файлами, через иерархические и сетевые базы данных. В конце 80-х годов доминирующей стала система управления реляционными базами данных (СУРБД). С этого времени такие СУБД стали стандартом де-факто, и для того, чтобы унифицировать работу с ними, был разработан структурированный язык запросов (SQL), который представляет собой язык управления именно реляционными базами данных.

Замечание

Взаимодействие с базой данных происходит при помощи Системы Управления Базой Данных (СУБД), которая расшифровывает запросы и производит операции с информацией в базе данных. Поэтому более правильно было бы говорить о запросе к СУБД и о взаимодействии с СУБД из Web-приложения. Но так как это несколько усложняет восприятие, далее везде мы будем говорить "база данных", подразумевая при этом СУБД.

Существуют следующие разновидности баз данных:

  •  иерархические;
  •  реляционные;
  •  объектно-ориентированные;
  •  гибридные.

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

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

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

Гибридные СУБД совмещают в себе возможности реляционных и объектно-ориентированных баз данных.

В Web-приложениях, как правило, используются реляционные базы данных. Мы будем рассматривать пример базы данных, на которой основано большинство форумов, в том числе и тот, который мы далее будем разрабатывать. В этой базе хранится информация об авторах форума (authors), о названиях форумов (forums), о темах форума (themes) и, собственно, сами сообщения (posts). Таким образом, наша база данных будет включать следующие таблицы:

Таблица 1 Таблицы базы данных Forum.

authors

forums

posts

themes

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

Таблица 2 Структура реляционной базы данных.

 

ряд

 

 

строка

id_forum

name

Description

 

1

дизайн

Обсуждаются вопросы дизайна

 

2

MySQL

Обсуждаются вопросы, связанные с MySQL

 

3

PHP

Обсуждаются вопросы, связанные с PHP

 

4

разное

Другие вопросы

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

Каждый столбец таблицы forums представляет один элемент данных для каждого из форумов. Столбец id_forum содержит уникальный идентификатор форума, столбец name содержит название форума и столбец description содержит краткое описание проблемы, обсуждаемой на форуме.

Кратко особенности реляционной базы данных можно описать следующим образом:

  •  Данные хранятся в таблицах, состоящих из столбцов и строк;
  •  На пересечении каждого столбца и строчки стоит в точности одно значение;
  •  У каждого столбца есть своё имя, которое служит его названием, и все значения в одном столбце имеют один тип. Например, в столбце id_forum все значения имеют целочисленный тип, а в строке name - текстовый;
  •  Столбцы располагаются в определённом порядке, который определяется при создании таблицы, в отличие от строк, которые располагаются в произвольном порядке. В таблице может не быть не одной строчки, но обязательно должен быть хотя бы один столбец;

Запросы к базе данных возвращают результат в виде таблиц, которые тоже могут выступать как объект запросов.


 

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

56119. «Сміхові» вправи в системі здоров’язберігаючих технологій 69.5 KB
  Сміх йде від здоров’я. Тому діти і сміються таким тотальним сміхом. Одним з малорозвинених напрямків здоровязберігаючих технологій є напрямок вправ зі сміхом.
56121. Тренінгове заняття «Що я знаю про СНІД» 87.5 KB
  Мета: сформувати у підлітків розуміння власної відповідальності за ризик інфікування ВІЛ та ІПСШ; сприяти зміні мотивації статевої поведінки підлітків на користь репродуктивного здоровя та індивідуального захисту від ВІЛ; систематизувати знання про шляхи передачі ВІЛ...
56122. ПРОФІЛАКТИКА ВІЛ/СНІДу 70.5 KB
  Мета уроку: Розглянути теоретичні основи та практичні способи профілактики ВІЛ-інфекції СНІДу; ознайомити учнів з розповсюдженням ВІЛ СНІД в Україні; Навчити учнів оцінювати ступінь ризику захворювання; Розвивати вміння аналізувати робити висновки...
56123. ЕКОНОМІКА ПІДПРИЄМСТВА 248 KB
  Мета заняття: Навчальна: економічно обґрунтоване визначення величини затрат для виробництва і збуту продукції. Методичне забезпечення: Роздатковий матеріал 2 компоненти: вправа для розпізнання термінів; економічний...
56124. Собівартість продукції, її структура. Витрати на виробництво продукції 135.5 KB
  Вивчення теми «Собівартість продукції, її структура. Витрати на виробництво продукції» в рамках усієї дисципліни сприяє формування у студентів вмінь та знань щодо структури собівартості, витрат на виробництво продукції...
56125. Содержание понятия нормирование труда 57 KB
  Нормирование труда - это установление норм затрат труда на изготовление единицы продукции или выработки количества продукции в единицу времени различают следующие основные виды норм: нормы времени; нормы выработки...
56126. Закріплення теоретичного матеріалу по знаках альтерації й вокально-інтонаційних, метро-ритмічних навичок на прикладі знайомих поспівок і пісень 55.5 KB
  Учні повинні довідатися по перших 8 тактах пісню – звучить пісня «Паровоз» Г.Ернесакса у виконанні педагога. Спів групою 1-го куплету пісні. Після цього діти повинні «зіграти» на паперових клавіатурах мелодію заспіву пісні від «ре», від « до», від «фа» з проспівуванням нотами водночас.