Реляционное исчисление кортежей и доменов.

Предположим, что мы работаем с базой данных, обладающей схемой Студенты (Номер зачётной книжки, Фамилия И. О., Номер группы, Адрес) и Группы (Номер группы, Число студентов, Староста) и хотим узнать фа милии, номера зачётных книжек и место жительства старост групп, число студентов которых превышает 20 человек.

При использовании реляционной алгебры пришлось бы выполнить следующие вычисления:

- выполнить соединение отношений Студенты и Группы по атрибутам Номер группы, Фамилия И.О. (требуется Переименование атрибута "Старос­та" в атрибут "Фамилия И.О. ");

- ограничить полученное отношение по условию Число студентое>20]

- спроецировать результат предыдущей операции на атрибуты: Номер зачётной книжки, Фамилия И. О., Адрес;

- в полученном отношении переименовать атрибут Фамилия И.О. в ат­рибут Староста.

Мы чётко сформулировали последовательность операций реляционной алгебры. Другими словами, алгебраическая формулировка запроса является процедурной, т.е. задающей правила выполнения запроса.

Если же составить этот запрос с использованием реляционного исчис­ления, то полученную формулу можно прочитать так: "Выдать Номер зачёт­ной книжки, Фамилию И.О., Адрес студентов, являющихся старостами групп, имеющих более 20 студентов". В этой формулировке содержится только ха­рактеристика результирующего отношения и не указывается путь её получе­ния. Таким образом, логическая формулировка запроса является описатель­ной (декларативной), поскольку она описывает лишь свойства желаемого ре­зультата. Как указывалось выше, на самом деле алгебраическая и логическая формы запроса взаимозаменяемы и существуют несложные правила преобра­зования одного формализма в другой.

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

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

Для определения кортежной переменной используется оператор RANGE. Например, для определения переменной "Студент", областью опре­деления которой является отношение "Студенты", необходимо использовать запись:

RANGE Студент IS Студенты.

Как указывалось выше, переменная "Студент" представляет некото­рый кортеж отношения "Студенты". При использовании кортежных переменных можно ссылаться на значения атрибута переменной (например, менных можно ссылаться на значения атрибута переменной (например, на атрибут "Фамилия И.О.), используя следующую конструкцию: Студент. Фамилия_К_0.

Правильно построенные формулы ППФ (Well Formed Formula - WFF) служат для выражения условий, накладываемых на кортежные переменные. Основой правильно построенных формул являются простые сравнения (com­parison), представляющие собой сравнение скалярных значений (значений атрибутов переменных или литерально заданных констант). Например, вы­полнение условия "в группе количество студентов превышает 20 человек" может быть записано следующим образом:

Группа. Число^студентов > 20.

Эта запись является простым сравнением и потому может считаться ППФ. Более сложные формулы могут быть построены путём использования скобок (заключённая в скобки ППФ является простым сравнением).

Более сложные варианты ППФ строятся с помощью логических связок NOT, AND, OR и IF...THEN.

Например, запись: Студент. Фамилия И. 0.= Группа. Староста AND (Группа. Число студентов > 20) позволяет выбрать из отношения фамилии старост групп, число студентов в которых превышает 20 человек.

При построении ППФ могут использоваться кванторы существования EXISTS и всеобщности VORALL. Конструкции EXISTS var (form) и VORALL var (form) являются правильно постоенными формулами.

Таким образом, ППФ обеспечивает средства формулировки условий выборки из отношений баз данных. Для определения набора и имён столбцов результирующего отношения используется компонент, получивший название " целевой список " (target Jist).

Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:

- var.attr, где var - имя свободной переменной соответствующей ППФ, attr - имя атрибута отношения, на котором определена переменная var;

- var соответствует наличию подсписка var.attr 1, var.attr2,...var.attrn, где var.attrl, var.attr2,...var.attrn включает имена всех атрибутов отношения;

- newname = var.attr; new_name - новое имя атрибута результирующе­го отношения. Последний целевой элемент используется в тех случаях, когда в ППФ необходимо иметь несколько свободных переменных с одинаковой областью определения.

Выражением реляционного исчисления кортежей называется конст­рукция вида целевой список WHERE ППФ. Значением выражения является отношение, тело которого определяется ППФ, а набор атрибутов и их имена -Целевым списком.

Вопрос 38

Пример использования реляционного исчисления для обработки данных.

В рассмотренным выше примере выражение реляционного исчисления будет иметь следующий вид:

RANGE Студент IS Студенты. RANGE Группа IS Группы.

Номер зачётной книжки, Староста, Адрес = Студент. Номер зачёт­ной книжки, Студент. Фамилия И. О., Студент. Адрес WHERE EXISTS Студент. (Студент. Фамилия И. О. = Группа.. Староста AND (Группа. Чис­ло студентов > 20)).

В исчислении доменов областью определения переменных являются не отношения, а домены. Применительно к базе данных Студенты - Группы можно говорить, например, о доменных переменных Фамилия И. О. (значе­ние - допустимые фамилии) или Номер зачётной книжки (значение -допустимые номера).

Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяю­щих выражать так называемое условия членства. Если R есть n-арное отно­шение с атрибутами a_ha₂,...a„, то условие членства имеет вид:

где v,y - это либо задаваемая константа, либо имя кортежной перемен­ной. Условие членства принимает значение true в том случае, если в отноше­нии R существует кортеж, содержащий заданные значения указанных атри­бутов. Если Vy - константа, то на атрибут а$ задаётся условие, не зависящее от текущих значений доменных переменных. Если же Vy - имя доменной пе­ременной, то условия членства могут принимать разные значения при разных значениях этой переменной;

т - кардинальное число отношения.

Во всех остальных отношениях формулы и выражения исчисления до­менов строятся аналогично формулам и выражениям исчисления отношений.

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

Отношение Абитуриенты имеет атрибуты Номер, Фамилия И. О., Балл. При этом последний атрибут может принимать значения Балл1=6, Балл2=7, БаллЗ=8, Балл4=9иБалл5=10.

RANGE Абитуриент IS Абитуриенты. Номер, Фамилия И.О. = Абитуриент. Номер, Абитуриент. Фамилия И. О. WHERE EXISTS Абитуриент. (Абитуриент (Номер, Фамилия И. О., Балл) AND {Абитуриент. Балл > Абитуриент. БаллЗ)).

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

 

 

Вопрос 39