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

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

Наиболее важной частью ЯМД является раздел формулировки запросов, который должен обладать достаточной выразительностью. Разработано три типа ЯМД:

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

2) реляционное исчисление с переменными кортежами

3) реляционное исчисление с переменными доменами.

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

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

Рассмотрим основные операции:

1. Объединение отношений R = R₁ U R₂

Применяется только к отношениям одной и той же –арности.

а б в

R₁: д е а R₂: и к л

и к л г д е

R₁ ÈR₂ : а б в

д е а

и к л

г д е

2. Разность отношений R = R₁ -R₂

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

R₁ -R₂: а б в

д е а

3. Декартово произведение R = R₁ * R₂

Если отношение R₁ имеет арность К₁, а отношение R₂ арность К₂, то декартовым произведением R₁*R₂ является множество кортежей арности К₁+К₂, при чем первые К₁ элементов образуют кортеж из отношения R₁, а последние К₂ элементов – кортеж из описания R₂

а б в и к л

д е а и к л

и к л и к л

а б в г д е

д е а г д е

и к л г д е

4. Проекция отношения R₁ на компонент i₁, i₂,..,i_r R=Пi₁,i₂,…,i_r (R1), где i₁,i₂,…,i_r – номера столбцов отношения R₁

Операция проекции заключается в том, что из отношения R1 выбираются столбцы с индексами i₁, i₂,..,i_r и компонуются в указанном порядке

R=П_1,2 (R₁) а б R= П_3,1 (R₁) в а

д е а д

и к л и

5. Селекция отношения R₁ по формуле F: R =σ_F(R₁), где F – формула, образованная операндами, являющимися номерами столбцов, логическими операторами «И», «ИЛИ», «НЕ» и операциями сравнения < = > ≤ ≥ ≠. Могут использоваться скобки.

R = σ_1=a v₁=д(R₁); R = σ_2=к (R₁);

а б в и к л

д е а R = σ_1≠3 (R₁)

а б в

д е а

и к л

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

1. Пересечение: R= R₁ ∩ R₂ = R₁ - (R₁ - R₂)

R₁ и к а н R₁ и к н а R₁ ∩ R₂: с а м д

с а м д с а м б о л р б

и к б в р к б в

о л р б о л р б

д в е н е д в и

2. Соединение отношений R₁ >< R₂, Ө - оператор сравнения, i, j – номера столбцов в отношениях R₁ и R_2. ^{i ө j}

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

R₁ А В С R₂ Д Е R₁ > < R₂

а б в а и ^В=Д

а и р е к А В С Д Е

д е ж д е ж е к

Полученная система операций реляционной алгебры образует полный язык.

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

Централизация и децентрализация процессов обработки данных.

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

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

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

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

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

- большой объем общих данных;

- защита данных;

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

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

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

- все данные распред. Б.Д. полностью дублируются в каждом узле сети;

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

- распределенные БД м.б. однородными или неоднородными в смысле используемых в системе технических и программных средств (СУБД). Если используются разные СУБД, то д.б. решена проблема преобразования структур данных и прикладных программ, т.к. для пользователей д.б. обеспечена прозрачность этих преобразований.

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

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

- д.б.решен вопрос о синхронизации процессов обновления и обработки копий данных;

- необходимо решить вопрос защиты данных и их восстановления;

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

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

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

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

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

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

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

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

Нормализованное отношение R находится в 3НФ, если каждая детерминанта является возможным ключом.

Рассмотрим другой пример.

Отношение СКП (студент, курс, преподаватель)

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

– каждый преподаватель преподает только один предмет;

– каждый предмет преподается нескольким преподавателям.

Из 1-го имеется функциональная зависимость (С, К) ® П

Из 2-го П ® К К ® П нет функциональной зависимости

СКП

С	К	П
Смит	Математика	проф. Вайт
Смит	Физика	проф. Грин
Джонс	Математика	проф. Вайт
Джонс	Физика	проф. Браун

Заменяем отношение СКП двумя проекциями в 3НФ СП и ПК.

Пример. Отношение ЭКЗАМЕН с атрибутами С(студент), К(предмет), М(место). Конкретный студент экзаменуется по определенному предмету и занимает определенное место.

– никакие два студента не могут занять одно и то же место по одному и тому же предмету. Имеем два возможных ключа (С,К) и (К,М). Ключи перекрываются. Отношение находится в 3НФ, т.к. ключи являются единственными детерминантами.

Пример отношения КПУ (курс, преподаватель, учебник)

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

КУРС	ПРЕПОДАВАТЕЛЬ	УЧЕБНИК
Физика	проф. Грин	Основы механики
Физика	проф. Грин	Законы оптики
Физика	проф. Браун	Основы механики
Физика	проф. Браун	Законы оптики

Ключ – весь кортеж. КПУ находится в 3НФ. Говорят, что атрибут КУРС «многозначно определяет» атрибут ПРЕПОДАВАТЕЛЬ, или существует «многозначная зависимость» ПРЕПОДАВАТЕЛЬ от КУРС. ПРЕПОДАВАТЕЛЬ не зависит функционально от КУРС, но каждый курс имеет хорошо определенное множество, соответствующих преподавателей. Множество значений ПРЕПОДАВАТЕЛЬ для заданной пары значений КУРС и УЧЕБНИК зависят только от конкретного значения КУРС, а значение УЧЕБНИК несущественно. Многозначные зависимости не являются функциональными зависимостями. Проекция КП и КУ не содержат таких зависимостей.

Некоторые отношения R(A, B, C), в котором B и C многозначно зависят от A, всегда эквивалентно соединению по А двух проекций R₁(A, B) и R₂(A, C).

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

Процесс сводится к устранению аномалий.

2НФ а) устраняем не полные функциональные зависимости

3НФ б) устраняем транзитивные зависимости

4НФ в) устраняем многозначные зависимости.

Традиционный набор операций

Для операций объединения, пересечения и вычитания оба участвующих отношения должны быть совместимы по объединению, т.е. они должны иметь одну и ту же степень n и j-й атрибут одного из них дожжен быть из того же домена, что и j-й атрибут другого (1 ≤ j ≤ n).

Объединением отношений A и B (A U B) называется множество всех кортежей t, принадлежащих или A, или B, или обоим вместе.

A – множество поставщиков, находящихся в Лондоне.

В – множество поставщиков, поставляющих деталь д1.

A U B – п1 Смит 20 Лондон

п4 Кларк 20 Лондон

п2 Джонсон 10 Париж

Пересечением отношений A и B (A ∩ B) называется множество всех кортежей t, принадлежащих как A, так и B.

A ∩ B – п1 Смит 20 Лондон

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

A - B – п4 Кларк 20 Лондон

Расширенным декартовым произведением отношений A и B (A*B) является множество всех кортежей t, таких что t есть конкатенация кортежей aÎA, и кортежей bÎB.

a=(a₁,…,a_m) b=(b_m+1,…,b_m+n)

t=(a₁,…,a_m,b_m+1,…,b_m+n)