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

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

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



История

Реляционная модель данных (РМД) относится к теоретико-множественным моделям данных. Появление теоретико-множественных моделей в системах баз данных (БД) было предопределено настоятельной потребностью пользователей в переходе от работы с элементами данных, как это делается в теоретико-графовых моделях [1], к работе с некоторыми макрообъектами.

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

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

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

алгебра реляционный отношение результирующий

Реляционная модель данных (РМД) - это способ рассмотрения данных, при котором данные воспринимаются пользователем как таблицы и в распоряжении пользователя имеются некоторые операторы, которые генерируют новые таблицы из старых.

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

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

Основной структурой данных в РМД является отношение (от англ. relation - отношение). Отсюда возникло название модели, основанной на отношениях: такую модель стали называть реляционной моделью данных.

Введем некоторые определения.

N-арным отношением R называют подмножество декартова произведения множеств .

Исходные множества называют доменами.

, (1)

где - полное декартово произведение множеств.

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

Например, пусть имеются три домена (три некоторых множества):

- содержит наименования складов торговой фирмы;

- содержит наименования групп товаров;

- содержит наименования товаров, которыми торгует фирма.

Предположим, что содержимое доменов следующее:

= {Склад №1, Склад №2};

= {Стройматериалы, Бытовая химия};

= {Кирпич, Шифер, Мыло, Порошок}.

Тогда полное декартово произведение содержит набор из 16 троек (2x2x4), где первый элемент - один из складов фирмы, второй - название группы товаров, третий - наименование товара:

=	{<Склад №1, Стройматериалы, Кирпич>, <Склад №1, Стройматериалы, Шифер>, <Склад №1, Стройматериалы, Мыло>, <Склад №1, Стройматериалы, Порошок>, <Склад №1, Бытовая химия, Кирпич>, <Склад №1, Бытовая химия, Шифер>, <Склад №1, Бытовая химия, Мыло>, <Склад №1, Бытовая химия, Порошок>, <Склад №2, Стройматериалы, Кирпич>, <Склад №2, Стройматериалы, Шифер>, <Склад №2, Стройматериалы, Мыло>, <Склад №2, Стройматериалы, Порошок>, <Склад №2, Бытовая химия, Кирпич>, <Склад №2, Бытовая химия, Шифер>, <Склад №2, Бытовая химия, Мыло>, <Склад №2, Бытовая химия, Порошок> }

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

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

R = {<Склад №1, Стройматериалы, Кирпич>,

<Склад №1, Стройматериалы, Шифер>,

<Склад №2, Стройматериалы, Шифер>,

<Склад №2, Бытовая химия, Мыло>,

<Склад №2, Бытовая химия, Порошок>}.

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

R

Склад	Группа товаров	Товар
Склад №1	Стройматериалы	Кирпич
Склад №1	Стройматериалы	Шифер
Склад №2	Стройматериалы	Шифер
Склад №2	Бытовая химия	Мыло
Склад №2	Бытовая химия	Порошок

Наборы из n значений называют n-ками.

Представленная таблица (отношение в виде таблицы) обладает рядом свойств:

1. Таблица имеет столбцы, соответствующие доменам.

2. Каждый столбец имеет уникальное имя.

3. В таблице нет двух одинаковых строк.

4. Порядок строк и столбцов в таблице произвольный.

Домен - множество всех допустимых значений какого-либо свойства или признака объекта (рис.1.1). При этом значения признака соответствуют определенному типу данных. Примерами элементарных доменов являются целые числа, дробные числа, строки и т.д. Одному домену может соответствовать несколько атрибутов, а одному атрибуту - несколько доменов. Например, домен «Текстовая строка» определяет множество допустимых значений для таких атрибутов как «Наименование склада», «Наименование товара», «Единица измерения» и пр. В то же время атрибут «Наименование склада» может быть определен доменом «Наименование объектов», как текстовой строки размером 50 знаков.

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

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

Степень отношения - это количество атрибутов в отношении.

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

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

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

Пример отношения «Остатки товаров на складах»

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

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

.

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

= {=, <>, >=, <=, <, >}.

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

- схема отношения R1

- схема отношения R2 после упорядочивания имен атрибутов.

Тогда,

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

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

Отсутствие кортежей-дубликатов.

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

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

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

Отсутствие упорядоченности кортежей.

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

Отсутствие требования к поддержанию порядка на множестве кортежей отношения дает дополнительную гибкость СУБД при хранении баз данных во внешней памяти и при выполнении запросов к базе данных. Это не противоречит тому, что при формулировании запроса к БД, например, на языке SQL можно потребовать сортировки результирующей таблицы в соответствии со значениями некоторых столбцов. Такой результат не является отношением, а представляет собой некоторый упорядоченный список кортежей.

Отсутствие упорядоченности атрибутов.

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

Атомарность значений атрибутов.

В любом отношении значения всех атрибутов должны быть атомарными (неделимыми).

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

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

Реляционная алгебра - множество отношений с замкнутым на нем множеством операций над отношениями.

Основным множеством в реляционной алгебре является множество отношений. Э.Ф. Кодд предложил 8 операций над отношениями (рис.1.2). В общем случае это множество операций является избыточным, т.к. одни операции можно выразить через другие. Однако, именно такой минимальный состав операций был выбран для того, чтобы обеспечить максимальное удобство при работе с отношениями.

Все множество операций над отношениями можно разделить на две группы (рис.1.2):

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

- специальные операции.

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

Операции реляционной алгебры



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

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

Выделяют следующие теоретико-множественные операции:

­ объединение;

­ пересечение;

­ разность;

­ расширенное декартово произведение.

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

Пусть заданы два отношения , , где r₁ и r₂ - соответственно кортежи отношений R₁ и R₂, тогда объединение

,

где r - кортеж нового отношения; - операция логического «ИЛИ».

Рассмотрим пример данной операции.

Предположим, имеются отношения R₁ и R₂, которые содержат
списки деталей, изготавливаемых соответственно на первом и втором участках цеха. Отношение R₃ содержит общий перечень деталей, изготавливаемых в цехе.

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

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

,

где r - кортеж нового отношения; - операция логического «И».

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

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

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

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

,

.

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

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

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

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

1. Операции сразу целиком выполняются на отношениях.

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

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

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

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

,

где - число элементов в первом кортеже, - число элементов во втором кортеже.

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

Т.е. если , , то

.

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

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

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

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

Универсум не имеет самостоятельного значения, но может активно использоваться в операциях над данными. Так, операцию расширенного декартова произведения (или получения универсума) нужно использовать во всех ситуациях, которые характеризуются словом «все».

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

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

Специальные операции реляционной алгебры

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

Терм сравнения - это элементарное (неделимое) логическое выражение, состоящее из сравниваемых выражений левой и правой части, разделенных операцией сравнения.

Пусть - логическое выражение, состоящее из термов сравнения с помощью связок (И, ИЛИ, НЕ).

В качестве термов сравнения допускаются:

а) терм А ос а,

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

б) терм А ос B,

где A, B - имена некоторых -сравнимых атрибутов, т.е. атрибутов, принимающих значение одного и того же домена.

Тогда результатом выбора, или фильтрации, заданной на отношении R в виде булевского выражения , называется отношение R[a], включающее те кортежи из исходного отношения, для которых истинно условие выбора или фильтрации:

.

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

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

Пример:

Пусть необходимо выбрать из R₁₀ детали с шифром «110033».

R₁₂ = R₁₀ [Шифр детали = «11003»]

Вертикальный выбор (проекция)

Проекцией отношения R на набор атрибутов B (R[B]) называется отношение со схемой, соответствующей набору атрибутов S_R[B] = B, содержащему кортежи, получаемые из исходного отношения R путем удаления из них значений, не принадлежащих атрибутам из набора B.

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

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

Пример:

Пусть необходимо выбрать все цеха, которые изготавливают деталь «Болт М1».

Для этого необходимо из отношения R₁₀, содержащего фактическую номенклатуру производства по цехам, выбрать детали с заданным названием, а потом полученное значение спроецировать на столбец «Цех».

R₁₃ = R₁₀ [ Название детали = «Болт М1» ]

R₁₄ = R₁₃ [ Цех ]

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

Операция условного соединения

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

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

Предположим, что имеется некоторое отношение R₁₅ (Схема отношения = {Шифр детали, Название детали, Название материала}), которое содержит перечень деталей с указанием материалов, из которых они изготавливаются.

Рассмотренное выше отношение R₁₀ (Схема отношения = {Шифр детали, Название детали, Цех}) содержит список деталей, которые фактически производятся в цехах.

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

Как видно из представленных ниже отношений, список деталей, которые изготавливаются в цехе «Цех 1», можно получить из отношения R₁₀, применив операцию горизонтального выбора по атрибуту «Цех».

R₁₆ = R₁₀ [ Цех = «Цех 1»].

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

Однако, требуется получить не все детали, которые производит «Цех 1», а только те из них, которые произведены из материала «сталь-ст1». Следовательно, необходимо соединить два отношения по атрибуту «Шифр детали» с тем, чтобы получить отношение, в котором наряду со сведениями по номенклатуре производства по цехам также будут сведения по материалам, необходимых для их производства.

R₁₇ = R₁₅[R₁₅.Шифр детали = R₁₀.Шифр детали]R₁₀.

В результате получим новое отношение, каждый кортеж которого будет представлять собой сцепление кортежей отношения R₁₅ c кортежами отношения R₁₀, удовлетворяющими условию:

R₁₅.Шифр детали = R₁₀.Шифр детали.

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

Теперь необходимо провести операцию горизонтального выбора по условию [(R₁₇.Название материала = «сталь-ст1») (R₁₇.Цех = «Цех 1»)].

R₁₈ = R₁₇[(R_17.Название материала = «сталь-ст1») (R₁₇.Цех = «Цех 1»)]

Теперь для получения общего результата необходимо выполнить операцию вертикального выбора по атрибуту «Цех»: R₁₉= R₁₈[Цех].

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

Запишем операцию условного соединения одним оператором:

R₁₇=R₁₅[R₁₅.Шифр детали = R₁₀.Шифр детали]R₁₀.

R₁₈ = R₁₇[(R_17.Название материала = «сталь-ст1») (R₁₇.Цех = «Цех 1»)].

R₁₉= R₁₈[Цех].

R₁₉= (R₁₅[(R₁₅.Шифр детали = R₁₀.Шифр детали) (R₁₅.Название материала = «сталь-ст1») (R₁₀.Цех = «Цех 1»)]) R₁₀) [Цех].

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

Дополнительные операции с отношениями

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

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

Пример:

Информация о продаваемых товарах собирается в отношении R₂₀.

R₂₀

Дата операции	Покупатель	Наименование товара	Количество	Цена, руб	Сумма
04.05.2003	ООО "ОРИОН"	Товар 1	5 000	7,5	37 500
04.05.2003	ООО "ОРИОН"	Товар 2	12 000	6	72 000
04.05.2003	ООО "ОРИОН"	Товар 3	2 000	20	40 000
08.05.2003	ООО "Дельта"	Товар 2	2 000	6	12 000
Дата операции	Покупатель	Наименование товара	Количество	Цена, руб	Сумма
08.05.2003	ООО "Дельта"	Товар 3	30 000	20	600 000
11.05.2003	ООО "Пингвин"	Товар 3	1 600	20	32 000
11.05.2003	ООО "Пингвин"	Товар 1	5 000	7,5	37 500
18.05.2003	ООО "Дельта"	Товар 1	5 000	7,5	37 500
18.05.2003	ООО "Дельта"	Товар 3	30 000	20	600 000

Тогда группировка по атрибуту «Покупатель» будет означать объединение кортежей (строк).

R₂₁ = группировка по атрибуту «Покупатель» (R₂₀)

В результате получим из отношения R₂₀ список покупателей продукции.

R₂₁

Покупатель
ООО "ОРИОН"
ООО "Дельта"
ООО "Пингвин"

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

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

R₂₂ = группировка по атрибуту «Покупатель» и атрибуту «Товар» ( R₂₀ )

В результате получим новое отношение R₂₂ на основе исходного отношения R₂₀ путем объединения строк таблицы, у которых значения атрибутов «Покупатель» и «Товар» являются одинаковыми.

R₂₂

Покупатель	Товар
ООО "Дельта"	Товар 1
ООО "Дельта"	Товар 2
ООО "Дельта"	Товар 3
ООО "ОРИОН"	Товар 1
ООО "ОРИОН"	Товар 2
ООО "ОРИОН"	Товар 3
ООО "Пингвин"	Товар 1
ООО "Пингвин"	Товар 3

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

Предположим, необходимо на основе отношения R₂₀ получить объемы продаж по каждому товару. Операцию группировки запишем в следующем виде:

R₂₃ = группировка по атрибуту «Покупатель» (R₂₀)

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

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

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

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

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

6. Применить операции реляционной алгебры к исходным отношениям на каждом шаге.

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

Литература

1. Дейт К. Введение в системы баз данных: Пер. с англ. - 6-е изд. - СПб.: Вильямс, 1999.

2. Карпова Т.С. Базы данных: модели, разработка, реализация. - СПб.: Питер, 2001.

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