Модуль1_Организация и управление БД

1.Объединение отношений. Объединением отношений R US

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

R US = { r | r R r S }.

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

Например, если сведения по учебным лабораториям разных факультетов (1) представлены следующими, имеющими одинаковые структуры, отношениями

ЛАБОРАТОРИЯ_РТФ (Название, Изучаемый предмет, Используемое оборудование), ЛАБОРАТОРИЯ_ФТФ (Название, Изучаемый предмет, Используемое оборудование),

то выражение ЛАБОРАТОРИЯ_РТФ U ЛАБОРАТОРИЯ_ФТФ создаст общий перечень учебных лабораторий на этих двух факультетах.

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

R \ S = { r | r R r S }.

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

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

ЛАБОРАТОРИЯ_РТФ \ ЛАБОРАТОРИЯ_ФТФ.

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

При необходимости результат пересечения отношений R и S вычисляется выражением R IS = R \ (R \ S).

42

3. Декартово произведение отношений. Данная операция выполняет сцепление (конкатенацию) кортежей исходных отношений. Сцеплением кортежей

a = <a1, a2, a3, . . . , an> и b = < b1, b2, b3, . . . , bm>

является кортеж, в котором значения (поля) второго кортежа добавлены к значениям первого, т.е. <a, b> = <a1, a2, a3, . . . , an, b1, b2, b3, . . . , bm>.

Декартовым произведением отношения R со схемой СR (A1, A2, . . ., An) и отношения S со схемой СS (B1, B2, . . . , Bm ) называется отношение со схемой С (A1, A2, . . ., An , B1, B2, . . . , Bm), кортежи которого <a, b>

образованы сцеплением каждого кортежа отношения R с каждым кортежом отношения S:

R × S = { <a, b> | a R b S }.

На рис. 6.2 результат операции декартова произведения представлен в графическом виде. Количество строк в результате произведения отношений равно произведению количеств строк в сомножителях (kr X ks ).

	Отношение R	Отношение S				Отношение R X S
kr					=
	. . . . . . . . .	X	. . . . .	ks
								kr X ks
	n					. . . . . . . . . . . . . . . .
			m
						n + m

Рис. 6.2. Декартово произведение отношений

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

43

интерес. Для фильтрации строк предусмотрена специальная операция –
селекция отношения.
4.	Селекция строк в отношении. Селекция отношения (Sel) - унарная
операция, выполняющая фильтрацию кортежей - «горизонтальную выборку»
по условию на значения данных. Операция селекции кроме отношения (R)
использует параметр (F), являющийся условием фильтрации и задаваемый
булевой функцией, построенной из высказываний (сравнений) вида:
<атрибут в R> <сравнение> <атрибут в R >		и/или
<атрибут в R > <сравнение> <константа>.
Здесь <сравнение> { >, <, <=, >= , =, # }.
Результатом селекции является множество кортежей отношения, для которых
функция F выполняется – принимает значение истина:
SelF(R)	= { r | r R F }.
Графически результат операции селекции может быть представлен в
следующем виде (см. рис. 6.3).
Отношение R
	Функция F- истинна
. . . . . . . . . . . . . . . .		SelF(R)
	Функция F- истинна
. . . . . . . . . . . . . . . .
	Функция F- истинна
. . . . . . . . . . . . . . . .			Строки отношения
	Функция F- истинна		R, для которых
			выполняется	F
	Рис. 6.3. Селекция отношения
Примером операции селекции может		служить	запрос:	Получить из
отношения СТУДЕНТ все сведения о студентах радиотехнического факультета:

Sel Факультет = ‘Радиотехнический’ (СТУДЕНТ).

44

5.Проекция отношения. Проекция отношения (Pr) - унарная

операция, реализующая			выбор подмножества		атрибутов (столбцов) из
отношения. Операция проекции кроме отношения (R)						использует параметры
(i1, i2,	i3, . . . , ik),	являющиеся именами		или номерами атрибутов			отноше-
ния R.	Результатом проекции являются кортежи отношения R, в						которых
представлены атрибуты, заданные параметрами i1,					i2,	i3, . . . , ik :
Pr i1, i2,	i3, . . . , ik (R) = {< a1, a2, a3, . . . , ak> | a1 = r i1 a2 = r i2 . . . . ak = r ik }.
Таким	образом,	проекция выполняет		выборку		заданных	столбцов

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

Отношение R

.......... .i1. . . . . . . . i2 . . . . i3 . . . . . . . . . . . . . . ik . . . .

i1	i2	i3	. . . . .	ik		Pr i1, i2, i3, . . . , ik (R)

Рис. 6.4. Проекция отношения R по атрибутам i1, i2, i3, . . . , ik

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

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

45

Проектирование результата предыдущего запроса позволит вывести только специальности и фамилии И.О. студентов радиотехнического факультета:

Pr Специальность, Фамилия И.О. (Sel Факультет = ‘Радиотехнический’ (СТУДЕНТ)).

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

1.Условное или Θ-соединение. Θ1-соединение является бинарной операцией, сцепляющей кортежи двух отношений – операндов R и S, но не каждого кортежа R с каждым кортежом S, а только, удовлетворяющих определенному условию. Для задания условия сцепления операция имеет параметр F, задаваемый булевой функцией, построенной из высказываний вида: <атрибут в R> <сравнение Θ > <атрибут в S>. Для обозначения атрибута можно использовать его имя, а если имена атрибутов совпадают, то уточнять имя атрибута именем отношения, отделяемым точкой:

<имя отношения>.< имя атрибута>.

Здесь, как и в операции селекции,

<сравнение Θ > { >, <, <=, >= , =, # }.

Θ-соединением отношения R со схемой СR (A1, A2, . . ., An ) и множеством кортежей вида a = <a1, a2, a3, . . . , an> с отношением S со схемой СS (B1, B2, . . . , Bm ) и кортежами вида b = < b1, b2, b3, . . . , bm> называется отношение со схемой С (A1, A2, . . ., An , B1, B2, . . . , Bm), кортежи которого

1 Θ (тэта) – буква греческого алфавита

46

<a, b> образованы сцеплением тех кортежей отношения R с такими кортежами отношения S, для атрибутов которых выполняется функция F:

R S = {<a, b> | a R b S F}.

F

Поскольку Θ-соединение является дополнительной операцией, ей соответствует эквивалентное по результату выражение из основных операций:

R S = Sel F (R X S).

F

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

Pr	( Лаборатории специальностей	Лаборатория),
Название специальности,		φ
Изучаемый предмет
где φ – условие соединения кортежей –		булева функция вида:

(ЛАБОРАТОРИИ СПЕЦИАЛЬНОСТЕЙ.Название лаборатории =ЛАБОРАТОРИЯ.Название).

7. Естественное соединение является бинарной операцией, развивающей Θ-соединение. В естественном соединении условие связывания кортежей соответствует ограничению ссылочной целостности отношений. Одно из отношений, участвующих в операции, должно иметь внешний ключ (FК), ссылающийся на первичный ключ (РК) в другом операнде естественного соединения. Результат естественного соединения вычисляется как Θ-соединение по условию равных значений атрибутов первичного и внешнего ключей соединяемых отношений:

R S = Sel PK = FK (R X S).

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

47

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

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

Лекция 7. Реляционное исчисление над переменными-кортежами

В качестве примера реляционного исчисления (РИ) рассмотрим реляционное исчисление над переменными – кортежами.

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

местным предикатом первого порядка называется выражение, содержащее n

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

Выражения для запроса в РИ использует форму записи элементов множества с определяющей функцией:

{<элемент множества>| <определяющая функция – условие для элемента множества>} .

48

Например, {x | x mod (2) ≡ 0}.

Здесь x mod (2) ≡ 0 – предикат (определяющая функция). Операция x mod (2) вычисляет остаток от деления предметной переменной (целого) x на 2. Поэтому x mod (2) ≡ 0 является одноместным предикатом, принимающим истинное значение при четных x. Таким образом, запись { x | x mod (2) ≡ 0} определяет множество четных чисел.

Общая форма записи запроса в РИ имеет вид: {t | φ(t) },

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

Формула φ(t) строится их следующих элементарных (атомарных) условий:

1.R(t) – предикат, принимающий значение истина, если переменная t является кортежом в отношении R. Тогда запись {t | R(t) } является запросом, возвращающим все кортежи отношения R;

2.u[i] Θ v[j] или u[i] Θ u[j], логическое выражение с переменными u, v, областью возможных значений которых являются кортежи каких-либо

отношений,		i, j – номера или имена атрибутов в отношении, тогда u[i] и v[j]			-
поля i-го и j-го атрибутов кортежей отношений. u[i] и v[j]				выполняют роль
предметных переменных в предикатах определяющей функции. Как и в РА,					Θ
– операция бинарного сравнения элементов кортежей разных отношений
(u[i]	Θ v[j]) или элементов кортежа одного отношения (u[i] Θ u[j]),
Θ { >, <,		<=, >= , =, # };
3.	u[i]	Θ <константное выражение> -	логическое	выражение для
сравнения		значения элемента u[i] (поля) кортежа	в отношении со значением
выражения, построенного на константах и скалярных функциях.
	Из перечисленных элементарных условий по следующим правилам
рекурсивно строятся определяющие функции:

1)каждое элементарное условие является определяющей функцией;

2)если ψ1 и ψ2 - являются определяющими функциями, то выражения вида:

49

ψ1 ψ2 , ψ1 ψ2 и ¬ψ1 – также являются определяющими функциями, в

которых:

- операция конъюнкции (логическое И),

- операция дизъюнкции (логическое ИЛИ),

¬- одноместная операция отрицания (логическое НЕ);

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

При вычислении значений предиката первыми выполняются операции связывания переменных кванторами и , затем операции сравнения (Θ),

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

С помощью приведенных правил могут быть построены запросы, приводящие к практически бесполезным, но при этом весьма объемным результатам. Например, если правильным является выражение {t | R(t)}, то формально правильным в соответствии с правилом 2 является выражение {t | ¬ R(t)}. Данное выражение требует возвратить все кортежи, отсутствующие в отношении R. Ответ на такой запрос можно представить в виде разности отношения, получаемого декартовым произведением доменов, используемых атрибутами отношения R (всеми возможными кортежами) и существующими кортежами отношения R. Поскольку многие домены реальных баз задаются допустимыми типами данных, например, фамилия – строка фиксированной длины, дата рождения – произвольная дата из заданного интервала, то большинство кортежей, полученное декартовым произведением таких доменов,

50

не имеет смысла. Поэтому в запросах {t | φ(t)} РИ рассматривают подмножества определяющих функций φ(t), называемых безопасными. Безопасные определяющие функции не позволяют создавать в результате запроса данные, которые не представлены в используемых отношениях БД или в самой определяющей функции. Безопасные выражения для запросов оказываются всегда вычислимы по БД.

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

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

{t | ЛАБОРАТОРИЯ_РТФ (t) ЛАБОРАТОРИЯ_ФТФ (t)}.

Однако, если лаборатории всех факультетов хранятся в общем отношении: ЛАБОРАТОРИИ_УГТУ (Название, Факультет, Изучаемый предмет,

Используемое оборудование), то данный запрос должен иметь вид:

{x | ЛАБОРАТОРИИ_УГТУ (x) (x [Факультет]=«РТФ» x [Факультет]=«ФТФ»)}.

Здесь x переменная, областью возможных значений которой определены кортежи отношения ЛАБОРАТОРИИ_УГТУ.

Реализованный ранее с помощью операции Θ-соединения запрос, возвращающий названия специальностей и изучаемых в них предметов в РИ, записывается выражением:

{x | ( v)( t) (ЛАБОРАТОРИИ СПЕЦИАЛЬНОСТЕЙ(v) ЛАБОРАТОРИЯ (t)

v[Название лаборатории] = t[Название]

x[1] = v [Название специальности] x[2] = t[Изучаемый предмет])}.

В этом выражении ЛАБОРАТОРИИ СПЕЦИАЛЬНОСТЕЙ (v) ЛАБОРАТОРИЯ (t)

определяет области возможных значений переменных – кортежей v и t.

51