Недостатки модели

Основной недостаток – невозможность реализации отношения «многие ко многим» в рамках одной базы данных. Реализация такого отношения на основе двух БД затрудняет управление.

9. Сетевая модель данных. Достоинства и недостатки.

Сетевая (графовая) модель основана на рекомендациях рабочей группы по базам данных КОДАСИЛ (CODASYL ).

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

Запись – иерархия, образованная из простейших (атомарных) элементов данных, их групп и повторяющихся групп.

Тип набора – множество допустимых экземпляров набора записи. К набору относятся записи – участники набора и владелец набора. Записи-владельцы (участники) могут быть одновременно владельцами (участниками) других наборов.

Доступ к участнику набора производится только через владельца. Тип набора имеет имя (уникальность владельца). Универсальный владелец в сетевой модели – это СУБД. Через нее выполняется доступ к самым «верхним» владельцам. Допускается и набор без владельца – сингулярный набор . В этом случае доступ к информации производит система, играя роль универсального владельца.

Ограничения КОДАСИЛ

1. Тип набора определяет отношение 1:М между типом записи-владельца и типом записи-участника.

2. Экземпляр типа записи-участника может участвовать только в одном экземпляре типа набора.

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

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

Наборы в сетевой базе данных могут иметь управляющие атрибуты. Атрибут «обязательный -необязательный» определяет поведение СУБД при удалении владельца экземпляра набора. В первом случае члены набора удаляются при удалении владельца, во втором случае – нет. Атрибут «автоматический-ручной» определяет способ включения в набор. В первом случае члены набора включаются в нужный экземпляр набора автоматически, во втором случае в нужный набор запись включается по команде из прикладной программы.

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

Достоинства

Ÿ реализуется отношение «многие ко многим»;

Ÿ высокая производительность.

Недостатки

Ÿ Трудность изменения структуры базы данных;

Ÿ Накопление «информационного мусора» за счет некорректных удалений и сбоев;

Ÿ слабая выразительность языка запросов.

Первая СУБД, построенная по сетевой модели – IDMS (1971 г.). Правами на нее обладает компания Computer Associates , она до сих пор поставляет и развивает эту СУБД. Примером может служить и СУБД IMAGE/1000 фирмы Hewlett-Packard .

10. Реляционная модель данных. Основные принципы. Компоненты модели. Достоинства и недостатки модели.

Принципы

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

1) независимость данных на логическом и физическом уровнях – стремление к независимости;

2) создание структурно простой модели – стремление к коммуникабельности;

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

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

Напомним, что модель данных – это структура и комбинация трех составляющих:

1) типов структур данных;

2) операторов или правил вывода;

3) общих правил целостности.

Структурную часть реляционной модели составляют следующие компоненты:

Ÿ отношения неопределенного порядка - таблица;

Ÿ атрибуты(столбец) – атомарные данные, характеризующие отношения;

Ÿ домены – множества допустимых значений атрибутов;

Ÿ кортежи(строки) – совокупности значений всех атрибутов отношения, взятых по одному для каждого атрибута, представленные строками таблицы;

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

Ÿ первичные ключи – для каждого отношения это один из возможных ключей.

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

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

Таким образом, мы сформулировали следующие свойства отношений :

1) Нормализованные отношения представляются в виде табличной структуры.

2) Упорядоченность кортежей теоретически несущественна.

3) Все кортежи различны.

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

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

Недостаток – проблемы с организацией связи.

11. Операции, реализующие изменение отношений во времени.

Размещение дополнительной информации производится операцией добавления ADD(r; A1=d1, A2=d2 , ..., An=dn). (Вариант для фиксированного порядка атрибутов: ADD(r; d1, d2, ..., dn))

Возможные ошибки при добавлении:

1) добавляемый кортеж не соответствует схеме;

2) некоторые значения не принадлежат требуемым доменам;

3) после добавления появляется совпадение по ключу.

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

Удаление информации производится операцией DEL(r; A1=d1, ..., An=dn) или DEL(r; d1, ..., dn).

Если K={B1, B2 , ..., Bm } – ключ отношения, для удаления достаточно записать DEL(r; B1=b1, B2=b2 , ..., Bm=bm).

Возможная ошибка – отсутствие удаляемого кортежа. Заметим, что допускается удаление последнего кортежа, то есть, пустое отношение может существовать.

Модификация информации производится операцией изменения. Пусть {C1, ... Cp} {A1, ... An}. Тогда операция модификации записывается следующим образом: CH(r; A1=d1, ..., An=dn ; C1=c1,..., Cn=cp) или, в случае ключа, CH(r; B1=b1, ..., Bm=bm ; C1=c1, ..., Cn=cp).

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

12. Операции реляционной алгебры: булевы операции. Активное дополнение.

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

Булевы операции

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

Пересечением называется отношение q(R) = r(R)∩s(R) , содержащее кортежи, которые одновременно принадлежат и r , и s . Объединением называется отношение q(R) = r(R)Us(R) , содержащее кортежи, которые принадлежат либо r , либо s . Разностью называется отношение q(R) = r(R) - s(R) , содержащее кортежи, которые принадлежат r , но не принадлежат s . Или формально:

r∩s ={t |(t r)&(t s)};

rUs ={t |(t r) (t s)};

r–s ={t |(t r)&(t s)}.

Заметим, что r∩s = r – (r – s) , то есть достаточно лишь двух операций.

Обозначим dom(R ) множество всех кортежей над атрибутами из схемы R и их доменами: dom (R ) = {t (d1 d2 … dn )| di dom (Ai )}. Дополнение отношения определим как r(R): r = dom(R) - r(R) . Но если какой-либо атрибут из R имеет бесконечный домен, r будет тоже иметь бесконечное число кортежей, то есть по определению не будет отношением.

Определение. Пусть r(A1, A2,..., An) – отношение, Di = dom(Ai). Тогда активный домен атрибута Ai относительно r – это множество adom(Ai,r) = {d Di | t r, t(Ai)=d}.

Пусть adom(R,r) – множество всех кортежей над атрибутами из R и их активными доменами относительно r : adom (R , r ) = {t (d1 d2 … dn )| di adom (Ai , r )}. Тогда активным дополнением r будем называть (r’=adomR,r’-r)?. Так как число значений атрибутов, принадлежащих кортежам из r , конечно, то активное дополнение всегда будет отношением.

13. Операции реляционной алгебры: выбор; свойства выбора.

Пусть теперь A – это некоторый атрибут отношения r (R ) и a dom(A) – элемент множества значений, которые может принимать отображение t на этом атрибуте. Выберем из отношения r те кортежи, для которых отображение t(A)=a , то есть, на A принимает значение a , и результат обозначим через ϬA = a (r ). Это унарная операция (применяется к одному отношению), результат которой – новое отношение r (R ).

Определение. Выбором ϬA = a (r ) называется отношение r (R ) = ϬA = a (r ) {t r | t (A )=a }.

Пусть r и s – отношения со схемой R ; A , B , C ,… – конечное число атрибутов в R , пусть a dom (A ), b dom (B ), c dom (C ),… . Тогда верны следующие утверждения.

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

ϬA =а°ϬB = b(r) ϬA = a(ϬB = b(r)) = ϬB = b(ϬA = a(r))≡ϬB = b°ϬA = a(r).

Утверждение 6.2. Операция выбора дистрибутивна относительно бинарных булевых операций:

ϬA = a (r s ) = ϬA = a (r ) γϬA = a (s ), где γ - принадлежит{∩ ,U , – }.

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

14. Операции реляционной алгебры: проекция; свойства проекции.

Пусть r – отношение со схемой R , X - подмножество R .

Определение. Проекцией πX(r) называется отношение r (X) = πX(r)≡{t(X) | t r }.

Это унарная операция, но в отличие от операции выбора, которая выдаёт строки по заданным условиям, она выдаёт столбцы, заголовки которых перечислены в X .

Утверждение 6.3. Операторы проекции и выбора перестановочны относительно композиции:

πX °ϬA = a (r)≡ πX(ϬA = a (r)) = ϬA = a (πX(r)) ϬA = a° πX (r).

15. Операции реляционной алгебры: соединение. Пример соединения.

16. Операции реляционной алгебры: свойства соединения.

Свойства соединения

Свойство 1. Имитация выбора.

С помощью оператора соединения найдём для отношения r (R ). Для этого определим отношение s (A ) с одним единственным кортежем t таким, что t (A ) = a . Тогда r || s =

Доказательство

Свойство 2. Обобщённая операция выбора.

Введём новое отношение s (A ) с k кортежами t 1, t 2,…, tk , где ti (A ) = ai и ai dom (A ), i =1, 2,…, k .

Тогда r || s =

Свойство 3. Коммутативность оператора соединения.

Из определения следует, что r || s = s || r .

Свойство 4. Ассоциативность оператора соединения.

Для отношений q , r , s (q || r ) || s = q || (r || s ). Следовательно, последовательность соединений можно записывать без скобок.

Свойство 5. Многократные соединения.

Пусть r 1(S 1), r 2(S 2),…, rn (Sn ) – отношения, R = S 1 S 2 … Sn . Обозначим S – последовательность схем S 1, S 2,…, Sn . Пусть t1, t2,…, tn – последовательность кортежей, ti ri , i = 1, 2,…, n .

Определение. Кортежи t1, t2,…, tn соединимы на S, если существует кортеж t на R, что ti = t(Si) для каждого i = 1, 2,…, n. Кортеж t называется результатом соединения кортежей t1, t2,…, tn на S.

Если в определении принять n=2 и если кортежи t1 и t2 соединимы на S=S1, S2 с результатом t , то t1=t(S1), t2=t(S2) , следовательно, t r(S1) || r(S2) . Обратно, если t r(S1) ||r(S2) , то должны существовать t1 и t2 в r(S) такие, что t1=t(S1), t2=t(S2) , то есть они соединимы на S с результатом t . Следовательно, r(S1) ||r(S2) состоит из результатов соединений соединимых на S кортежей t1 и t2 .

Лемма. Отношение r1 || r2 ||…|| rn состоит из всех кортежей t, которые являются результатом соединения соединимых на S кортежей ti ri, i = 1, 2,…, n.

Не каждый кортеж каждого отношения может войти в соединение.

Определение. Отношения r1, r2,…, rn полностью соединимы, если каждый кортеж в каждом отношении является членом списка соединимых на S кортежей.

Свойство 6. Проекция соединения.

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

Пусть r(R) и s(S) – отношения, q = r || s, RS – схема q. Пусть r’ = ), тогда r’ r (для любого кортежа t из отношения q верно t(R) r, а r’ ={t(R)| t q}).

Включение может быть собственным:

Может быть равенство (r = r’) :

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

Если s’ = , то r’ = r и s’ = s тогда и только тогда, когда r и s – состоят из полностью соединимых кортежей, то есть полностью соединимы.

Свойство 7. Соединение проекций.

Поменяем местами проекции и соединения. Пусть q – отношение со схемой RS, r = , s = . Пусть q′ = r || s. Если t q, то t(R ) r, t(S) s t q′, т.е. q′ q. При q′ = q отношение разложимо без потерь на схемы R и S.

Свойство 8. Соотношение операций объединения и соединения.

Пусть r и r – отношения со схемой R и s – отношение со схемой S . Покажем, что (rr ) || s = (r || s )(r || s ).

Обозначим левую часть равенства как q (r r’)||s, а правую – q’ (r || s) (r’ || s). Для кортежа t q найдутся кортежи и такие, что t = || , причем r или r’ и s’. Если r, то t r || s, если же r’, то t r’ || s, то есть q q’. Чтобы установить включение q q’, выберем t q’. Тогда t r || s или t r’ || s, следовательно, t (r r’) || s. Из q q’ и q q’ следует q = q.

17. Операции реляционной алгебры: деление.

Определение. Пусть r(R) и s(S) – отношения, S R. Положим R = R - S. Тогда r, разделенное на s – это отношение r’(R’)=

Отношение r’ – частное от деления r на s , что обозначается r’ = r s . Иначе r s – это максимальное подмножество r’ множества , такое, что r’ || s r . Соединение здесь – декартово произведение.

18. Построение отношений. Переименование атрибутов. Пример. Одновременное переименование.

Постоянные отношения.

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

Определение. Пусть A1,…,An – различные атрибуты, а c_i является константой из dom(Ai) для 1 i n, тогда< с1 : А1,…,сn : An> – постоянный кортеж <с1,…,сn> над схемой А1А2…Аn.

Постоянное отношение над схемой А1А2…Аn представляется как множество кортежей. Пусть c_ij – константа из dom(Ai) для 1 i n и 1 j k, тогда

представляет отношение, которое обычно записывалось бы так:

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

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

Переименование атрибутов

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

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

Определение. Пусть r – отношение со схемой R, A R, В R – A, dom(A)=dom(B). Пусть R’ = (R – A)B. Тогда r с A, переименованным в В (обозначается ) есть отношение r’(R’) =

Пример (продолжение)

Отношение с искомыми парами рейсов:

Конец примера

Пусть r – отношение со схемой R,

B1,…, Bk R – (A1…Ak); (1)

I: dom(Bi) = dom(Ai).

Обозначим одновременное переименование атрибутов A 1,…, Ak в B 1,…, Bk как Благодаря условию (1) оно всегда может быть записано в виде последовательности переименований. Если это условие не выполняется, без введения дополнительных атрибутов такую замену выполнить нельзя. Очевидный пример – обмен

19. Операции реляционной алгебры: Эквисоединение, естественное и – соединение.

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

Определение. Пусть r(R), s(S) – отношения, Ai R , Bi S , dom(Ai) = dom(Bi), 1 i m, Ai ≠ Bi. Эквисоединением r и s по A1, A2,…,Am и B1, B2,…, Bm называется отношение

q (RS ) =

Эту операцию будем обозначать следующим образом:

r [A 1 = B 1, A 2 = B 2,…, Am = Bm ] s .

Заметим, что для однозначного определения операции эквисоединения достаточно условия Ai ≠ Bi для всех атрибутов, входящих в сравнение. Однако обычно требуют, чтобы в эквисоединении все атрибуты различались по именам, то есть, чтобы R S = пустому множеству. Это не сильное ограничение, так как путем переименования атрибутов в s и r можно добиться пустого пересечения их схем.

Замечание. Если в эквисоединении нет сравнений, то оно совпадает с декартовым произведением: r s = r s.

Соединение, определённое ранее, будем называть естественным .

Утверждение. Эквисоединение может быть выражено через переименование и естественное соединение.

Естественное соединение также может быть выражено через эквисоединение. Например, для отношений r (A , B , C ), s (B , C , D ), атрибутов B’ и C’ с dom (B’ ) = dom (B ), dom (C’ ) = dom (C ):

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

Определение. Если знак сравнения , а A и B – атрибуты, то говорят, что A -сравним с B, если – бинарное отношение в dom(A) dom(B).

Определение. Атрибут A -сравним, если он -сравним сам с собой.

Расширим оператор выбора, используя понятие -сравнимости. Пусть r – отно-шение со схемой R , атрибут A R , a dom (A ) – константа, , A -сравним. Тогда расширенный оператор выбора . Аналогично этот оператор определяется для случая сравнения между атрибутами, с учетом того, что B R , dom(B)=dom (A ):

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

Определение. Пусть r(R) и s(S) – отношения, для которых R S = пустое, и пусть A R и B S -сравнимы для. Тогда -соединением называется отношение q(RS) = {t | , которое обозначается q(RS) = r s.

20. Реляционная алгебра Кодда. Алгебра А (алгебра Дэйта). Полнота Алгебры А.

Реляционная алгебра. Полнота ограниченного множества операторов

Обозначим U – множество атрибутов (универсум ), D – множество доменов, dom – полная функция из U в D , R = {R 1, R 2,…, Rp } – множество схем, Ri U , d = {r 1(R 1), r 2(R 2),…, rp (Rp )} – множество наборов отношений, – множество бинарных отношений над доменами из D .

Определение. Реляционная алгебра над U , D , dom, R , d, – семиместный кортеж B =(U , D , dom, R , d, , O ), где O – множество операторов объединения, пересечения, разности, активного дополнения, проекции, естественного соединения, деления, переименования, которые используют атрибуты из U, и оператор выбора, использующий операторы из .

Теорема . Для выражения E над реляционной алгеброй существует выражение E’ над ней же, которое определяет ту же функцию и использует лишь операторы (1) постоянных отношений с единственным атрибутом и единственным кортежем, (2) выбора с одним сравнением, (3) естественного соединения, (4) проекции, (5) объединения, (6) разности, (7) переименования.

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

21. Операторы расщепления и фактора. Примеры использования

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

Определение. Пусть (t) – предикат на кортежах над R, тогда расщеплением r по называется пара отношений (s, s’), каждое со схемой R, такие, что s = {t r | (t)} и s’ = { t r | (t)}. Обозначается эта пара SPLIT (r).

Рассмотрим список студентов

Разобьём его на два по группам. Для этого воспользуемся операцией расщепления с предикатом (t ) = (t (Группа ) = 306). Тогда SPLIT (Студент ) = (гр306, гр506 ):

Конец примера

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

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

Определение. Пусть дано отношение r(R) и B1, B2,…, Bk R, L R. Тогда фактором будем называть пару следующих отношений: (s, s’) = FACTOR (r; B1, B2,…, Bk; L), где s = s((R – B1B2…Bk)L), s’ = s’ (B1B2…BkL), причём s и s’ соединяются по L без потерь.

Действие последнего оператора рассмотрим на примере.

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

Чтобы исключить доступ ко всей информации, разделим отношение на два, добавив в каждое одинаковую метку: Дело(метка, Группа, Номер экз.листа, ФИО) и Шифр(Шифр, метка) . Воспользуемся оператором FACTOR (Абитуриент ; шифр; метка ) = (Дело, Шифр) .

Конец примера

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

Рассмотрим список отдыхающих в некотором доме отдыха. Во время заезда админист-ратор интересуется у отдыхающих, курят они или храпят. Его цель – для минимизации конфликтов разместить курильщиков с курильщиками, храпящих – с храпящими.

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

Действительно, по определению оператора фактора получившиеся отношения должны быть соединимы по метке и не более того, что мы и наблюдаем. Но в первом примере одному кортежу первого отношения соответствовал единственный кортеж второго, а здесь нет. Для достижения полученного эффекта мы использовали правило: если атрибуты B 1, B 2,…, Bk R из определения оператора не содержат ключ, одинаковые кортежи t(B 1B 2…Bk) помечаются одинаковыми метками. В противном случае одинаковыми метками помечаются кортежи t(R-B 1B 2…Bk) .

22. Функциональная зависимость. Алгоритм проверки существования функциональной зависимости в отношении.

Определение. Пусть R – схема отношения, X,Y R. Множество атрибутов Y функционально зависит от X тогда и только тогда, когда в любой момент времени для каждого из различных значений Y существует только одно из различных значений X. Другими словами, для любого r(R), ti , tj r, ti(Y) ≠ tj(Y) ti(X) ≠ tj(X).

Эквивалентный термин: множество X определяет Y . Обозначение – X Y. Левую часть функциональной зависимости X называют детерминантом .

23. Нормальные формы. 1 нормальная форма. Её связь с постановкой задачи.

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

Нормальные формы, в которых находятся отношения, составляют иерархию, в которой формы с большими номерами не обладают некоторыми нежелательными свойствами, характерными для форм с меньшими номерами. В теории нормальных форм для реляционных БД рассматривается шесть уровней нормализации: 1НФ – 5НФ и форма Бойса-Кодда (промежуточная между 3НФ и 4НФ). Каждый из следующих уровней ограничивает типы допустимых функциональных зависимостей отношения. Функциональные зависимости отношения описывают его семантику. Уровень нормализации зависит от семантики отношения.

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

Нормальная форма (1НФ)

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

Определение. Отношение находится в 1НФ, если все значения его атрибутов атомарны, то есть, для каждого отношения r(R), если AR, adom(A,r) атомарен.

Пусть для отношения со схемой рейс (Номер, Пункт назначения, Вылет) атрибут Вы-лет определен как пара (День, Время) :

В этом случае легко реализовать запросы типа «Выдать все рейсы до Уфы», в отличие от запроса «Выдать все рейсы, вылетающие утром». С точки зрения второй задачи отношение не находится в 1НФ. Преобразование очевидно: отношение заменяется другим со схемой

рейс (Номер, Пункт назначения, День, Время).

24. Полная функциональная зависимость. 2 нормальная форма.

Нормальная форма (2НФ)

Широко распространённая ошибка при проектировании баз данных – попытка объявить в качестве первичного ключа суперключ: дескать, лишний атрибут в ключе не повредит. Такая практика на деле приводит к значительным неприятностям.

Определение. Функциональная зависимость X=(A1,A2,...,Ak) B полная, если B зависит от всех Ai из X. Если существует X" B, где X" – собственное подмножество X, функциональная зависимость неполная.

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

Определение запрещает в качестве ключа использовать суперключ, если отношение находится во 2НФ.

Задано отношение со схемой поставки (Поставщик, Товар, Цена), для которого опре-делены следующие ограничения:

Ÿ Товар могут поставлять разные поставщики.

Ÿ Цена одинаковых товаров одинакова.

Ÿ Поставщик может поставлять разные товары.

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

Поставщик, Товар Цена

Товар Цена

Здесь налицо неполная функциональная зависимость цены от ключа.

Аномалия включения : новый товар не включается в БД без поставки.

Аномалия удаления : поставки прекращаются – удаляются сведения о товаре.

Аномалия обновления : изменение цены влечет полный пересмотр.

Преобразование:

Поставки (поставщик, товар)

Цена товара (товар, цена)

25. Транзитивная зависимость. 3 нормальная форма.

Нормальная форма (3НФ)

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

Определение. Атрибут A транзитивно зависит от X, если существует Y такой, что выполняется условие X Y & (Y X) & Y A & X A, A XY.

Условие (Y X) означает, что Y – множество заведомо не первичных атрибутов.

Определение. Отношение находится в 3НФ, если оно находится в 1НФ и в нем отсут-ствует транзитивная зависимость атрибутов от первичных атрибутов.

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

Отделение Склад

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

Склад Объем

Таким образом, отношение оказалось не в 3НФ (существует транзитивная зависимость объема от отделения через склад: Отделение Склад & Склад Отделение & Склад Объем & Отделение Объем).

Аномалия включения : нет отделения, получающего товар с этого склада – нет сведе-ний об объеме.

Аномалия удаления : отделение перестает получать товар – нет данных о складе.

Аномалия обновления : изменение объема склада влечет полный пересмотр.

Преобразование:

хранение (Отделение, Склад)

объем склада (Склад, Объем)

26. Многозначная зависимость. 4 нормальная форма.

Нормальная форма (4НФ)

Другая распространённая ошибка при проектировании баз данных, кроме использования суперключа – наличие в одном отношении атрибутов, связанных отношением «один ко многим» или, что ещё хуже – «многие ко многим». Изначально эта связь может быть не очевидна, но по мере уточнения семантики отношения проявляется.

Определение. A многозначно определяет B в R (или B многозначно зависит от A), если каждому значению A соответствует множество (возможно, пустое) значений B, не зависимых от других атрибутов из R. Обозначение: A B.

Задано отношение преподаватель(Ид-преп, Дети, Курсы, Должность) , которое связывает уникальный идентификатор (код) преподавателя с его семейными обстоятельствами (наличием детей) и служебным положением (читаемые курсы). Будем считать, что атрибуты Ид-преп и Дети находятся в отношении 1:M, а Ид-преп и Курсы – в отношении M:N. Здесь наличие детей и читаемые курсы – независимые атрибуты, то есть присутствуют многозначные зависимости Ид-преп Дети и Ид-преп Курсы .

Определение. Отношение находится в 4НФ, если оно находится в 1НФ и в нем от-сутствует нефункциональные многозначные зависимости. Другое определение – для любой нетривиальной зависимости X Y множество атрибутов X содержит ключ).

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

Преобразование:

R1(Ид-преп, Дети)

R2(Ид-преп, Курсы)

R3(Ид-преп, Должность)

27. Проектирование данных. Уровни абстракции

Процессы проектирования

В ходе разработки проекта нужно ответить на следующие вопросы:

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

Ÿ как они преобразуются в структуру базы данных;

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

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

Концептуальный уровень – наиболее общее представление об информационном содержании предметной области. Представляется в виде концептуальной модели (КМ). КМ обладает высокой степенью стабильности, она проблемно-ориентирована и не зависит от конкретной СУБД, операционной системы и аппаратного обеспечения. Ее поведение должно быть полностью предсказуемо.

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

Обычно для концептуального представления используется модель «Сущность-Связь» (ER-модель) , введенная Ченом, которая графически выражается ER -диаграммами.

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

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

Есть и другая классификация уровней представления данных. Согласно стандарту ANSI / SPAC , архитектура БД представлена трехуровневой моделью с внешним , концептуальным и внутренним уровнями. В отличие от предыдущей модели, это не модель проектирования, а модель оперирования данными.

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

Концептуальный уровень – наиболее общее представление об информационном содержании предметной области. Определение совпадает с приведенным ранее.

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

28. Концептуальное проектирование. Выявление требований.

Похожая информация.

Лекция 20. Отношения на множестве

1. Отношения на множестве. Бинарные отношения.

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

§10. ОТНОШЕНИЯ НА МНОЖЕСТВЕ

В математике изучают не только связи между элементами двух множеств, т.е. соответствия, но и связи между элементами одного множества. Называют их отношениями.

Отношения многообразны. Между понятиями - это отношения ро­да и вида, части и целого; между предложениями - отношения следо­вания и равносильности; между числами - «больше», «меньше», «равно», «больше на...», «меньше на...», «следует» и др.

Если рассматривают отношения между двумя элементами, то их на­зывают бинарными; отношения между тремя элементами - тернарными; отношения между п элементами - n -арными. Все названные выше от­ношения являются бинарными. Примером тернарного отношения может служить отношение между точками прямой - «точка х лежит между точками у и 2».

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

Чтобы определить общее понятие бинарного отношения на множестве, поступим так же, как и в случае с соответствиями, т.е. рассмотрим сначала конкретный пример. Пусть на множестве X = {2, 4, 6, 8} задано отношение «меньше». Это означает, что для любых двух чисел из множества X можно сказать, какое из них меньше: 2 < 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения Х х Х , поэтому об отношении «меньше», заданном на множестве X , можно сказать, что оно является подмножеством множества Х х X .

Вообще бинарные отношения на множестве X определяют следующим способом:

Определение. Бинарным отношением на множестве X называется всякое подмножество декартова произведения Х х Х.

Так как в дальнейшем мы будем рассматривать только бинарные отношения, то слово «бинарные», как правило, будем опускать.

Условимся отношения обозначать буквами R, S, T, P и др.

Если R - отношения на множестве X , то, согласно определению, R с X х X . С другой стороны, если задано некоторое подмножество множества X х X , то оно определяет на множестве X некоторое отношение R .

Утверждение о том, что элементы х и у находятся в отношении R , можно записывать так: (х, у ) € R или хRу . Последняя запись читается: «Элемент х находится в отношении R с элементом у ».

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

Построим, например, граф отношений «меньше», заданного на множестве X = {2, 4, 6, 8}. Для этого элементы множества X изобразим точками (их называют вершинами графа), а отношение «меньше» - стрелкой (рис. 93).

На том же множестве X можно рассмотреть другое отношение - «кратно». Граф этого от­ношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе (рис. 94). Отношение можно задать при помощи пред­ложения с двумя переменными. Так, например, заданы рассмотренные выше отношения «мень­ше» и «кратно», причем использована краткая форма предложений «число x меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записывать, используя сим­волы. Например, отношения «меньше» и «кратно» можно было задать в таком виде: «x < у», «х: у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или x - у = 3).

Для отношения R , заданного на множестве X, всегда можно задать отношение R -1 , ему обратное, - оно определяется так же, как соответствие, обратное данному. Например, если R - отно­шение «х меньше y », то обратным ему будет отношение «у больше x ».

Понятием отношения, обратного данному, часто пользуются при начальном обучении математике. Например, чтобы предупредить ошибку в выборе действия, с помощью которого решается задача: «У Пети 7 карандашей, что на 2 меньше, чем у Бори. Сколько каран­дашей у Бори?» - ее переформулируют: «У Пети 7 карандашей, а у Бори на 2 больше. Сколько карандашей у Бори?» Видим, что перефор­мулировка свелась к замене отношения «меньше на 2» обратным ему отношением «больше на 2».

Понятие отношения на множестве

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

т.е. рассмотрим сначала конкретный пример. Пусть на множестве X = {2, 4, 6, 8} задано отношение «меньше». Это означает, что для любых двух чисел из множества X можно сказать, какое из них меньше: 2 < 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения X х X, поэтому об отношении «меньше», заданном на множестве X, можно сказать, что оно является подмножеством множества X х X.

Вообще бинарные отношения на множестве X определяют следующим способом:

Определение. Бинарным отношением на множестве X называется всякое подмножество декартова произведения X х X.

Так как в дальнейшем мы будем рассматривать только бинарные отношения, то слово «бинарные», как правило, будем опускать.

Условимся отношения обозначать буквами R, S, Т, Р и др.

Если R - отношения на множестве X, то, согласно определению, R X х X. С другой стороны, если задано некоторое подмножество множества X х X, то оно определяет на множестве X некоторое отношение R.

Утверждение о том, что элементы х и у находятся в отношении R, можно записывать так: (х, у) R или x R y. Последняя запись читается: «Элемент х находится в отношении R с элементом у».

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

Построим, например, граф отношений «меньше», заданного на множестве Х= (2, 4, 6, 8}. Для этого элементы множества X изобразим точками (их называют вершинами графа), а отношение «меньше» - стрелкой (рис. 1).

На том же множестве X можно рассмотреть другое отношение - «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе (рис. 2).

Отношение можно задать при помощи предложения с двумя переменными. Так, например, заданы рассмотренные выше отношения «меньше» и «кратно», причем использована краткая форма предложений «число х меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записывать, используя символы. Например, отношения «меньше» и «кратно» можно было задать в таком виде: «х<у», «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х – у = 3).

Для отношения R, заданного на множестве X, всегда можно задать отношение R -1 , ему обратное, - оно определяется так же, как соответствие, обратное данному. Например, если R - отношение «х меньше у», то обратным ему будет отношение «у больше х».

Понятием отношения, обратного данному, часто пользуются при начальном обучении математике. Например, чтобы предупредить ошибку в выборе действия, с помощью которого решается задача: «У Пети 7 карандашей, что на 2 меньше, чем у Бори. Сколько карандашей у Бори?» - ее переформулируют: «У Пети 7 карандашей, а у Бори на 2 больше. Сколько карандашей у Бори?» Видим, что переформулировка свелась к замене отношения «меньше на 2» обратным ему отношением «больше на 2».

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

Мы установили, что бинарное отношение на множестве X представляет собой множество упорядоченных пар элементов, принадлежащих декартову произведению ХхХ. Это математическая сущность всякого отношения. Но, как и любые другие понятия, отношения обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые. Рассмотрим на множестве отрезков, представленных на рис. 3, отношения перпендикулярности, равенства и «длиннее». Построим графы этих отношений (рис. 4) и будем их сравнивать.

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

Определение. Отношение R на множестве X называется рефлексивным, если о каждом элементе множества X можно сказать, что он находится в отношении R с самим собой.

R рефлексивно на Х <=> xRx для любого х X

Если отношение R рефлексивно на множестве X, то в каждой вершине графа данного отношения имеется петля. Справедливо и обратное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности.

Примеры рефлексивных отношений:

Отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе);

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

Существуют отношения, которые свойством рефлексивности на обладают. Таким, например, является отношение перпендикулярности на множестве отрезков: нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе. Поэтому на графе отношения перпендикулярности (рис. 4) нет ни одной петли. Не обладает свойством рефлексивности и отношение «длиннее» для отрезков.

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

Если один отрезок перпендикулярен другому отрезку, то этот «другой» перпендикулярен первому;

Если один отрезок равен другому отрезку, то этот «другой» равен первому.

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

Определение. Отношение R на множестве X называется симметричным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у, следует, что и элемент у находится в отношении R с элементом х.

Используя символы, это отношение можно записать в таком виде:

R симметрично на X <=> (xRy => yRx)

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

В дополнение к рассмотренным двум примерам симметричных отношений присоединим еще такие:

Отношение параллельности на множестве прямых (если прямая х параллельна прямой у, то и прямая у параллельна прямой х);

Отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).

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

Определение. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X выполнено условие: из того, что х находится в отношении R с элементом у, следует, что элемент у в отношении R с элементом х не находится .

антисимметрично на X <=> (xRy и х≠у => )

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

Кроме отношения «длиннее» на множестве отрезков свойством антисимметричности, например, обладают:

Отношение «больше» для чисел (если х больше у, то у не может быть больше х);

Отношение «больше на 2» для чисел (если х больше у на 2, то у не может быть больше на 2 числа х).

Существуют отношения, не обладающие ни свойством симметричности, ни свойством антисимметричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф отношения «быть сестрой» будет таким, как на рисунке 5. Он показывает, что данное отношение не обладает ни свойством симметричности, ни свойством антисимметричности.

Обратим внимание еще раз на одну особенность графа отношения «длиннее» (рис. 4). На нем можно заметить: если стрелки проведены от е к а и от а к с , то есть стрелка от е к с ; если стрелки приведены от е к b и от b к с , то есть стрелка и от е к с и т.д. Эта особенность графа отражает важное свойство отношения «длиннее»: если первый отрезок длиннее второго, а второй - длиннее третьего, то первый - длиннее третьего. Говорят, что это отношение обладает свойством транзитивности или просто транзитивно.

Определение. Отношение R на множестве X называется транзитивным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом z, следует, что элемент х находится в отношении R с элементом z.

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

R транзитивно на X <=> (xRy и yRz => xRz)

Граф транзитивного отношения с каждой парой стрелок, идущих от х к у и у к z , содержит стрелку, идущую от х к z . Справедливо и обратное утверждение.

Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку z , то отрезок х равен отрезку z . Это свойство отражено и на графе отношения равенства (рис. 4)

Существуют отношения, которые свойством транзитивности не обладают. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку d, а отрезок d перпендикулярен отрезку b, то отрезки а и b не перпендикулярны!

Рассмотрим еще одно свойство отношений, которое называют свойством связанности, а отношение, обладающее им, называют связанным.

Определение. Отношение R на множестве X называется связанным, если для любых элементов х и у из множества X выполняется условие: из того, что х и у различны, следует, что либо х находится в отношении R с элементом у, либо элемент у находится в отношении R с элементом х.

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

R связанно на множестве X <=> (х≠у xRy или yRx)

Например, свойством связанности обладают отношения «больше» для натуральных чисел: для любых различных чисел х и у можно утверждать, что либо х> у, либо у > х.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

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

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

Так, если суммировать все сказанное об отношении равенства, заданном на множестве отрезков (рис. 4), то получается, что оно рефлексивно, симметрично и транзитивно. Отношение «длиннее» на том же множестве отрезков антисимметрично и транзитивно, а отношение перпендикулярности-симметрично, но оно не обладает свойствами рефлексивности и транзитивности. Все эти отношения на заданном множестве

отрезков связанными не являются.

Задача 1. Сформулировать свойства отношения R, заданного при помощи графа (рис. 6).

Решение. Отношение R- антисимметрично, так как вершины графа соединяются только одной стрелкой.

Отношение R - транзитивно, так как с парой стрелок, идущих от b к а и от а к с , на графе есть стрелка, идущая от b к с .

Отношение R - связанно, так как любые две вершины соединены стрелкой.

Отношение R свойством рефлексивности не обладает, так как на графе есть вершины, в которых петли нет.

Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.

Решение. «Больше в 2 раза» - это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число у не больше числа х в 2 раза.

Данное отношение не обладает свойством рефлексивности, потому что ни про одно число нельзя сказать, что оно больше самого себя в 2 раза.

Заданное отношение не транзитивно, так как из того, что число х больше числа у на 2, а число у больше числа z на 2, следует, что число х не может быть больше числа z на 2.

Это отношение на множестве натуральных чисел свойством связанности не обладает, так как существуют пары таких чисел х и у, что ни число не больше числа у в два раза, ни число у не больше х в 2 раза. Например, это числа 7 и 3,5 и 8 и др.

Лекция 3.

п.3. Отношения на множествах. Свойства бинарных отношений.

3.1. Бинарные отношения .

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

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A ´B ) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S ´K можно выделить большое подмножество упорядоченных пар (s , k ), обладающих свойством: студент s слушает курс k . Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

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

Определение 3.1. Бинарным (или двухместным ) отношением r между множествами A и B называется произвольное подмножество A ´B , т. е.

В частности, если A= B (то есть rÍA 2), то говорят, что r есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами ) отношения r.

Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит : r, t, j, s, w и т. д.

Определение 3.2. Областью определения D r={a | $ b , что a rb } (левая часть). Областью значений бинарного отношения r называется множество R r={b | $ a , что a rb } (правая часть).

Пример 3. 1. Пусть даны два множества A ={1; 3; 5; 7} и B ={2; 4; 6}. Отношение зададим следующим образом t={(x ; y )ÎA ´B | x+ y =9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.

Пример 3. 2. Отношение равенства на множестве действительных чисел есть множество r={(x ; y ) | x и y – действительные числа и x равно y }. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, D r= R r.

Пример 3. 3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x ; y )ÎA ´B | y – цена x } – отношение множеств A и B .

Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x ; y )ÎA ´B | x+ y =9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

Способы задания отношений:

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом , точки же, изображающие элементы множеств, принято называть вершинами графа .

4) в виде матрицы: пусть A ={a 1, a 2, …, an } и B ={b 1, b 2, …, bm }, r – отношение на A ´B . Матричным представлением r называется матрица M =[mij ] размера n ´m , определенная соотношениями

.

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

Пример 3. 4. Пусть даны два множества A ={1; 3; 5; 7}и B ={2; 4; 6}. Отношение задано следующим образом t={(x ; y ) | x+ y =9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.

Решение. 1) t={(3; 6), (5; 4), (7; 2)} - есть задание отношения как множества упорядоченных пар;

2) соответствующий ориентированный граф показан на рисунке.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

Пример 3. 5 . Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M :

,

где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.

Рассмотрим информационный обмен между устройствами mi и mj , которые находятся в отношении r, если из устройства mi поступает информация в устройство mj .

Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:

Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:

Матричное представление этого бинарного отношения имеет вид:

. ,

Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.

Введем обобщенное понятие отношения.

Определение 3.3. n-местное (n -арное ) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей )

rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ùan ÎAn }

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

Слово «реляционная » происходит от латинского слова relation , которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).

Определение 3.4. Пусть rÍA ´B есть отношение на A ´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A ´B , которое определяется следующим образом:

r-1={(b , a ) | (a , b )Îr}.

Определение 3.5. Пусть r ÍA ´B есть отношение на A ´B, а s ÍB ´C – отношение на B ´C. Композицией отношений s и r называется отношение t ÍA ´C ,которое определяется следующим образом:

t=s◦r= {(a , c )| $ b Î B, что (a , b )Îr и (b , c )Îs}.

Пример 3. 6 . Пусть , и C ={, !, d, à}. И пусть отношение r на A ´B и отношение s на B ´C заданы в виде:

r={(1, x ), (1, y ), (3, x )};

s={(x ,), (x , !), (y , d), (y , à)}.

Найти r-1 и s◦r, r◦s.

Решение. 1) По определению r-1={(x , 1), (y , 1), (x , 3)};

2) Используя определение композиции двух отношений, получаем

s◦r={(1,), (1, !), (1, d), (1, à), (3,), (3, !)},

поскольку из (1, x )Îr и (x ,)Îs следует (1,)Îs◦r;

из (1, x )Îr и (x , !)Îs следует (1, !)Îs◦r;

из (1, y )Îr и (y , d)Îs следует (1, d)Îs◦r;

из (3, x )Îr и (x , !)Îs следует (3, !)Îs◦r.

Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:

2) ;

3) - ассоциативность композиции.

Доказательство. Свойство 1 очевидно.

Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a ; b ) Î (s◦r)-1 Û (b ; a ) Î s◦r Û $ c такое, что (b ; c ) Î r и (c ; a ) Î s Û $ c такое, что (c ; b ) Î r-1 и (a ; c ) Î s-1 Û (a ; b ) Î r -1◦s -1.

Свойство 3 доказать самостоятельно.

3.2. Свойства бинарных отношений .

Рассмотрим специальные свойства бинарных отношений на множестве A .

Свойства бинарных отношений.

1. Отношение r на A ´A называется рефлексивным , если (a ,a ) принадлежит r для всех a из A .

2. Отношение r называется антирефлексивным , если из (a ,b )Îr следует a ¹b .

3. Отношение r симметрично , если для a и b , принадлежащих A , из (a ,b )Îr следует, что (b ,a )Îr.

4. Отношение r называется антисимметричным , если для a и b из A , из принадлежности (a ,b ) и (b ,a ) отношению r следует, что a =b .

5. Отношение r транзитивно , если для a , b и c из A из того, что (a ,b )Îr и (b ,c )Îr, следует, что (a ,c )Îr.

Пример 3. 7. Пусть A ={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA 2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?

Решение. 1) Это отношение рефлексивно, так как для каждого a ÎA , (a ; a )Îr.

2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.

3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:

	(a , b )Îr	(b , a )	(b , a )Îr?

4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.

5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.

	(a , b )Îr	(b , c )Îr	(a , c )	(a , c )Îr?

Как по матрице представления

определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

3. Симметричность: если .

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

. Отношение равенства на множестве целых чисел есть отношение эквивалентности.

Пример 3. 9 . Отношение «одного роста» есть отношение эквивалентности на множестве людей X .

Пример 3. 1 0 . Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (m Î¥) и запишем , если равны остатки этих чисел от деления их на m , т. е. разность (x -y ) делится на m .

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т. к. для "x ΢ имеем x -x =0, и, следовательно, оно делится на m ;

это отношение симметрично, т. к. если (x -y ) делится на m , то и (y -x ) тоже делится на m ;

это отношение транзитивно, т. к. если (x -y ) делится на m , то для некоторого целого t 1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда , т. е. (x -z ) делится на m .

Определение 3.7. Отношение r на A есть отношение частичного порядка , если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

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

Пример 3. 11 . Отношение x £y на множестве действительных чисел есть отношение частичного порядка. ,

Пример 3. 1 2 . Во множестве подмножеств некоторого универсального множества U отношение A ÍB есть отношение частичного порядка.

Пример 3. 1 3 . Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

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

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

Отношение предпочтения P , которое можно определить как «aPb , a , b ÎA Û объект a не менее предпочтителен, чем объект b » является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a , то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование , т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

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

relatio - «отношение», «зависимость», «связь»).

Энциклопедичный YouTube

• 1 / 5

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

  • Заголовок (или схема) H отношения R - конечное множество упорядоченных пар вида (A i , T i ), где A i - имя атрибута , а T i - имя типа (домена), i =1,…, n . По определению требуется, чтобы все имена атрибутов в заголовке отношения были различными (уникальными).
  • Тело B отношения R - множество кортежей t . Кортеж t , соответствующий заголовку H , - множество упорядоченных триплетов (троек) вида <A i , T i , v i >, по одному такому триплету для каждого атрибута в H , где v i - допустимое значение типа (домена) T i . Так как имена атрибутов уникальны, то указание домена в кортеже обычно излишне. Поэтому кортеж t , соответствующий заголовку H , нередко определяют как множество пар (A i , v i ).

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

  Количество атрибутов называют степенью , или «арностью » отношения; отношение с одним атрибутом называется унарным, с двумя - бинарным и т.д., с n атрибутами - n -арным. С точки зрения теории вполне корректным является и отношение с нулевым количеством атрибутов, которое либо не содержит кортежей, либо содержит единственный кортеж без компонент (пустой кортеж) .

  Основные свойства отношения:

  • В отношении нет двух одинаковых элементов (кортежей).
  • Порядок кортежей в отношении не определён.
  • Порядок атрибутов в заголовке отношения не определён.

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

  Отношения и таблицы

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

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

  Пример

  Пусть заданы следующие типы (домены):

  Тогда декартово произведение T 1 × T 2 × T 3 {\displaystyle T_{1}\times T_{2}\times T_{3}} состоит из 18 кортежей, где каждый кортеж содержит три значения: первое - одна из фамилий, второе - учебная дисциплина, а третье - оценка.

  Пусть отношение R имеет заголовок H : { (Фамилия, T 1), (Дисциплина, T 2), (Оценка, T 3)}.

  Тогда тело отношения R может моделировать реальную ситуацию и содержать пять кортежей, которые соответствуют результатам сессии (Петров экзамен по Физике не сдавал). Отобразим отношение в виде таблицы:

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

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

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

  Примечания

  Литература

  • Когаловский М.Р. Энциклопедия технологий баз данных. - М. : Финансы и статистика, 2002. - 800 с. - ISBN 5-279-02276-4 .
  • Кузнецов С. Д. Основы баз данных. - 2-е изд. - М. : Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007. - 484 с. -