СУБД

х годах появилось несколько систем, среди которых IDMS.

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

иерархических структурах запись-потомок должна иметь в точности одного

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

Сетевая БД состоит из набора записей и набора связей между этими записями,

а если говорить более точно, из набора экземпляров каждого типа из

заданного в схеме БД набора типов записи и набора экземпляров каждого типа

из заданного набора типов связи. Тип связи определяется для двух типов

записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра

типа записи предка и упорядоченного набора экземпляров типа записи потомка.

Для данного типа связи L с типом записи предка P и типом записи потомка C

должны выполняться следующие два условия:

1. Каждый экземпляр типа P является предком только в одном экземпляре L;

2. Каждый экземпляр C является потомком не более, чем в одном экземпляре L.

На формирование типов связи не накладываются особые ограничения; но

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

1. Тип записи потомка в одном типе связи L1 может быть типом записи предка

в другом типе связи L2 (как в иерархии).

2. Данный тип записи P может быть типом записи предка в любом числе типов

связи.

3. Данный тип записи P может быть типом записи потомка в любом числе типов

связи.

4. Может существовать любое число типов связи с одним и тем же типом записи

предка и одним и тем же типом записи потомка; и если L1 и L2 - два типа

связи с одним и тем же типом записи предка P и одним и тем же типом

записи потомка C, то правила, по которым образуется родство, в разных

связях могут различаться.

5. Типы записи X и Y могут быть предком и потомком в одной связи и потомком

и предком - в другой.

6. Предок и потомок могут быть одного типа записи.

Пример:

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

1. Найти конкретную запись в наборе однотипных записей (инженера Сидорова);

2. Перейти от предка к первому потомку по некоторой связи (к первому

сотруднику отдела 310);

3. Перейти к следующему потомку в некоторой связи (от Сидорова к Иванову);

4. Перейти от потомка к предку по некоторой связи (найти отдел Сидорова);

5. Создать новую запись;

6. Уничтожить запись;

7. Модифицировать запись;

8. Включить в связь;

9. Исключить из связи;

10. Переставить в другую связь и т.д.

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

В принципе их поддержание не требуется, но иногда требуют целостности по

ссылкам (как в иерархической модели).

11,12.Общие понятия реляционного подхода к организации БД.

Основными понятиями реляционных баз данных являются тип данных, домен,

атрибут, кортеж, первичный ключ и отношение.

Тип данных.

Понятие тип данных в реляционной модели данных полностью адекватно понятию

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

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

специализированных числовых данных (таких как "деньги"), а также

специальных "темпоральных" данных (дата, время, временной интервал).

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

систем абстрактными типами данных.

Домен.

Понятие домена более специфично для баз данных, хотя и имеет некоторые

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

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

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

применяемого к элементу типа данных. Если вычисление этого логического

выражения дает результат "истина", то элемент данных является элементом

домена. Наиболее правильной интуитивной трактовкой понятия домена является

понимание домена как допустимого потенциального множества значений данного

типа.

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

Схема отношения - это именованное множество пар {имя атрибута, имя домена

(или типа, если понятие домена не поддерживается)}. Степень или "арность"

схемы отношения - мощность этого множества. Схема БД (в структурном смысле)

- это набор именованных схем отношений.

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

Кортеж, соответствующий данной схеме отношения, - это множество пар {имя

атрибута, значение}, которое содержит одно вхождение каждого имени

атрибута, принадлежащего схеме отношения. "Значение" является допустимым

значением домена данного атрибута (или типа данных, если понятие домена не

поддерживается). Тем самым, степень или "арность" кортежа, т.е. число

элементов в нем, совпадает с "арностью" соответствующей схемы отношения.

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

Отношение - это множество кортежей, соответствующих одной схеме отношения.

Иногда, чтобы не путаться, говорят "отношение-схема" и "отношение-

экземпляр", иногда, схему, отношения называют заголовком отношения, а

отношение как набор кортежей - телом отношения.

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

Наиболее распространенная трактовка реляционной модели данных, по-видимому,

принадлежит Дейту, который воспроизводит ее (с различными уточнениями)

практически во всех своих книгах. Согласно Дейту реляционная модель состоит

из трех частей, описывающих разные аспекты реляционного подхода:

структурной части, манипуляционной части и целостной части.

В структурной части модели фиксируется, что единственной структурой данных,

используемой в реляционных БД, является нормализованное n-арное отношение.

По сути дела, в предыдущих двух разделах этой лекции мы рассматривали

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

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

манипулирования реляционными БД - реляционная алгебра и реляционное

исчисление. Первый механизм базируется в основном на классической теории

множеств (с некоторыми уточнениями), а второй - на классическом логическом

аппарате исчисления предикатов первого порядка. Мы рассмотрим эти механизмы

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

функцией манипуляционной части реляционной модели является обеспечение меры

реляционности любого конкретного языка реляционных БД: язык называется

реляционным, если он обладает не меньшей выразительностью и мощностью, чем

реляционная алгебра или реляционное исчисление.

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

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

требования целостности, которые должны поддерживаться в любой реляционной

СУБД. Первое требование называется требованием целостности сущностей.

Объекту или сущности реального мира в реляционных БД соответствуют кортежи

отношений. Конкретно требование состоит в том, что любой кортеж любого

отношения отличим от любого другого кортежа этого отношения, т.е. другими

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

Второе требование называется требованием целостности по ссылкам. При

соблюдении нормализованности отношений сложные сущности реального мира

представляются в реляционной БД в виде нескольких кортежей нескольких

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

характеризуют сущности, представленные кортежами некоторого другого

отношения (т.е. задают значения их первичного ключа). Говорят, что

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

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

целостности по ссылкам, или требование внешнего ключа состоит в том, что

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

в отношении, на которое ведет ссылка, должен найтись кортеж с таким же

значением первичного ключа, либо значение внешнего ключа должно быть

неопределенным (т.е. ни на что не указывать).

Ограничения целостности сущности и по ссылкам должны поддерживаться СУБД.

Для соблюдения целостности сущности достаточно гарантировать отсутствие в

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

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

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

удаление кортежа, на который существуют ссылки (т.е. сначала нужно либо

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

их внешнего ключа). При втором подходе при удалении кортежа, на который

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

автоматически становится неопределенным. Наконец, третий подход (каскадное

удаление) состоит в том, что при удалении кортежа из отношения, на которое

ведет ссылка, из ссылающегося отношения автоматически удаляются все

ссылающиеся кортежи.

14.B – дерево.

Видимо, наиболее популярным подходом к организации индексов в базах данных

является использование техники B-деревьев. С точки зрения внешнего

логического представления B-дерево - это сбалансированное сильно ветвистое

дерево во внешней памяти. Сбалансированность означает, что длина пути от

корня дерева к любому его листу одна и та же. Ветвистость дерева - это

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

точки зрения физической организации B-дерево представляется как

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

соответствует блок внешней памяти (страница). Внутренние и листовые

страницы обычно имеют разную структуру. В типовом случае структура

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

При этом выдерживаются следующие свойства:

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

предыдущем подразделе, то видно, что домены атрибутов результирующего

отношения однозначно определяются доменами отношений-операндов.

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

Смысл операции объединения в реляционной алгебре в целом остается теоретико-

множественным. Но если в теории множеств операция объединения осмысленна

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

результатом операции объединения должно являться отношение. Если допустить

в реляционной алгебре возможность теоретико-множественного объединения

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

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

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

относительно понятия отношения, то такая операция объединения является

бессмысленной.

Все эти соображения приводят к появлению понятия совместимости отношений по

объединению: два отношения совместимы по объединению в том и только в том

случае, когда обладают одинаковыми заголовками. Более точно, это означает,

что в заголовках обоих отношений содержится один и тот же набор имен

атрибутов, и одноименные атрибуты определены на одном и том же домене.

Если два отношения совместимы по объединению, то при обычном выполнении над

ними операций объединения, пересечения и взятия разности результатом

операции является отношение с корректно определенным заголовком,

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

Заметим, что включение в состав операций реляционной алгебры трех операций

объединения, пересечения и взятия разности является, очевидно, избыточным,

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

Тем не менее, Кодд в свое время решил включить все три операции, исходя из

интуитивных потребностей потенциального пользователя системы реляционных

БД, далекого от математики.

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

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

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

составленные из элементов первого и второго множеств. Поскольку отношения

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

прямого произведения. Но результат не будет отношением! Элементами

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

Поэтому в реляционной алгебре используется специализированная форма

операции взятия прямого произведения - расширенное прямое произведение

отношений. При взятии расширенного прямого произведения двух отношений

элементом результирующего отношения является кортеж, являющийся

конкатенацией (или слиянием) одного кортежа первого отношения и одного

кортежа второго отношения.

Понятие совместимости по взятию расширенного прямого произведения. Два

отношения совместимы по взятию прямого произведения в том и только в том

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

два отношения могут быть сделаны совместимыми по взятию прямого

произведения путем применения операции переименования к одному из этих

отношений.

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

заметить, что все четыре операции являются ассоциативными. Т. е., если

обозначить через OP любую из четырех операций, то (A OP B) OP C = A (B OP

C), и следовательно, без введения двусмысленности можно писать A OP B OP C

(A, B и C - отношения, обладающие свойствами, требуемыми для корректного

выполнения соответствующей операции). Все операции, кроме взятия разности,

являются коммутативными, т.е. A OP B = B OP A.

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

Операция ограничения требует наличия двух операндов: ограничиваемого

отношения и простого условия ограничения. Простое условие ограничения может

иметь либо вид (a comp-op b), где а и b - имена атрибутов ограничиваемого

отношения, для которых осмысленна операция сравнения comp-op, либо вид (a

comp-op const), где a - имя атрибута ограничиваемого отношения, а const -

литерально заданная константа.

Операция взятия проекции также требует наличия двух операндов -

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

отношения A.

Результатом проекции отношения A по списку атрибутов a1, a2, ..., an

является отношение, с заголовком, определяемым множеством атрибутов a1, a2,

..., an, и с телом, состоящим из кортежей вида

таких, что в отношении 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 с заголовком {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 имеются кортежи

множество значений {w} включает множество значений атрибута b в отношении

B.

18.Реляционное исчисление кортежей.

Предположим, что мы работаем с базой данных, обладающей схемой СОТРУДНИКИ

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

ОТД_НАЧ), и хотим узнать имена и номера сотрудников, являющихся

начальниками отделов с количеством сотрудников больше 50.

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

то мы получили бы алгебраическое выражение, которое читалось бы, например,

следующим образом:

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

ОТД_НАЧ;

ограничить полученное отношение по условию ОТД_КОЛ 50;

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

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

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

тот же запрос с использованием реляционного исчисления, которому

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

прочитать, например, следующим образом: Выдать СОТР_ИМЯ и СОТР_НОМ для

сотрудников таких, что существует отдел с таким же значением ОТД_НАЧ и

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

Во второй формулировке мы указали лишь характеристики результирующего

отношения, но ничего не сказали о способе его формирования. В этом случае

система должна сама решить, какие операции и в каком порядке нужно

выполнить над отношениями СОТРУДНИКИ и ОТДЕЛЫ. Обычно говорят, что

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

выполнения запроса, а логическая - описательной (или декларативной),

поскольку она всего лишь описывает свойства желаемого результата. Как мы

указывали в начале лекции, на самом деле эти два механизма эквивалентны и

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

другой.

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

Реляционное исчисление является прикладной ветвью формального механизма

исчисления предикатов первого порядка. Базисными понятиями исчисления

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

значений и понятие правильно построенной формулы, опирающейся на

переменные, предикаты и кванторы.

В зависимости от того, что является областью определения переменной,

различаются исчисление кортежей и исчисление доменов. В исчислении кортежей

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

допустимым значением каждой переменной является кортеж некоторого

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

домены, на которых определены атрибуты отношений базы данных, т.е.

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

Мы рассмотрим более подробно исчисление кортежей, а в конце лекции коротко

опишем особенности исчисления доменов.

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

не удастся избежать использования некоторого конкретного синтаксиса,

который мы, тем не менее, формально определять не будем. Необходимые

синтаксические конструкции будут вводиться по мере необходимости. В

совокупности, используемый синтаксис близок, но не полностью совпадает с

синтаксисом языка баз данных 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 с совершенно разным

смыслом.

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

Итак, 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, а набор атрибутов и их имена - целевым списком.

Реляционное исчисление доменов.

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

а домены. Применительно к базе данных СОТРУДНИКИ-ОТДЕЛЫ можно говорить,

например, о доменных переменных ИМЯ (значения - допустимые имена) или

НОСОТР (значения - допустимые номера сотрудников).

Основным формальным отличием исчисления доменов от исчисления кортежей

является наличие дополнительного набора предикатов, позволяющих выражать

так называемые условия членства. Если 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, который был первым (и наиболее

интересным) языком в семействе языков, основанных на табличных формах.

Страницы: 1, 2