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

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

Содержание

Введение

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

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

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

1.3 Замкнутость реляционной алгебры

2. Реляционные исчисления

2.1 Реляционные операторы

2.2 Выражение реляционного исчисления

2.3 Реляционные исчисления с переменными на доменах

Заключение

Список литературы

Введение

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

Автоматизация процессов и хранения информации дает возможность обрабатывать намного больше информации и с большей надежностью, при этом время обработки сокращается. Применение компьютеров для автоматизации информационных процессов нуждается в соответствующих программных средствах, которые в свою очередь нуждаются в серьёзной теоретической базе. Опыт применения ЭВМ для построения прикладных средств показывает, что самым эффективным средством здесь являются не универсальные алгоритмические языки, а специализированные языки для сoздания систем управления данными. Эти средства включены в состав систем управления базами данных (СУБД), но они могут существовать и отдельно. Пpи помощи СУБД пользователи могут осуществлять непосредственное управление данными, а программисты быстрo разрабатывают более совершенные средства их обработки. Реляционная модель - это один из способов установления связей между данными.

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

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

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

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

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

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

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

Реляционная алгебра -- это замкнутая система операций над отношениями в реляционной модели данных. Операции реляционной алгебры также называют реляционными операциями. Набор операций впервые был предложил Э. Кодд в 1970-е годы. Набор состоял из 8 операций. Это те операции, которые до сих пор используются (проекция, соединение и т.д.), и которые не вошли в употребление (например, деление отношений). В процессе развития реляционной теории и практики были разработаны новые реляционные операции, например полусоединение (SEMI-JOIN) и полуразность, или анти-полусоединение (ANTI-SEMI-JOIN), CROSS APPLY и OUTER APPLY, транзитивное замыкание (TCLOSE) и др. Поскольку многие операции выражались друг через друга, в составе реляционной алгебры можно было выделить несколько вариантов базиса (набора операций, через который выразимы все остальные). Наиболее известный и строго определённый базис (алгебра А) предложен Кристофером Дейтом и Хью Дарвеном.

Главная мысль реляционной алгебры произведено в том, собственно что коль быстро дела считаются огромными количествами, способы манипулирования отношениями имеют все шансы базироваться на классических теоретико-множественных операциях, дополненных кое-какими особыми операциями, специфическими для реляционных баз данных. Есть большое количество раскладов к определению реляционной алгебры, которые отличаются наборами операций и методами их интерпретации, но, в принципе, считаются больше или же наименее равносильными. В предоставленном разделе мы опишем исходный вариант алгебры, который был предложен Коддом (будем именовать ее «алгеброй Кодда»). В данном варианте комплект ведущих алгебраических операций произведено из 8 операций, которые разделяются на 2класса - теоретико-множественные операции и особые реляционные операции. В состав теоретико-множественных операций входят операции:

· объединения отношений;

· пересечения отношений;

· взятия разности отношений;

· взятия декартова произведения отношений.

Специальные реляционные операции включают:

· ограничение отношения;

· проекцию отношения;

· соединение отношений;

· деление отношений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RENAME WHERE = PROJECT TIMES = JOIN = INTERSECT = DIVIDE BY UNION = MINUS

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

Рис. 1. Таблица приоритетов операций традиционной реляционной алгебры

1.3 Замкнутость реляционной алгебры

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

Заголовок отношения состоит из множества пар: <имя-атрибута, имя-домена>. Если рассмотреть общий обзор реляционных операций, приведенный в данной рабoте, тj видно, что домены атрибутов результирующего отношения однозначно определяются доменами отношений-операндов. Однако с именами атрибутов результата не всегда все так просто. Например, если у отношений-операндов операции декартова произведения имеются одноименные атрибуты с одинаковыми доменами, то какой должен быть заголовок результирующего отношения? Так как мы рассматриваем множество, а в нем не должны содержаться одинаковые элементы. Но и потерять атрибут в результате недопустимо. Это значит, что в таком случае вообще невозможно корректно выполнить операцию декартова произведения.

Аналогичные проблемы могут возникнуть и в случаях других двуместных операций. Чтобы разрешить проблему, то в число операций реляционной алгебры вводится операция переименования. Ее следует применять в том случае, когда возникает конфликт именования атрибутов в отношениях-операндах одной реляционной операции. В этом случае к одному из операндов сначала применяется операция переименования, а затем основная операция выполняется уже без всяких проблем. Более строго можно определить операцию переименования в следующей лекции, а пока лишь заметим, что результатом этой операции является отношение, совпадающее во всем с отношением-операндом, кроме того, что имя указанного атрибута изменено на заданное имя. В дальнейшем изложении предположим, что применение операции переименования во всех конфликтных ситуациях. Можно заметить, что невозможно применить некоторых операций к произвольным парам значений отношений без предварительного переименования атрибутов отношений операндов. Это означает, что «алгебра» Кодда не является алгеброй отношений в математическом смысле. Описываемая Алгебра A такими недостатками не обладает: результатом применения любой операции к любым отношениям является некоторое отношение.

2. Реляционные исчисления

2.1 Реляционные операторы

реляционный алгебра предикат кортеж

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

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

Основными понятиями исчисления являются понятие переменной с некоторой областью допустимых значений и понятие правильно построенной формулы (WFF - well formulated formula), опирающейся на предикаты, переменные и кванторы. В зависимости от области определения переменной различают исчисление кортежей и исчисление доменов. Вычислении кортежей областью определения переменных являются отношения базы данных, т.е. допустимым значением каждой переменной является кортеж некоторого отношения. В исчислении доменов областью определения переменных являются домены, на которых определены атрибуты отношений базы данных, то есть допустимым значением каждой переменной является значение некоторого домена.

2.2 Выражение реляционного исчисления кортежей

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

RANGE OF T IS X1, X2, …, Xn. (1)

Здесь Т - определяемая переменная кортежа, а Xi (i = 1, 2, …, n) - либо имя отношения, либо выражение исчисления кортежей. Пусть Xi является отношением Ri (i = 1, 2, …, n). Отношения R1, R2, …, Rn должны быть совместимы по типу, т.е. они должны иметь идентичные заголовки. Тогда переменная кортежа Т изменяется на объединении этих отношений, т.е. ее значение в любое заданное время будет некоторым текущим кортежем по крайней мере одного из этих отношений. Конечно, если список идентификаторов выражений будет просто одним именованным отношением R (это обычный случай), то переменная кортежа будет просто принимать значения текущих кортежей одного такого отношения R. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной (это аналогично тому, как, например, при программировании на языке Pascal можно сослаться на значение поля переменной типа записи). Правильно построенная формула WFF служит для выражения условий, накладываемых на кортежные переменные. WFF состоит из простых сравнений скалярных значений (значений атрибутов переменных или литерально заданных констант). Более сложные варианты WFF строятся с помощью логических операций NOT, AND, OR, IF…THEN, и двух кванторов EXISTS и FORALL. Квантор EXISTS называется квантором существования, а квантор FORALL - квантором общности. Если f - формула WFF, в которой участвует переменная x, то EXISTS x ( f ) и FORALL x ( f ) являются допустимыми формулами WFF.

Первая формула означает: «существует по крайней мере одно значение переменной x, что вычисление формулы f для этого x дает значение истина». Вторая формула означает: «Для всех значений переменной x вычисление формулы f дает значение истина». Квантор существования EXISTS определяется формально, как повторяющееся OR (ИЛИ). То есть, если R - это отношение с кортежами Т1, Т2, …, Тm; Т - это переменная кортежа, которая изменяется на этом отношении; а f( T ) - это формула, в которой используется переменная Т, то формула EXISTS T ( f (T) ) определяется равносильно следующей формуле WFF: false OR ( f (T1)) OR … OR ( f (Tm) ). Квантор существования FORALL определяется, как повторяющееся AND (И). Другими словами, если R, T и f (T) такие же, как рассматривались выше, то формула FORALL T ( f ( T ) ) определяется равносильно следующей формуле:

true AND ( f ( T1 ) ) AND ... AND ( f ( Tm ) ). (2)

Переменные, входящие в WFF, могут быть свободными или связанными. Все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true, то эти значения кортежных переменных могут входить в результирующее отношение. Пусть f - формула WFF, в которой переменная x свободна. Если имя переменной x использовано сразу после квантора при построении WFF вида EXISTS x ( f ) или FORALL x ( f ), то в этой WFF и во всех WFF, построенных с ее участием, x - это связанная переменная. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся ее область определения.

Пусть T и K - две кортежные переменные, определенные на отношении R. Тогда, WFF EXISTS K (T.A > K.A) для текущего кортежа переменной T принимает значение true в том и только в том случае, если во всем отношении R найдется кортеж (связанный с переменной K) такой, что значение его атрибута A удовлетворяет внутреннему условию сравнения. Формула WFF FORALL K (T.A > K.A) для текущего кортежа переменной T принимает значение true в том и только в том случае, если для всех кортежей отношения R (связанных с переменной K) значения атрибута A удовлетворяют условию сравнения. Таким образом, кванторы в реляционном исчислении играют ту же роль, что декларации в языке программирования. Понятие свободной переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие связанной переменной аналогично понятию локальной переменной, описанной в текущей процедуре. Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком (target_list). Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:

T.A [AS X] (3)

где T - имя свободной переменной соответствующей WFF, а A - имя атрибута отношения, на котором определена переменная T, а X - это имя атрибута, результата вычисления элементов целевого списка. T, что эквивалентно наличию подсписка T.A1, T.A2,..., T.An, где A1, A2, ..., An включает имена всех атрибутов определяющего отношения;

N = T.A;

N - новое имя соответствующего атрибута результирующего отношения.

Последний вариант требуется в тех случаях, когда в WFF используются несколько свободных переменных с одинаковой областью определения. Выражением реляционного исчисления кортежей называется конструкция вида TARGET_LIST WHERE WFF. Значением выражения является отношение, тело которого определяется WFF, а набор атрибутов и их имена - целевым списком. Как указывалось выше, для описания реляционного исчисления кортежей использован синтаксис реального языка запросов QUEL. Если использовать традиционный синтаксис языка предикатов, то описание реляционного исчисления с переменными кортежей выглядит следующим образом. Выражение записывается в виде:

{t | y (t)} (4)

где t - единственная свободная переменная, обозначающая кортеж фиксированной длины (если необходимо указать арность кортежа, то используют запись t⁽ⁱ⁾; i - арность кортежа t); y - правильно построенная формула (WFF).

На рис. 2 представлен обзор рассмотренных элементов языка QUEL и их эквиваленты из языка предикатов.

Рис. 2. Элементы синтаксиса языка QUEL и языка предикатов

2.3 Реляционное исчисление с переменными на доменах

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

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

R (pair, pair,…), (5)

где каждая пара pair имеет вид t:v, при этом v - это либо литерально задаваемая константа, либо имя доменной переменной. Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий значения указанных атрибутов. Если v - константа, то на атрибут t задается жесткое условие, не зависящее от текущих значений доменных переменных; если же v - имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной.

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

Далее будем считать, что существуют переменные доменов с именами, образуемыми добавлением цифр 1, 2, 3, ... к соответствующим именам доменов. Кроме того предполагается, что в базе данных поставщиков и деталей каждый атрибут имеет такое же имя, как и соответствующий ему домен, за исключением атрибутов ПФАМ и ДНАЗВ, для которых соответсвующий домен называется просто ИМЯ.

Реляционное исчисление доменов является основой большинства языков запросов, основанных на использовании форм. В частности, на этом исчислении базируется известный язык QBE (Query-by-Example), который был первым (и наиболее интересным) языком в семействе языков, основанных на табличных формах.

Заключение

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

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

1. Теоретико-множественные операторы: объединение, пересечение, вычитание, декартово произведение.

2. Специально реляционные операторы: выборка, проекция, соединения, деления.

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

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

Список литературы

1. Грей П. Логика, алгебра и базы данных. -- М.: Машиностроение, 1989. -- С. 188-213. -- 368 с.

2. Русскоязычное издание: Дейт К. Д., Дарвен Х. Основы будущих систем баз данных: Третий манифест. -- 2-е изд. -- М.: Янус-К, 2004. -- С. 656. -- ISBN 5-8037-0183-1.

3. https://ru.wikipedia.org/wiki/Реляционная_алгебра

4. bgtu-ief.com/index.php?option=com_content&view.

5. https://www.opennet.ru/docs/RUS/psql_tutor/sql534.html

6. www.rfe.by/media/kafedry/kaf5/publikation/kozadaev/.../lection-05.doc

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