Реляционная модель данных.

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

Из теории множеств известно, что формальным анало­гом таблицы выступает отношение. Пусть дана совокупность

множеств D₁, D₂, ..., D_n. Отношением R называется некоторое подмножество декартова произведения этих множеств:

R D₁×D₂× ... ×D_n.

Декартово произведение D₁×D₂× ... ×D_n — множество всех возможных кортежей (d₁, d₂, ..., d_n ) таких, что d_i D_i, i = 1, 2, ..., п. Множества D называют доменами, а п — степенью отношения R.

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

■ Примечание. В общем случае допустимо, чтобы различные
домены имели общие элементы, а атрибуты представляли под­
множества одного и того же домена.

С другой стороны, атрибут А_i можно рассматривать как проекцию отношения R на i-ю координату. Напри­мер, D₁= {a₁, а₂, а₃, а₄},

D₂ = {b₁, b₂, b₃}. Тогда

D₁×D₂ ={<a₁, b₁ >, < a₁, b₂ > , < а₁, b₃>, < а₂, b₁>, <а₂,b₂ >,<a₂, b₃ >, < а₃, b₁ >, < а₃, b₂ >, < а₃, b₃ >, <a₄, b₁>,< а₄, b₂ >, < a₄, b₃ >}.

Построим отношение Q = {<a₁, b₃>, <a₂, b₁>, <a₂, b₃>, <a₃, b₁ >, <a₃, b₂>}. Очевидно, что Q D₁, × D₂. Атрибутами являются множества А_{1 =} { а₁, а₂, а₃}, A₂ = {b₁ b₃}. При этом A₁ D₂, A₂ D₂.

В форме таблицы отношение Q выглядит как табл. 2.1.
Таблица 2 1

Степень отношения Q равна 2.

Запись вида Q(A₁, A₂) на­зывается схемой отношения Q и содержит наряду с названи­ем отношения имена атрибутов. Совокупность схем отноше­ний составят схему реляцион­ной БД.

■ Примечание. Распространен случай, когда БД, имеющая
многие десятки тысяч кортежей, содержит сравнительно неболь­шое число схем отношений.

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

Это означает, что отношения не могут быть элементами отношений.

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

Реляционное исчисление.Оно базируется на теорети­ческих основах исчисления предикатов. Использование реляционного исчисления дает возможность манипулировать с данными на уровне выходного документа, что поз­воляет строить удобные для пользователя ЯМД непро­цедурного типа. Пользователь имеет возможность произ­водить описание необходимого ему отношения независи­мо от процедур поиска и порядка действий над данными.

■ Примечание. Напомним, что предикатом P(x₁, х₂, ..., х _n)называется функция, принимающая значения «истина» или «ложь», от аргументов, определенных в конкретных областях D₁, D₂, ..., D_n. При построении высказываний используются логи­ческие связки /\, V, ┐, →, ←→, называемые соответственно конъюнкцией, дизъюнкцией, отрицанием, импликацией и эквива­лентностью. Кроме того, применяются термы сравнения, имею­щие вид x_i*x_j, где * — символ операции сравнения, в качест­ве которого могут применяться символы =, ≠,>,<, ≥, ≤. Кванторы существования g и всеобщности V позволяют отне­сти высказывание ко всему рассматриваемому множеству. Так, выражение x X (f (x) >а) означает, что среди элементов мно­жества X найдется по крайней мере один, при котором оказы­вается истинным неравенство, заключенное в скобках. Если ис­пользовать квантор всеобщности , x X (f (i) > a), то получим высказывание: для всех элементов множества X некоторая функция f(x) больше заданного значения а. Неравенство (f(x)>a) представляет собой предикат: «функция от х больше константы а». Предикат принимает значение «истина» (1) или «ложь» (0). Областью определения аргумента х предиката яв­ляется множество X. Если указанный предикат обозначить Р(х) и опустить явное указание области определения X, то получим более принятую в исчислении предикатов запись: а хР(х) и VxP(x).

Таким образом, по определению кванторов существования и все­общности имеем следующие соотношения:

где {b₁ , b₂ ...,b_n} = Х.

В реляционном исчислении принято связывать с отно­шением R(A₁, ..., А_n) некоторый предикат Р(х₁ ..., х_п), аргументы которых имеют одинаковые области определе­ния, таким образом, что если Р(а₁ а₂, ..., а_п) = 1то кор­теж < а₁ а₂, ..., а_п > принадлежит отношению R a_i A_i,

i = 1, п. В противном случае кортеж не входит в состав указанного отношения. Отсюда следует, что посредством задания некоторого предиката может быть задано и со­ответствующее ему отношение.

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

Пример построения отношения.Задано отношение R₁(A₁, ..., А₂) = = {<5,1>, <10,4>, <7,2>, <9,8>}. Поставим отношению R₁ в соответствие предикат P₁:

R₁(A₁, А₂) ←→ P₁ (x₁, x₂),

где переменные x₁ и х₂ имеют области определения A₁ и А₂. Тогда предикат Р₂(x₁) ←→ х₂ P₁ (x₁, x₂) /\ (x₂ > 2) формирует но­вое отношение R₂(A₃), в которое войдут лишь те значения x₁ для которых соответствующие значения х₂ в отношении R, ока­зались больше 2: R₂(A₁) = {<10>, <9>}. Ясно, что предикат Р₂ однозначно определяет отношение R₂.

В [19] приводится описание псевдоязыка реляционно­го исчисления. Кратко рассмотрим его использование для операций поиска.

Оператор построения нового отношения

СОЗДАТЬ R (...): L,

где R (...),

означает наименование искомого отношения (в скобках указываются имена атрибутов; символ «:» имеет смысл выражения «такое, что»; L — некоторое высказывание от­носительно используемых отношений, значений атрибутов, их взаимозависимости). Имена атрибутов обычно зада­ются совместно с именем отношения, разделителем вы­ступает точка. Например, аргумент А₂ из отношения R₁ будем обозначать R₁ ∙ A₂.

Оператор принадлежности

ПУСТЬ В ОТНОШЕНИИ Р КОРТЕЖ X

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

Примеры запросов.Пусть БД задана в виде совокупности трех
отношений, представленных в табл. 2.2 ... 2.4.
1. Получить коды всех микросхем

СОЗДАТЬ W (ОМС.КМ)

Таблица 2.2

Таблица 2.3

Таблица 2.4

Результат

Тот же результат может быть получен и с помощью оператора

СОЗДАТЬ W (ОСУ.КМ) Все повторяющиеся значения кодов микросхем встречаются в отношении VV лишь однажды.

2. Получить коды микросхем, для которых мощность потребле­ния не превосходит 130 мВт.

СОЗДАТЬ W (ОМС.КМ): ОМС.ПМ<130

Результат

3. Получить коды узлов, в составе которых присутствуют микро­схемы 155ЛАЗ в количестве не менее 5 шт.

СОЗДАТЬ W (ОСУ.КУ): ОСУ.КМ='155ЛАЗ'ЛОСУ.К>5

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

4. Получить логические функции микросхем, используемых в узле СМ5.

ПУСТЬ В ОТНОШЕНИИ ОСУ КОРТЕЖ X

СОЗДАТЬ W (ОМС.ЛФМ): Х(Х.КУ=='СМ5'ЛХ.КМ =

= ОМС.КМ)