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

В 1970-1971 годах Е.Ф.Кодд опубликовал две статьи, в которых ввел реляционную модель данных и реляционные языки обработки данных – реляционную алгебру и реляционное исчисление. Хотя реляционная модель сама по себе имела важное значение, именно реляционные языки оказались серьезным основанием для реляционной революции в базах данных.

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

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

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

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

Объединение. Операция реляционной алгебры, создающая теоретико-множественное объединение двух объединительно-совместимых реляционных таблиц. Объединительная совместимость требуется для того чтобы результатом выполнения операции объединения была реляционная: таблица. Операция объединения (U) позволяет нам комбинировать данные из двух таблиц С:=А U В

Пересечение. Операция реляционной алгебры, создающая пересечение в теоретико-множественном смысле двух объединительно-совместимых реля­ционных таблиц. Операция пересечения (∩) позволяет нам идентифицировать строки, об­щие для двух таблиц. Результатом выполнения операции пересечения будет реляционная таб­лица, состоящая из всех строк, встречающихся в обеих исходных таблицах. То есть, если С – пересечение А и В:

С:= А ∩ В, то С состоит из тех строк, которые есть и в А, и в В. Как и ранее, А и В должны быть объединительно-совместимы.

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

С:= А – В, то строками С являются те строки, которые есть в А, но которые отсут­ствуют в В.

Обратите внимание, что А – В не совпадает с В – А. Таким образом, порядок таблиц в операции разности очень важен. Отметим, что таблицы должны быть объединительно-совместимыми. Операцию разности можно также назвать операцией вычитания. Вычитание – о перация взятия разности в реляционной алгебре.

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

Произведение С:= А*В создается путем:

1. Связывания, или соединения, атрибутов двух таблиц.

2. Присоединения к каждой строке таблицы А каждой строки таблицы В. Таким образом, атрибутами С будут все атрибуты А и В вместе взятые. Если таблицы А и В имеют по два атрибута каждая, то С будет иметь четыре атрибута. Строки С созданы соединением строк А и В; Каждая строка А связана с каждой строкой В. Если в В три строки, каждая строка А (2 строки) связывается с тремя строками В и повторяется в строках С три раза. Легко видеть, что число строк С всегда будет равно произведению числа строк А на число строк В. Операция произведения используется в языке запросов SQL, который является наиболее важным коммерческим реляционным языком.

Выборка. Операция реляционной алгебры, производящая отбор строк из таблицы на основании некоторого условия. Операция выборки используется для создания реляционной таблицы из другой реляционной таблицы путем отбора только тех строк, которые удовлетворяют заданному условию. С:= SELЕСТ (имя таблицы: условие выбора).

Например SР_ТОКУО:= SELЕСТ (SALESPERSON: OFFICE = «Токио»)

Можно использовать операторы сравнения =, <, >, <=, >=. Для каждого из них есть соответствующий оператор, использующий булеву операцию «не». Можно использовать булевы операторы «и» и «или». «Не» также можно использовать в общем случае для отрицания всего условия.

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

квадратных скоб­ках перечисляем те столбцы, которые необходимо оставить. Например, С:=SР_ТОКУО [SALPERS_NAME]. Операция автоматически исключает повторы из результирующей таблицы. Это происходит и в том случае, когда результирующая таблица содержит более одного столбца.

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

Естественное соединение. Операция соединения, связывающая таблицы, когда общие столбцы имеют равные значения. Операция естественного соединения записывается следующим образом: Д:=JOIN (А,В).

Общее определение естественного соединения: Предположим, что необходимо взять естественное соединение двух таблиц А и В, имеющих общие строки С1,...,Сп. Тогда операция JOIN (А, В) выполняется за следую­щие три шага:

1. Берется произведение таблиц А и В. В результате получается таблица, содержащая по два столбца на каждый С1,...,Сп.

2. Из таблицы произведения исключаются все строки кроме тех, в которых значения столбцов С1,..,Сп из таблицы А равны соответственно, значе­ниям этих столбцов в В.

3. Проектированием исключается одна копия столбцов С1.....Сп.

Как показывает общее определение, если две реляционные таблицы имеют более одного об­щего столбца, то соединение производится на основании равенства значений во всех общих столбцах. Если таблица А имеет k столбцов, а таблица В имеет m столбцов, то естественное соединение таблиц А и В будет состоять из (k+m-n) столбцов, где n – число общих столбцов таблиц А и В.

Тета-соединение – это соединение с определенным условием, в котором участвуют столбцы из каждой таблицы. Это условие означает, что два столбца будут определенным образом сравниваться. Оператор сравнения мо­жет быть любой из шести следующих: =, не =, <,>, <=, >=

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

Общий вид тета-соединения таков:

С:=JOIN (а, В: X δ У),

где А и В – соединяемые таблицы, X и У – столбцы из этих двух таб­лиц, а греческая буква δ обозначает один из шести операторов, перечислен­ных выше.

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

Эквисоединение. Тета-соединение, основанное на равенстве определенных столбцов.

Тета-соединение, в отли­чие от естественного соединения, не включает удаление одного или более столбцов на последнем шаге. Другими словами, если таблица А содержит k столбцов, а таблица В – m столбцов, то тета-соединение А и В будет состо­ять из k+m столбцов.

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

Общее описание операции следующим обра­зом. Допустим, что А, В – реляционные таблицы, тогда С:= А/В

1. Столбцы В должны составлять подмножество множества столбцов А. Столбцами С будут только те столбцы А, которые не являются столбцами В.

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

Операция деления является обратной к операции произведения. Легко проверить, что если таблица является произведением двух таблиц В и С, то мы можем получить таблицу В, разделив произведение на С. То есть (В * С) /C = В.

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

Присвоение. Операция реляционной алгебры, дающая имя таблице.