Лекция

Фактографические БД. Реляционная алгебра и реляционное исчисление. Основные операции реляционной алгебры и реляционного исчисления при обработке данных

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

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

1) понятен пользователю-непрограммисту;

2) позволяет легко изменять схему – присоединять новые элементы данных и записи без изменения соответствующих подсхем;

3) обеспечивает необходимую гибкость при обработке непредвиденных запросов.

В математических дисциплинах понятию «таблица» соответствует понятие «отношение» (relation). Отсюда и произошло название модели – реляционная. Т.е., применительно к базам данных понятия «реляционная БД» и «табличная БД» по существу являются синонимами.

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

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

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

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

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

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

Остальные ключи, которые можно также использовать в качестве первичных, называются потенциальными или альтернативными ключами.

Модель предъявляет к таблицам следующие требования:

1. данные в ячейках таблицы должны быть структурно неделимыми;

2. данные в одном столбце должны быть одного типа;

3. каждый столбец должен быть уникальным (недопустимо дублирование столбцов);

4. столбцы размещаются в произвольном порядке;

5. строки размещаются в таблице также в произвольном порядке;

6. столбцы имеют уникальные наименования.

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

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

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

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

К числу операций реляционной алгебры (в том виде, в котором она была определена Э.Ф. Коддом) относят следующие: (слайд 7)

- бинарные операции:

- объединение

- пересечение

\ - разность

- декартово произведение

J - соединение

/ - деление

- унарные операции:

S - выборка

Pr - проекция.

Этот набор операций можно классифицировать следующим образом:

- теоретико-множественные операции (аналогичные одноименным операциям в теории множеств): объединение, пересечение, разность, декартово произведение;

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

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

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

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

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

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

Выборка. Пусть задано логическое выражение – условие отбора F с атрибутами некоторой реляционной таблицы R. Тогда результатом выборки S_F(R) будет подмножество множества записей R, для которых F имеет значение истина (слайд 12).

Проекция. Пусть реляционная таблица R имеет n атрибутов. Зададим подмножество атрибутов a₁, a₂, …, a_m (m≤n). Тогда результатом проекции будет реляционная таблица, имеющая m атрибутов из n атрибутов таблицы R. Следует отметить, что в результате операции количество кортежей может уменьшиться, т.к. по определению отношение не может содержать одинаковые кортежи (слайд 13).

Соединение. Рассмотрим вариант так называемого естественного соединения двух реляционных таблиц по равенству значений заданных атрибутов. Будем считать, что в отношениях сравниваются одноименные атрибуты. Тогда естественным соединением отношений R и P по равенству атрибутов a₁, a₂, …, a_m (каждый из которых присутствует в обоих отношениях) будет отношение, полученное после выборки из декартового произведения отношений R и P только тех кортежей, на которых значения заданных в операции атрибутов совпадают. При этом значения одноименных атрибутов в результирующем кортеже появляются один раз, а не дважды (слайд 14).

Деление. Отношение, полученное в результате деления R/P, содержит в качестве атрибутов те, и только те атрибуты делимого R, которые отсутствуют в делителе P, а в качестве кортежей в результат деления включаются те кортежи делителя, которые при декартовом умножении частного на делитель P содержаться в делимом R (слайд 15).

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

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

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

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

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

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

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

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

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

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

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

4.3. Реляционное исчисление

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

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

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

В логике первого порядка (или теории исчисления предикатов) под предикатом подразумевается истинностная функция с параметрами. После подстановки значений вместо параметров функция становится выражением, называемым суждением, которое может быть истинным или ложным. Например, предложение «Иванов И.И. является сотрудником данного ВУЗа» является суждением, поскольку можно определить его истинность или ложность.

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

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

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

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