Бегун.Рекомендую - рекламодателю
Здесь может быть ваша реклама
|

 ГЛАВА 4. Реляционная модель данных

ГЛАВА 4. Реляционная модель данных

Основные определения

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

Теоретической основой этой модели стала теория отношений, основу которой заложили два логика — американец Чарльз Содерс Пирс (1839-1914) и немец Эрнст Шредер (1841-1902). В руководствах по теории отношений было показано, что множество отношений замкнуто относительно некоторых специальных операций, то есть образует вместе с этими операциями абстрактную алгебру. Это важнейшее свойство отношений было использовано в реляционной модели для разработки языка манипулирования данными, связанного с исходной алгеброй. Американский математик Э. Ф. Кодд в 1970 году впервые сформулировал основные понятия и ограничения реляционной модели, ограничив набор операций в ней семью основными и одной дополнительной операцией. Предложения Кодда были настолько эффективны для систем баз данных, что за эту модель он был удостоен престижной премии Тьюринга в области теоретических основ вычислительной техники.

Основной структурой данных в модели является отношение, именно поэтому модель получила название реляционной (от английского relation — отношение).

N-арным отношением R называют подмножество декартова произведения D,xD2x ... xDn множеств D,, D2, ..., Dn (n > 1), необязательно различных. Исходные множества D1, D2, ..., Dn называют в модели доменами.

R Базы данных, программы, электронные книги, раскрутка, оптимизацияD1xD2x...xDm

где D1xD2x ...xDn— полное декартово произведение.

Полное декартово произведение — это набор всевозможных сочетаний из п элементов каждое, где каждый элемент берется из своего домена. Например, имеем три домена: D1 содержит три фамилии, D2 — набор из двух учебных дисциплин и D3 — набор из трех оценок. Допустим, содержимое доменов следующее:

  • D1 = {Иванов, Крылов, Степанов};
  • D2 = (Теория автоматов, Базы данных};
  • D3 = {3, 4, 5}

Тогда полное декартово произведение содержит набор из 18 троек, где первый элемент — это одна из фамилий, второй — это название одной из учебных дисциплин, а третий — одна из оценок.

<Иванов.Теория автоматов.3>: <Иванов.Теория автоматов.4>; <Иванов.Теория автоматов,5> <Крылов.Теория автоматов.3>: <Крылов,Теория автоматов,4>: <Крылов,Теория автоматов.5>: <Степанов.Теория автоматов.3>; <Степанов.Теория автоматов.4>: <Степанов,Теория автоматов.5>: <Иванов,Базы данных.3>: <Иванов.Базы данных.4>: <Иванов,Базы данных.5>: <Крылов,Базы данных,3>; <Крылов,Базы данных,4>; <Крылов.Базы данных.5>; <Степанов.Базы данных.3>: <Степанов,Базы данных.4>: <Степанов,Базы данных,5>:

Отношение R моделирует реальную ситуацию и оно может содержать, допустим, только 5 строк, которые соответствуют результатам сессии (Крылов экзамен по «Базам данных» еще не сдавал):

<Иванов.Теория автоматов.4>: <Крылов,Теория автоматов,5>: <Степанов,Теория автоматов,5>; <Иванов.Базы данных.3>; <Степанов.Базы данных.4>;

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

R



Фамилия

Дисциплина

Оценка

Иванов

Теория автоматов

4

Иванов

Базы данных

3

Крылов

Теория автоматов

5

Степанов

Теория автоматов

5

Степанов

Базы данных

4

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

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

Вхождение домена в отношение принято называть атрибутом. Строки отношения называются кортежами.

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

Следует заметить, что в отношении не может быть одинаковых кортежей, это следует из математической модели: отношение — это подмножество декартова произведения, а в декартовом произведении все n-ки различны,

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

R1

Дисциплина

Фамилия

Оценка

Теория автоматов

Крылов

5

Теория автоматов

Степанов

5

Теория автоматов

Иванов

4

Базы данных

Иванов

3

Базы данных

Степанов

4

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

Схемой отношения R называется перечень имен атрибутов данного отношения с указанием домена, к которому они относятся:

SR = (А1, А2, Аn) АiБазы данных, программы, электронные книги, раскрутка, оптимизацияDi

Если атрибуты принимают значения из одного и того же домена, то они называются Q-сравпимыми, где Q— множество допустимых операций сравнения, заданных для данного домена. Например, если домен содержит числовые данные , то для него допустимы все операции сравнения, тогда Q = {=, <>,>=,<-,<,>}. Однако и для доменов, содержащих символьные данные, могут быть заданы не только операции сравнения по равенству и неравенству значений. Если для данного домена задано лексикографическое упорядочение, то он имеет также полный спектр операций сравнения.

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

SR1 = (A1, A2, ..., An) — схема отношения R1.

SR2= (Bi1, Bi2,..., Bin) — схема отношения R2после упорядочения имен атрибутов.

Тогда

sR1~sR2<=>1. n=m, или 2. Аj,BijБазы данных, программы, электронные книги, раскрутка, оптимизацияDj

Как уже говорилось ранее, реляционная модель представляет базу данных в виде множества взаимосвязанных отношений. В отличие от теоретико-графовых моделей в реляционной модели связи между отношениями поддерживаются неявным образом. Какие же связи между отношениями поддерживаются в реляционной модели? В этой модели, так же как и в остальных, поддерживаются иерархические связи между отношениями. В каждой связи одно отношение может выступать как основное, а другое отношение выступает в роли подчиненного. Это означает, что один кортеж основного отношения может быть связан с несколькими кортежами подчиненного отношения. Для поддержки этих связей оба отношения должны содержать наборы атрибутов, по которым они связаны. В основном отношении это первичный ключ отношения (PRIMARY KEY), который однозначно определяет кортеж основного отношения. В подчиненном отношении для моделирования связи должен присутствовать набор атрибутов, соответствующий первичному ключу основного отношения. Однако здесь этот набор атрибутов уже является вторичным ключом, то есть он определяет множество кортежей подчиненного отношения, которые связаны с единственным кортежем основного отношения. Данный набор атрибутов в подчиненном отношении принято называть внешним ключом (FOREIGN KEY).

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

Базы данных, программы, электронные книги, раскрутка, оптимизация

Рис. 4.1. Связь между основным и подчиненным отношениями

PRIMARY KEY отношения Сотрудник атрибут Паспорт является FOREIGHN KEYдля отношения «карьера».

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

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

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

Основным множеством в реляционном алгебре является множество отношений. Всего Э. Ф. Коддом было предложено 8 операций. В общем это множество избыточное, так как одни операции могут быть представлены через другие, однако множество операций выбрано из соображений максимального удобства при реализации произвольных запросов к БД. Все множество операций можно разделить на две группы: теоретико-множественные операции и специальные операции. В первую группу входят 4 операции. Три первые теоретико-множественные операции являются бинарными, то есть в них участвуют два отношения и они требуют эквивалентных схем исходных отношений.

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

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

Пусть заданы два отношения R1 = { r1 } , R2 = { r2 }. где r1 и r2 — соответственно кортежи отношений R1 и R2, то объединение

R1Базы данных, программы, электронные книги, раскрутка, оптимизацияR2 = { г | г Базы данных, программы, электронные книги, раскрутка, оптимизацияR1Базы данных, программы, электронные книги, раскрутка, оптимизацияr Базы данных, программы, электронные книги, раскрутка, оптимизацияR2 }. Здесь r — кортеж нового отношения, Базы данных, программы, электронные книги, раскрутка, оптимизация— операция логического сложения «ИЛИ».

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

R1

Шифр детали

Название детали

00011073

Гаика Ml

00011075

Гайка М2

00011076

Гаика M3

00011003

Болт Ml

00011006

Болт МЗ

00013063

Шайба Ml

00013066

Шайба МЗ

 

R2

Шифр детали

Название детали

00011073

Гайка М1

00011076

Гайка М3

00011077

Гайка М4

00011004

Гайка М2

00011006

Гайка М3

 

R3


Шифр детали

Название детали

00011073

Гайка Ml

00011075

Гайка М2

00011076

Гайка МЗ

00011003

Болт Ml

00011006

Болт МЗ

00013063

Шайба Ml

00013066

Шайба МЗ

00011077

Гайка М4

00011004

Болт М2

Пересечением отношений называется отношение, которое содержит множество кортежей, принадлежащих одновременно и первому и второму отношениям. R1 и R2:

R3 = R1Базы данных, программы, электронные книги, раскрутка, оптимизация R2={ г | r Базы данных, программы, электронные книги, раскрутка, оптимизацияR1 ^ г Базы данных, программы, электронные книги, раскрутка, оптимизацияR2 }, здесь ^ — операция логического умножения (логическое «И»).

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

R4


Шифр детали

Название детали

00011073

Гайка Ml

00011076

Гайка МЗ

00011006

Болт МЗ

Разностью отношений R1 и R2 называется отношение, содержащее множество кортежей, принадлежащих R1 и не принадлежащих R2:

R5 = RI R2 = { г | r Базы данных, программы, электронные книги, раскрутка, оптимизацияR1 ^ r Базы данных, программы, электронные книги, раскрутка, оптимизацияR2 }

Отношение R5 содержит перечень деталей, изготавливаемых только на участке 1, отношение RG содержит перечень деталей, изготавливаемых только на участке 2.

R6 = R2 R1 = { r | r Базы данных, программы, электронные книги, раскрутка, оптимизацияR2 ^ rБазы данных, программы, электронные книги, раскрутка, оптимизацияR1 }

R5


Шифр детали

Название детали

00011075

Гайка М2

00011003

Болт Ml

00013063

Шайба Ml

00013066

Шайба МЗ

 

R6


Шифр детали

Название детали

00011077

Гайка М4

00011004

Болт М2

 

R3

Шифр детали

Название детали

00011073

Гайка Ml

00011075

Гайка М2

00011076

Гайка МЗ

00011003

Болт Ml

00011006

Болт МЗ

00013063

Шайба Ml

00013066

Шайба МЗ

00011077

Гайка М4

00011004

Болт М2

Пересечением отношений называется отношение, которое содержит множество кортежей, принадлежащих одновременно и первому и второму отношениям. R1 и R2:

R3 = R1Базы данных, программы, электронные книги, раскрутка, оптимизация R2 ={ r | r Базы данных, программы, электронные книги, раскрутка, оптимизация R1 ^ r Базы данных, программы, электронные книги, раскрутка, оптимизацияR2 }

здесь ^— операция логического умножения (логическое «И»).

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

R4

Шифр детали

Название детали

00011073

Гайка M1

00011076

Гайка МЗ

00011006

Болт МЗ

Разностью отношений R, и R2 называется отношение, содержащее множество кортежей, принадлежащих R1 и не принадлежащих R2:

R5 = R1 R2 = { r | r Базы данных, программы, электронные книги, раскрутка, оптимизацияR1 ^ г Базы данных, программы, электронные книги, раскрутка, оптимизацияR2 }

Отношение R5 содержит перечень деталей, изготавливаемых только на участке 1, отношение R6 содержит перечень деталей, изготавливаемых только на участке 2.

R6 = R2 R1 = { r | r Базы данных, программы, электронные книги, раскрутка, оптимизация R2 ^ r Базы данных, программы, электронные книги, раскрутка, оптимизация R1 }

R5

Шифр детали

Название детали

00011075

Гайка М2

00011003

Бол г M1

00013063

Шайба M1

00013066

Шайба МЗ

 

R6

Шифр детали

Название детали

00011077

Гайка М4

00011004

Болт М2

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

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

Для демонстрации возможностей трех первых операций реляционной алгебры рассмотрим еще один пример — уже из другой предметной области. Исходными являются три отношения R1 R2 и R3. Все они имеют эквивалентные схемы.

  • R1= (ФИО, Паспорт, Школа);
  • R2= (ФИО, Паспорт, Школа);
  • R3= (ФИО, Паспорт, Школа).

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

Ответим на следующие вопросы:

  1. Список абитуриентов, которые поступали два раза и не поступили в вуз. R = R1Базы данных, программы, электронные книги, раскрутка, оптимизацияR2 R3
  2. Список абитуриентов, которые поступили в вуз с первого раза, то есть они сдавали экзамены только один раз и сдали их так хорошо, что сразу были зачислены в вуз. R = (R1 R2Базы данных, программы, электронные книги, раскрутка, оптимизация R3 )Базы данных, программы, электронные книги, раскрутка, оптимизация (R2 R1Базы данных, программы, электронные книги, раскрутка, оптимизация R3)
  3. Список абитуриентов, которые поступили в вуз только со второго раза.

    Прежде всего это те абитуриенты, которые присутствуют в отношениях R1 и R2, потому что они поступали два раза, и присутствуют в отношении R3, потому что они поступили. R = R1Базы данных, программы, электронные книги, раскрутка, оптимизация R2Базы данных, программы, электронные книги, раскрутка, оптимизация R3

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

    Это прежде всего те абитуриенты; которые присутствуют в R1и не присутствуют в R2, и те, кто присутствуют в R2 и не присутствуют в R1. И разумеется, никто из них не присутствует в R3. R = (R1 R2) Базы данных, программы, электронные книги, раскрутка, оптимизация (R2 R1) R3

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

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

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

Сцеплением, пли конкатенацией, кортежей с = <c1, с2, ..., сn> и q = <q1, q2, ..., qm> называется кор

 
MKPortal©2003-2008 mkportal.it
MultiBoard ©2007-2009 RusMKPortal