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

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

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

Заголовком (или схемой) отношения r (Hr) называется конечное множество упорядоченных пар вида <A, T>, где A называется именем атрибута, а T обозначает имя некоторого базового типа или ранее определенного домена. По определению требуется, чтобы все имена атрибутов в заголовке отношения были различны.

Кортежем tr, соответствующим заголовку Hr, называется множество упорядоченных триплетов вида <A, T, v>, по одному такому триплету для каждого атрибута в Hr. Третий элемент – v – триплета <A, T, v> должен являться допустимым значением типа данных или домена T.

Телом Br отношения r называется произвольное множество кортежей tr.

Значением Vr отношения r называется пара множеств Hr и Br.

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

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

Схема реляционной базы данных набор пар <имя_VARr, Hr>, включающий имена и заголовки всех переменных отношения, которые определены в базе данных.

Реляционная база данных – это набор пар <VARr, Hr> (конечно, каждая переменная отношения в любой момент времени содержит некоторое значение-отношение, в частности, пустое).

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

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

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

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

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

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

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

Реляционная  модель  данных:  общее понятие и составные части.

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

Модель данных (в контексте области баз данных) описывает некий набор родовых понятий и признаков, которыми должны обладать все конкретные СУБД и управляемые ими базы данных, если они основываются на этой модели.

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

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

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

Реляционная алгебра Кодда

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

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

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

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

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

• Результатом ограничения (WHERE) отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию.

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

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

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

• Операция переименования (RENAME) производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены.

• Операция присваивания (:=) позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД.

Алгебра A

Базисом предложенной Крисом Дейтом и Хью Дарвеном Алгебры A являются операции реляционного отрицания (дополнения), реляционной конъюнкции (или дизъюнкции) и проекции (удаления атрибута). Реляционные аналоги логических операций определяются в терминах отношений на основе обычных теоретико-множественных операций и позволяют выражать напрямую операции пересечения, декартова произведения, естественного соединения, объединения отношений и т. д. Путем комбинирования базовых операций выражаются операции переименования атрибутов, соединения общего вида, взятия разности отношений. Алгебра A позволяет лучше осознать логические основы реляционной модели, хотя, безусловно, является в меньшей степени ориентированной на практическое применение, чем алгебра Кодда

Во всех формальных спецификациях exists обозначает квантор существования; exists tr означает «существует такой tr, что». Символ « » означает принадлежность одного множества другому; tr Br означает, что элемент tr принадлежит множеству Br. Выражение tr Br означает, что элемент tr не принадлежит множеству Br. Операции minus и union являются традиционными теоретико-множественными операциями взятия разности и объединения множеств.

Операция реляционного дополнения.

Пусть s обозначает результат операции <NOT> r. Тогда:

• Hs = Hr (заголовок результата совпадает с заголовком операнда);

• Bs = {ts : exists tr (tr Br and ts = tr) } (в тело результата входят все кортежи, соответствующие заголовку и не входящие в тело операнда).

Операция <NOT> производит дополнение s заданного отношения r. Заголовком s является заголовок r. Тело s включает все кортежи, соответствующие этому заголовку и не входящие в тело r.

Операция удаления атрибута.

• Пусть s обозначает результат операции r <REMOVE> A. Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип (или домен) T такой, что <A, T> Hr (т. е. в состав заголовка отношения r должен входить атрибут A). Тогда: Hs = Hr minus {<A, T>}, т. е. заголовок результата получается из заголовка операнда изъятием атрибута A;

• Bs = {ts : exists tr exists v (tr Br and v T and <A,T,v> tr and ts = tr minus {<A,T,v>})}, т. е. в тело результата входят все кортежи операнда, из которых удалено значение атрибута A.

Операция <REMOVE> производит отношение s, формируемое путем удаления указанного атрибута A из заданного отношения r. Операция эквивалентна взятию проекции r на все атрибуты, кроме A. Заголовок s получается теоретико-множественным вычитанием из заголовка r множества из одного элемента {<A, T>}. Тело s состоит из таких кортежей, которые соответствуют заголовку s, причем каждый из них является подмножеством некоторого кортежа тела отношения r.

Операция переименования.

Пусть s обозначает результат операции r <RENAME> (A, B). Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип T, такой, что <A, T> Hr, и чтобы не существовал такой тип T, что <B, T> Hr. (Другими словами, в схеме отношения r должен присутствовать атрибут A и не должен присутствовать атрибут B.) Тогда:

• Hs = (Hr minus {<A, T>}) union {<B, T>}, т. е. в схеме результата B заменяет A;

• Bs = {ts : exists tr exists v (tr Br and v T and <A, T, v> tr and ts = (tr minus {<A, T, v>}) union {<B, T, v>})}, т. е. в кортежах тела результата имя значений атрибута A меняется на B.

Операция <RENAME> производит отношение s, которое отличается от заданного отношения r только именем одного его атрибута, которое изменяется с A на B. Заголовок s такой же, как заголовок r, за исключением того, что пара <B, T> заменяет пару <A, T>. Тело s включает все кортежи тела r, но в каждом из этих кортежей триплет <B, T, v> заменяет триплет <A, T, v>.

Операция реляционной конъюнкции

Пусть s обозначает результат операции r₁ <AND> r₂. Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1> Hr₁ и <A, T2> Hr₂, то T1=T2. (Другими словами, если в двух отношениях-операндах имеются одноименные атрибуты, то они должны быть определены на одном и том же типе (домене).) Тогда:

• Hs = Hr₁ union Hr₂, т. е. заголовок результата получается путем объединения заголовков отношений-операндов, как в операциях TIMES и JOIN из предыдущей лекции;

• Bs = { ts : exists tr₁ exists tr₂ ((tr₁ Br₁ and tr₂ Br₂) and ts = tr₁ union tr₂)}; обратите внимание на то, что кортеж результата определяется как объединение кортежей операндов; поэтому:

  • если схемы отношений-операндов имеют непустое пересечение, то операция <AND> работает как естественное соединение;

  • если пересечение схем операндов пусто, то <AND> работает как расширенное декартово произведение;

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

Операция <AND> является реляционной конъюнкцией, в некоторых случаях выдающей в результате отношение rs, ранее называвшееся естественным соединением двух заданных отношений r₁ и r₂. Заголовок rs является объединением заголовков r₁ и r₂. Тело s включает каждый кортеж, соответствующий заголовку s и являющийся надмножеством некоторого кортежа из тела r₁ и некоторого кортежа из тела r₂.

Операция реляционной дизъюнкции

Пусть s обозначает результат операции r₁ <OR> r₂. Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1> Hr₁ и <A, T2> Hr₂, то должно быть T1 = T2 (одноименные атрибуты должны быть определены на одном и том же типе). Тогда:

• Hs = Hr₁ union Hr₂ (из схемы результата удаляются атрибуты-дубликаты);

• Bs = { ts : exists tr₁ exists tr₂ ((tr₁ Br₁ or tr₂ Br₂) and ts = tr₁ union tr₂)}; очевидно, что при этом:

  • если у операндов нет общих атрибутов, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr₁ и tr₂, соответствующих заголовкам отношений-операндов, и хотя бы один из этих кортежей принадлежит телу одного из операндов;

  • если у операндов имеются общие атрибуты, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr₁ и tr₂, соответствующих заголовкам отношений-операндов, если хотя бы один из этих кортежей принадлежит телу одного из операндов, и значения общих атрибутов tr₁ и tr₂ совпадают;

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

Операция <OR> является реляционной дизъюнкцией и обобщением того, что ранее называлось объединением. Заголовок s есть объединение заголовков r₁ и r₂. Тело s состоит из всех кортежей, соответствующих заголовку s и являющихся надмножеством либо некоторого кортежа из тела r₁, либо некоторого кортежа из тела r₂.