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

Размещено на http://www.allbest.ru/

Введение

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

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

Примеры пар: <x, y>, <1, 2>, <2, 2>.

Пара отличается от двухэлементного множества следующим:

- в паре порядок элементов имеет значение;

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

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

Бинарным отношением, заданным на множествах M и N, является некоторое подмножество тех пар (кортежей) <x, y> из декартова (прямого) произведения M*N, между элементами которых существует связь R. Здесь R - имя отношения.

Бинарное отношение - это множество кортежей длиной 2.

Для кортежей, принадлежащих отношению R, приняты следующие обозначения:

x R y - -x находится в отношении R к y;

R(x, y) - между x и y существует отношение R;

<x, y> R - кортеж <x, y> принадлежит отношению R.

Пусть заданы два множества M = {m1, m2} и {n1, n2, n3}. В результате декартова произведения множеств M*N будет получено множество кортежей: {<m1, n1>, {m1, n2>, <m1, n3>, <m2, n1>, <m2, n2>, <m2, n3>}. Отношению R будут принадлежать те кортежи, для которых m i находится в отношении R к n j.

В частном случае можно задать отношение на одном множестве M. Это будет подмножество кортежей из декартова произведения M*M.

Пример

Определим отношение с именем МЕНЬШЕ на множестве целых чисел M= {1, 2, 3}. Декартово произведение M*M представляет собой множество кортежей <1,1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>.

Отношению МЕНЬШЕ принадлежат те кортежи декартова произведения, у которых первый элемент меньше второго.

МЕНЬШЕ={ <1, 2>, <1, 3>, <2, 3>}.

Пример

Пусть множество M1 содержит имена детей одной семьи.

M1 = {Таня, Галя, Сережа}

Тогда отношение с именем БРАТ состоит из двух кортежей: <Сережа, Таня>, <Сережа, Галя>, а отношение СЕСТРА состоит из четырех кортежей: <Таня, Галя>, <Таня, Сережа>, <Галя, Таня>, <Галя, Сережа>.

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

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

Состояние реляционной БД можно описать как совокупность некоторых множеств М1, М2, ….., Мi, ….., Мn, на которых задан ряд отношений. Каждое отношение представляет собой подмножество кортежей из декартовых произведений определенных множеств. Множества, на которых задано конкретное отношение, называются несущими множествами для данного отношения.

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

Основные понятия реляционной модели данных

При рассмотрении реляционной модели, основанной на понятии отношения (relation), оперирует терминами, пришедшими из математики.

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

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

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

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

Таким образом, отношение - это совокупность кортежей, т.е. таблица со всеми своими строками.

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

Рассмотренная выше реляционная модель данных содержит три базовых отношения. Отношение СТУДЕНТ - имеет арность 4 и содержит 4 кортежа, отношение ПРЕПОДАВАТЕЛЬ - бинарное и содержит 3 кортежа, отношение ПРЕДМЕТ - тернарное и содержит 3 кортежа. Связующие отношения ПРЕПОДАВАТЕЛЬ_ПРЕДМЕТ и СТУДЕНТ_ПРЕПОДАВАТЕЛЬ - бинарные.

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

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

Ключи отношений

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

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

Рассмотрим 3 отношения, содержащие сведения о поставщиках, поставляемых ими изделиях и объемах поставок. Каждому поставщику и каждому изделию присвоены уникальные номера: П, И.

ПОСТАВЩИК ИЗДЕЛИЕ

П#.	Имя поставщ.	Город		И#	Наименование	Вес
П1	Восход	Тула		И1	Болт	12
П2	Заря	Самара		И2	Гайка	8
П3	Салют	Тула		И3	Гвоздь	6

ПОСТАВКИ

П#	И#	Количество
П1	И1	300
П1	И2	200
П1	И3	200
П2	И1	200
П2	И2	500
П3	И4	80

В таблице ПОСТАВЩИК первичным ключом является атрибут П#, а в таблице ИЗДЕЛИЕ - И#.

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

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

Для реляционных БД очень важным является также понятие внешнего ключа отношений. Атрибут, являющийся первичным ключом одного отношения и входящий в составной первичный ключ другого отношения является внешним ключом этих отношений. Так, например, внешним ключом отношений ПОСТАВЩИК и ПОСТАВКИ является атрибут П#, а внешним ключом отношений ИЗДЕЛИЕ и ПОСТАВКИ является атрибут И#. Через внешний ключ между этой парой отношений устанавливается связь 1:М.

Отношение ПОСТАВКИ является связующим для отношений ПОСТАВЩИК и ИЗДЕЛИЕ, между которыми устанавливается связь М:М.

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

Контроль ссылочной целостности

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

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

Ссылочная целостность контролируется:

при вводе записей в подчиненную таблицу;

при удалении записи из родительской таблицы;

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

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

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

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

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

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

НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ РЕЛЯЦИОННОЙ БД

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

Известно 5 нормальных форм (НФ) отношений. Нормализация выполняется поэтапно. Сначала отношение приводится к первой НФ (1НФ), затем - ко 2НФ и т.д. вплоть до 5НФ. Однако для устойчивой работы БД часто оказывается достаточным, если ее отношения находятся в 3НФ

Первая нормальная форма

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

Пусть в рассмотренной нами выше предметной области о поставках на предприятие изделий поставщик П1 поставляет в определенных количествах изделия И1, И2 и И3, поставщик П2 - изделия И1 и И2, а поставщик П3 - изделие П4. Эти данные можно представить в виде таблицы ПОСТАВКИ1. Такой вид таблицы типичен для многих документов. Так, например, в одну колонку таблицы часто помещают фамилию, имя и отчество человека или адрес, содержащий почтовый индекс, город, улицу, номер дома, номер квартиры.

Номера поставщиков П# уникальны, и этот атрибут можно принять в качестве первичного ключа отношения ПОСТАВКИ1.

ПОСТАВКИ 1

П#	ПК
	И#	Кол
П1	И1 И2 И3	300 200 200
П2	И1 И2	200 500
П3	И4	80
П#	И#	Кол
П1 П1 П1 П2 П2 П3	И1 И2 И3 И1 И2 И4	300 200 200 200 500 80

Можно заметить, в таблице на пересечении, например, строки П1 и столбца И# содержится несколько значений номеров изделий. Другими словами, в отношении ПОСТАВКИ1 значения ключа П# идентифицирует сразу несколько значений не ключевых атрибутов И# и Кол, что недопустимо. Это отношение находится не в 1НФ.

Преобразуем отношение так, чтобы устранить этот недостаток. В преобразованном отношении ПОСТАВКИ первичный ключ - составной П# И# и каждое значение первичного ключа идентифицирует единственное значение не ключевого атрибута Кол. Это отношение находится в 1НФ.

Вторая нормальная форма

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

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

ПОСТАВКИ 2

П#	И#	Кол	Имя поставщика	Город	Тариф
П1	И1	300	Восход	Тула	10
П1	И2	200	Восход	Тула	10
П1	И3	200	Восход	Тула	10
П2	И1	200	Заря	Самара	15
П2	И2	500	Заря	Самара	15
П3	И4	80	Салют	Тула	10

Отметим, что у этого отношения первичный ключ составной - П# И#.

Рассмотрим следующую ситуацию. Пусть ведутся переговоры о поставках с новым предприятием Победа, расположенном в городе Тамбове. Требуется включить в таблицу сведения об этом предприятии и сведения о тарифе по доставки грузов с этого предприятия. Мы не сможем этого сделать. Это предприятия еще ничего не поставляет и код поставляемых изделий неизвестен, т.е. И# =0, а у составного первичного ключа ни одна из компонент не может быть нулевой. В этом и состоит аномалия включения.

Если же какое-либо предприятие, например, Заря перестанет поставлять нам изделия, то для него И# =0. Из таблицы придется исключить все сведения об этом предприятии, в том числе и те, которые мы хотели бы сохранить. В этом состоит аномалия удаления.

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

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

Рис. 1

Ключ отношения составной, но он, целиком, определяет лишь атрибут Кол. Атрибуты Имя поставщика, Город и Тариф зависят лишь от части первичного ключа, так как именно номер поставщика однозначно определяет имя предприятия, название города, а, следовательно, и тариф. Это отношение находится не во 2НФ. Для приведения его ко 2НФ надо выделить группы атрибутов, зависящие от частей составного ключа, в отдельные таблицы.

В таблицу ПОСТАВЩИК1 выделим атрибуты П#, Имя поставщика, Город, Тариф. Ключ этого отношения - П#. В таблицу ПОСТАВКИ выделим атрибуты П#, И#, Кол. Здесь первичный ключ составной - П #И#. Отношения связаны между собой через внешний ключ П#. Теперь полученные отношения находятся во 2НФ и в БД можно включать сведения о новых предприятиях даже в том случае, когда они не поставляют никаких изделий.

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

ПОСТАВЩИК 1

П#	Имя поставщика	Город	Тариф
П1 П2 П3	Восход Заря Салют	Тула Самара Тула	10 15 10
П#	И#	Кол
П1 П1 П1 П2 П2 П3	И1 И2 И3 И1 И2 И4	300 200 200 200 500 80

Третья нормальная форма

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

Рассмотрим зависимости между атрибутами отношения ПОСТАВЩИК 1.

Рис. 2

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

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

Для приведения отношения к 3НФ необходимо выделить в отдельную таблицу не ключевые атрибуты, функционально полно зависящие друг от друга. Таблицу ПОСТАВЩИК1 разделим на две таблицы: ПОСТАВЩИК и ДОСТАВКА.

ПОСТАВЩИК ДОСТАВКА

П#	Имя поставщика	Город
П1 П2 П3	Восход Заря Салют	Тула Самара Тула
Город	Тариф
Тула Самара	10 15

Теперь эти отношения находятся в 3НФ и в БД можно включать сведения о новых городах и тарифах даже в том случае, когда из этих городов пока не делается никаких поставок. Между полученными отношениями существует связь типа 1:М (на стороне 1 находится отношение ДОСТАВКА). Связь осуществляется через атрибут Город.

Таким образом, исходная таблица ПОСТАВКИ2 разделилась на три таблицы: ПОСТАВЩИК, ДОСТАВКА, ПОСТАВКИ. Каждая из таблиц находится в 3НФ. Эти таблицы можно рассматривать в качестве модели данных реляционной БД.

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

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

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

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

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

Теоретико-множественные операции

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

Пусть имеются два идентичных бинарных отношения с именами R и S, состоящие из атрибутов А1 и А2.

Объединением отношений R и S (R S) называется новое отношение, состоящее из кортежей <x, y>, принадлежащих либо отношению R, либо отношению S.

реляционный модель база данная

R

S

RS

RS

R\ S

A 1

A 2

A 1

A 2

A 1

A 2

A 1

A 2

A 1

A 2

a

b

p

q

a

b

a

b

l

k

c

d

c

d

c

d

c

d

m

p

l

k

a

b

l

k

m

p

l

n

m

p

p

q

l

n

Пересечением отношений R и S (RS) называется новое отношение, состоящее из кортежей <x, y>, принадлежащих одновременно отношениям R и S.

Разностью отношений R и S (R\S) называется отношение, кортежи которого принадлежат R но не принадлежат S.

Операция декартова произведения рассматривалась нами выше.

Специальные операции над отношениями

Пусть имеются два бинарных отношения с именами R и S. Отношение R состоит из атрибутов А1 и А2, отношение S - из атрибутов А2 и А3.

Сцепление отношений

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

Сцеплением бинарных отношений R и S называется новое отношение R*S, состоящее из кортежей <x, y, z>, для которых кортеж <x, y> принадлежит R, а <y, z> принадлежит S.

Пример

Определим результат выполнения операции сцепления отношений R и S, атрибуты которого А2 определены на одном и том же домене. Это значит, что если в столбце с именем А2 таблицы R содержатся, например, названия городов, то и в столбце А2 таблицы S также содержатся названия городов.

R S R*S R*M

А1

А2

А2

А3

А1

А2

А3

А1

А2

a

b

b

k

a

b

k

a

b

c

b

d

f

c

b

k

c

b

c

d

d

p

c

d

f

e

q

c

d

p

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

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

В общем случае, если отношение R имеет арность m, а отношение S - арность n , то R*S будет иметь арность m+n-1.

Эта операция называется еще операцией соединения или естественного соединения.

Можно выполнить сцепление отношения с множеством.

Пусть множество М является одноэлементным и содержит одно значение {b} из того же домена, на котором задан атрибут А2 отношения R. Тогда результатом операции сцепления будет отношение R*M, состоящее из тех кортежей отношения R, у которых значение атрибута А2 равно b.

Иными словами, в результате сцепления таблицы R с константой b из таблицы R оказались выбранными стоки, содержащие в столбце А2 значение b. Если в столбце А2 содержались, например, названия городов, то из таблицы отберутся строки с заданным названием города.

Проекция отношения на его компоненты

Проекцией отношения R на его i-ю компоненту (атрибут Аi ) называется множество, состоящее из различных значений этого атрибута. Операция проекции обозначается R [Аi].

Пример

Найдем проекцию отношения R на его атрибут А2. В результате получим множество {b, d, q}. Иными словами, результатом проекции является множество различных значений, образующих столбец А2 таблицы R.

Можно выполнять операцию проекции на несколько компонент.

Список использованной литературы

1. Информатика. Базовый курс / Симонович С.В. и др. - СПб: Издательство «Питер», 2000. - 640 с.

2. Информатика. Учебное пособие / Под ред. В.Г. Кирия. - Иркутск: ИрГТУ, 1998 часть 2. - 382 с.

3. Информатика. Учебное пособие / Ломтадзе В.В., Шишкина Л.П. - Иркутск: ИрГТУ, 1999. - 116 с.

Размещено на Allbest.ru