Ю. А. Григорьев, Г. И. Ревунков - Банки данных

2. Модели данных

Это множество всех кортежей, состоящих из к элементов — по одному из каждого домена Д:

Например, если

Z), = {А, 2}, D2 = {Д С}, А = {4, 5, D}, то А: = 3 и соответственно

D = D,xD2xD,= {(А, 5, 4), (^, 5, 5), (^, Д Z)), (А, С, 4), (^, С, 5), (А, С, /)), (2, В, 4), (2, 5, 5), (2, 5, Z)), (2, С, 4), (2, С, 5), (2, С, Z))},

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

Отношением R на множествах D\, Di, ..., Д называется подмножество декартова произведения D\ х Di х ... х Dk. Иными словами, отношение Л, определенное на множествах D\, Di, ..., Dk (причем не обязательно, чтобы эти множества были различными), есть некоторое множество кортежей ар­ ности к\

<dy , d^	, ..., d,^ >,
таких, что б/, принадлежит D\, d^	принадлежит Di и т.д.:
RQD^XDJX	... xDb

Элементами отношения являются кортежи. Арность кортежа опреде­ ляет арность отношения. Отношения арности 1 часто называют унарным, арности 2 — бинарным, арности 3 — тернарным, арности к — ^-арным. Поскольку отношение есть множество, в нем не должны встречаться одина­ ковые кортежи и, кроме того, порядок кортежей в отношении несуществен.

Укажем в данном примере несколько отношений:

R, = {{А, В, 4), (А, С, 4)} с /), X D2 X А ;

/?2={(2,C,5)}eAxD2xZ)3;

R, =	{(2,	С, DI (А, 5, 5), {А, Д		4), (2, 5, D)} QD^XDJX	Д ;
R, = {(А, 5, 4), (А, 5, 5), (А, Д				Z)), (А, С, 4), (А, С, 5),..., (2, С, D)} с
	QD\	X Djx	Д ;
/?5 =	0 е	Z), X Д	X Д .

В ряде случаев отношение удобно представлять как таблицу, где каж­ дая строка — это кортеж, а каждый столбец соответствует одному и тому же компоненту декартова произведения (т.е. в нем могут появляться только элементы из соответствующего домена). Таблица, представляющая ^-арное отношение 7?, обладает следующими свойствами:

•каждая строка представляет собой кортеж из к значений, принадле­ жащих к столбцам;

•порядок столбцов фиксирован (1, 2,..., к);

70

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

•порядок строк безразличен;

•любые две строки различаются хотя бы одним элементом;

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

Использование отношений для представления данных. Для пред­ ставления данных математическое отношение используется двояко:

•для представления набора объектов (напомним, что набор объектов представляет собой группу подобных объектов);

•для представления связей между наборами объектов.

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

Пусть имеется:

1) набор объектов Е

Е= {ей 62,..., ^„ ..., в«};

2)множество атрибутов, описывающих набор

Л= {А\, А2, •--')Лр ..., Л;,,};

3)множество значений по каждому атрибуту (которые этот атрибут может принимать):

Кх = {А:ц, ^12, ..., ^1,, } по атрибуту .4,;

К2 = {k2i, к22, ..., к^,^ } по атрибуту ^2;

Кп, = {кпц, кп,^, ..., к^„^^^ } по атрибуту ^„,.

При выполнении интерпретации объявляем, что:

1) 1-й столбец отношения соответствует атрибуту А и 2-й столбец от­ ношения — атрибутуу^2; •••; ^-й столбец отношения — атрибуту^;,,.

2) каждому атрибуту соответствует домен:

D\ = К], D2 = К2,...,	Dm = К„^;
3) отношение
7? е Z)i X /)2 X ••• X DfTj = К]	X К2Х ... х Кщ

описывает набор объектов Е.

Вэтом отношении R будет п кортежей — по числу объектов в наборе

Е.Каждый кортеж г, отношения R описывает отдельный объект Ci из набора объектов Е.

Если атрибуте/ (или совокупность атрибутов {А],А2, ..., А.}) является ключом, то значение в столбце / (или совокупность значений из столбцов 1, 2, ..., z) некоторой строки отношения R однозначно идентифицирует эту

71

2. Модели данных

строку (кортеж) в данном отношении. Таким образом, по значению ключа всегда найдем в отношении кортеж, описывающий интересующий нас объ­ ект. Например, нас интересует описание объекта //„. Известно, что значение ключа Aj для этого объекта равно kjy Находим в отношении R строку, у ко­ торой в столбце j находится значение kjy Это и будет искомое описание

объекта e^.

Отношение также используется для представления связей между на­ борами объектов Е], El,..., Ek^

Кортеж г, в отношении R в этом случае обозначает список объектов:

''' = <Ч'I ' % Ч' •• 'К

где	\	е £", = = '{^11.е\2,'
		еЕг-- = {^21,1 ^ 2 2 »
	%		^'2
	%	е Ek = {^ki. Skj,	"'1

•' \ Ь

•••' ч ^' ••' ч ^

Чтобы реализовать такую ситуацию, каждому столбцу отношения R ставят в соответствие ключевой атрибут соответствующего набора объектов. Например, 1-й столбец соответствует ключевому атрибуту набора Е\\ 2-й столбец — Ei, ...\ k-vi столбец — Ek.

Наличие кортежа Г/ в отношении R указывает, что объекты е, , е^ , ...

..., Cj^ ассоциируют между собой с помощью связи, представляемой отно­

шением R,

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

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

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

72

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

Л(^Ь^2,...,Л).

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

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

(RiiAiuAn, ..., Л, );

^2(^21, ^22, ..., Л ь )'

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

1)реляционная алгебра;

2)реляционное исчисление с переменными-кортежами;

3)реляционное исчисление с переменными-доменами.

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

Языки второго и третьего типов — языки исчисления — позволяют выражать запросы путем спецификации предиката, которому должны удов­ летворять требуемые кортежи (или домены).

Все эти языки предложил Е.Ф. Кодд для оценки возможностей реаль­ ных языков запросов к реляционной модели данных. По своей выразитель­ ности все три языка оказались эквивалентны между собой.

Реальные языки (ISBL, SEQUEL, QBE и др.) обеспечивают не только функции соответствующего теоретического языка или их комбинации, но и реализуют некоторые дополнительные операции (арифметические опера­ ции, команды присваивания, печати и т.п.).

Реляционная алгебра. При определении операций реляционной ал­ гебры предполагается, что порядок столбцов в отношении фиксирован, са­ ми отношения конечны.

Основные операции реляционной алгебры. 1. Объединение отношений R\ и Rj:

73

2. Модели данных

R = Rx UR2.

Операция применяется только к отношениям одной и той же арности. 2. Разность отношений R] и /?2'

R — R]— Rj.

Разностью {R\ - R2) называется множество кортежей, принадлежащих отношению Ru но не принадлежащих отношению 7?2.

Отношения /?1, /?2 и 7? должны быть одинаковой арности. 3. Декартово произведение отношений R\ и Ry.

R = Rix R2.

Если отношение R] имеет арность к], а отношение 7?2 — арность к2, то декартовым произведением i?i х i?2 отношений R] и 7?2 называется множество кортежей арности (к\ + ^2)5 причем первые к\ элементов обра­ зуют кортеж из отношений R\, а последние к2 элементов образуют кор­ теж из отношения i?2-

4. Проекция отношения R] на компоненты /ь /2,..., /V:

где /i, /2,..., /V — номера столбцов отношения 7?i.

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

5. Селекция отношения 7?i по формуле F: R = G,(R,l

где F— формула, образованная:

—операндами, являющимися номерами столбцов;

—логическими операторами:

л(and, и), V (or, или), I (not, не);

—арифметическими операторами сравнения

В формуле могут использоваться скобки.

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

6. Пересечение отношений R\ и 7?2:

/? = ;?, ni?2 = /?i-(i?i-/?2).

7. Частное отношений R] и 7?2*

R = R\ : R2 = Hi 2,. 77 w(^i) - П] 2, ,n т((П12, ,л w(^i) X ^2) - ^1)5

где п — арность отношения Ru т — арность отношения R2; п> m,R2^0. 8. Соединение отношений R\ и /?2:

/? = /?, ®7?2 = а,e(../)(^ix7?2),

74

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

где О — арифметический оператор сравнения; п — арность отношения Ru i Hj — номера столбцов соответственно в отношениях R\ и 7?2-

Если 0 является арифметическим оператором равенства, то операцию называют эквисоединением.

В приведенных выше операциях использовано обращение к элемен­ там кортежей по номерам столбцов отношения. Если будет обращение по имени столбцов, при этом, естественно, должны выполняться преобразова­ ния имени столбца в его порядковый номер и обратно. Тогда в случае ис­ пользования имен атрибутов отношения R можно подставлять имена в фор­ мулы. Например, если имеется отношение со схемой R(A, В, С, /)), то можно записать

ПАЛЯХ

<7 В=х V D=y (Л)-

9. Естественное соединение отношений R\ и R2.

Эта операция применяется только тогда, когда столбцы отношений R\ и 7?2 имеют имена.

Пусть отношения R\ и 7?2 имеют соответственно схемы:

^ l ( ^ b ^2?	•••5 ^Ь	В\, ^2, ..., Вп),
Rii^x.Ai,	...,Ак,	С], С2,..., Сщ),

где имена ^1, Ai, ..., А^ у обоих отношений совпадают, а остальные различа­ ются (для упрощения совпадающие имена поместим в начале, но они, ко­ нечно, могут быть записаны в любом другом порядке):

R = RX®R2= ^в,,В,,....В„А^А2 A,^C,Xh,..,C„,i^R,A=R2A^.-^IhA,=R2.A, № >< ^2)),

где R\A\ — имя столбца отношения {R\ х R{)^ соответствующего столбцу А\ в отношении Ru RiA\ — имя столбца отношения {R\ х /?2), соответствующе­ го столбцу У4| В отношении 7?2.

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

Реальным языком запросов, реализующим реляционную алгебру, яв­ ляется, например, алгебраический язык ISBL (Information System Base Language).

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

{tmt)),

где t — единственная свободная переменная — кортеж, обозначающая кор­ теж фиксированной длины; если необходимо указать арность кортежа, то используют запись f'\ где / — арность кортежа t\^ — некоторая формула,

75

2. Модели данных

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

Например, выражение

где в качестве формулы выступает конструкция R\{t) v Riit), означает, что нас интересует множество всех кортежей /, причем таких кортежей, которые принадлежат отношению R\ или отношению /?2- Отметим, что формула (^i(/) V i?2(0) имеет смысл только тогда, когда отношения R\ и Rj имеют одинаковую арность (поскольку переменная-кортеж / задана как переменная фиксированной длины). Приведенное выражение {tlR\{t) v /?2(0} эквива­ лентно операции объединения {R\ U Ri) реляционной алгебры.

Формулы в реляционном исчислении строятся из атомов и совокупно­ сти операторов (арифметических и логических).

Атомы формул бывают трех типов:

1)/?(/), где R — имя отношения. Этот атом означает, что t есть кортеж

вотношении /?;

2)s[i\ О w[/], где s w и — переменные-кортежи; 0 — арифметический оператор отношения; i,j — номера или имена интересующих нас компонен­ тов (столбцов) в соответствующих кортежах; s[i\ — обозначение /-го ком­ понента в кортеже-переменной s\ u(j) — обозначениеу-го компонента в кор­ теже-переменной и.

Например, атом (^[3] ^ и[5]) означает, что третий компонент пере­ менной S больше или равен пятому компоненту переменной w;

3) s[i] 9 а или а 6 s[i], где а — константа.

Например, атом (^[4] = 70) означает, что четвертый компонент пере­ менной-кортежа S равен 70.

При записи формул используется понятие «свободных» и «связанных» переменных-кортежей, что определяется характером использования в фор­ муле кванторов:

V — квантор всеобщности (общности); читается: все, всякий, каков бы ни был и т.п.

3 — квантор существования; читается: некоторые, хотя бы один, су­ ществует и т.п.

Вхождение переменной X в формуле Ч^ связано, если в Ч^ оно нахо­ дится в подформуле, начинающейся квантором V или 3, за которым непо­ средственно следует переменная X и о котором говорят в данном случае, что

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

(Vx)(i?(x, у) V (ЗуХЩх, у, Z) л ^х, 7))) V (Vx)(3r)([/(:t,у, z) v (3jc)(FW)

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

76

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

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

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

1. Каждый атом есть формула. Все вхождения переменных-кортежей, упомянутые в атоме, являются свободными.

2. Если/] и / — формулы, то:

/i	^fi	(утверждает, что/i	и / являются истинными),
/i	v /	(утверждает, что/i	или/, или обе истинны),

1/i (утверждает, что/ не истинна) также являются формулами.

Экземпляры переменных-кортежей являются свободными или связан­

ными в (/i л / ) , (/i v / )	и ( I / ) точно так же, как они являются свободными
или связанными в / и /	(т.е. свободны, соответственно связаны, те и только

те вхождения переменных, которые происходят от свободных, соответст­ венно связанных, вхождений переменных в / и / ) . Некоторое вхождение переменной может быть связанным в / , например, в то время как другое — свободным в / и т.п.

3.Если/— формула, то (V5)(/) тоже формула. Свободные вхождения переменной s в формуле/теперь становятся связанными квантором (V^) в формуле {\fs)(f). Формула (V5)(/) утверждает: какое бы значение (т.е. какой бы кортеж) подходящей арности ни подставляли вместо свободных вхожде­ ний S в формуле/ она всегда истинна.

4.Если/— формула, то {3s)(J) также формула. Свободные вхождения переменной s в формуле / теперь также становятся связанным квантором (3^) в формуле (3s)(J). Формула {3s)(J) утверждает, что существует значе­ ние S, при подстановке которого вместо всех свободных вхождений s в формулу/ эта формула становится истинной.

Например, формула (3s){R{s)) означает, что отношение R не пусто, т.е. существует некоторый кортеж 5, принадлежащий R.

5.Формулы при необходимости заключаются в скобки. Используется следующий порядок старшинства (в перечисленном порядке): арифметиче­ ские операторы сравнения; кванторы 3 и V; 1, л, v.

6.Ничто иное не является формулой.

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

{t^\3u)iR{u) л ((Г[1] = г/[/,]) л ... л {t[k] = и[Ш},

Можно сократить число скобок:

77

2. Модели данных

{/'V(3w)(i?(t/) л 41] = u\i{\ л ... л т = u[k])}.

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

{t/^R{t)},

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

С этой целью в реляционном исчислении рассматривают только так называемые «безопасные» выражения {//^(/)}, для которых выполняется условие, что каждый компонент (элемент столбца) любого /, удовлетво­ ряющего 4^(/), является элементом некоторого множества элементов DQ¥).

Множество DC^) определяется как функция фактических отношений, которые указываются в 4/(t\ констант, присутствующих в формуле ^(0, и элементов кортежей тех отношений, которые указаны в ^(0- Так как все отношения в БД предполагаются конечными, то и множество DC¥) конечно:

DC¥)={a,^} и {«24>} и ... и {а„^} U ЩК,) U П2(/г,) U ...

...п,(л,)ип,(Л2)и... ищтгд

где (71ч>, ..., (7„4> — константы, встретившиеся в формуле ^(0; ^\{R\X n2(/?i),..., Uk{Rn) — проекции кортежей фактических отношений R\, R2, ..., /?„, встретившихся в формуле Ч^(/) (в данном случае — компоненты кортежей).

При таком определении множества DQ¥) справедливо следующее:

DC¥,(t) V ^2(0) = Д ^ 1 ) и DC¥2);

Z)(^,(0 л ^2(0) = DC¥i) и /)(Ч^2); DC¥iit) л 1^2(0) = DC¥i) и Д ^ 2 ) и т.п.

Например, если задано выражение {t/C v /?(/)}, где R — бинарное от­ ношение, то

д^) = {С}ип,(Л)ип2(/г).

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

1. Из истинности Т(/) следует, что каждый компонент кортежа t при­ надлежит DQ¥).

2. Для любой подформулы Ч^ вида

входящей в состав Ч', и принадлежит DQ¥\X если и удовлетворяет ^ j . 3. Если для любой подформулы ^ вида

(УмХЧ'Км)),

78

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

входящей в состав ^ , каждый компонент и не принадлежит DQV\) (или, что то же самое, из истинности 1^(w) следует, что и принадлежит Z)(Ti)), то и удовлетворяет ^\{i). При выполнении этих условий выражение {tm{t)} яв­ ляется безопасным.

Отметим, что выражению (Vw)(4^i(w)) эквивалентно выражение

1(3w)(lTi(t/)). По условию 3 (VM)(TI(M)) безопасно, когда безопасно

1(3«)(1т,(г/)).

На основании вышеизложенного можно утверждать, что если форму­ ла ^ ( 0 такова, что любая ее подформула вида (3w)(T/(/)) или (V2/)(^/(/)) безопасна, то безопасно каждое выражение вида

{ Щ / ) л ^ ( / ) } .

Действительно, любой кортеж, удовлетворяющий формуле {R{t) л л Т(0) (т.е. при подстановке которого в эту формулу она становится истин­ ной), принадлежит (в соответствии с этой формулой) отношению R. Следо­ вательно, каждый из его компонентов будет принадлежать также и множе­ ству элементов D{R{t) л Ч^(/)). Тогда по условию 1 (выполнение условий 2 и 3 задано как исходная предпосылка) выражение {t\R{t) л ^{t)} является безо­ пасным.

Заметим, что если в ^{t) найдется хотя бы одна из подформул вида (3w)(^i(/)) или (Vw)(4^y(/)), которая окажется небезопасной, то тогда и выра­ жение {tlR{t) л Т(0} не будет являться безопасным. Если в формуле m{t) вообще отсутствуют подформулы вида (3w)(^,(/)) или (Vw)(^/(0), то выра­ жение {tlR{t) л ^(0} всегда является безопасным.

Например, если Т(/) = 1/?2(0? то получим безопасное выражение

{tlR,{i)A^R2{t)}.

Безопасным является также выражение {///?(/)}, соответствующее от­ ношению R (точнее — переменной R, обозначающей отношение).

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

Теорема 1. Если Е — выражение реляционной алгебры, то существу­ ет эквивалентное ему безопасное выражение в реляционном исчислении с переменными-кортежами.

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

1. Операции объединения {R\ U R2) соответствует выражение:

{tlR,{t)wR2{t)}.

2. Операции разности {R] - Ri) соответствует выражение:

{m{t)A^R2{t)}.

Здесь рассматривается все множество кортежей t таких, что t принад­ лежит /?] и не принадлежит R2.

79