Базы данных Лекция 6 Базисные средства манипулирования реляционными данными: реляционное исчисление

Базы данных Введение Лекция 6 Реляционное исчисление является прикладной ветвью формального механизма исчисления предикатов первого порядка. В основе исчисления лежит понятие переменной с определенной для неё областью допустимых значений и понятие правильно построенной формулы, опирающейся на переменные, предикаты и кванторы. В зависимости от области определения переменной, различают: исчисление кортежей; исчисление доменов.

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

Базы данных Исчисление кортежей Лекция 6 Для определения кортежной переменной используется оператор RANGE. Например, для того чтобы определить переменную СЛУЖАЩИЙ, областью определения которой является отношение СЛУЖАЩИЕ, нужно употребить конструкцию: RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной. Например, для того, чтобы сослаться на значение атрибута СЛУ_ИМЯ переменной СЛУЖАЩИЙ, нужно употребить конструкцию: СЛУЖАЩИЙ.СЛУ_ИМЯ.

Базы данных Исчисление кортежей: правильно построенные формулы Лекция 6 Правильно построенная формула (Well-Formed Formula, WFF) служит для выражения условий, накладываемых на кортежные переменные. Простые условия Основой WFF являются простые условия, представляющие собой операции сравнения скалярных значений (значений атрибутов переменных или литерально заданных констант). Более сложные варианты WFF строятся с помощью логических связок NOT, AND, OR и IF … THEN с учётом обычных приоритетов операций ( NOT > AND > OR ) и возможности расстановки скобок.

Базы данных Исчисление кортежей: правильно построенные формулы Лекция 6 Для примера возьмём отношения СЛУЖАЩИЕ, ПРОЕКТЫ и НОМЕРА_ПРОЕКТОВ :

Базы данных Исчисление кортежей: правильно построенные формулы Лекция 6 Правильно построенной является следующая формула: IF СЛУЖАЩИЙ.СЛУ_ИМЯ = 'Иванов THEN (СЛУЖАЩИЙ.СЛУ_ЗАРП >= AND СЛУЖАЩИЙ.ПРО_НОМ = 1) Эта формула будет принимать значение true для следующих значений кортежной переменной СЛУЖАЩИЙ : СЛУ_НОМЕРСЛУ_ИМЯСЛУ_ЗАРППРО_НОМ 2934Иванов Петров Сидоров Федоров Иванова Петров Сидоренко Федоренко Иваненко

Базы данных Исчисление кортежей: правильно построенные формулы Лекция 6 Пусть имеется следующее определение кортежной переменной ПРОЕКТ : RANGE ПРОЕКТ IS ПРОЕКТЫ Вот еще пример правильно построенной формулы: СЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУК Эта формула будет принимать значение true для следующих пар значений кортежных переменных СЛУЖАЩИЙ и ПРОЕКТ : СЛУЖАЩИЕПРОЕКТЫ СЛУ_НОМЕРСЛУ_ИМЯСЛУ_ЗАРППРО_НОМ ПРОЕКТ_ РУК 2934Иванов Иванов 2941Иваненко Иваненко 2934Иванов Иванов

Базы данных Исчисление кортежей: кванторы, свободные и связанные переменные Лекция 6 При построении WFF допускается использование кванторов существования ( EXISTS ) и всеобщности ( FORALL ). Если form это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) и FORALL var (form) представляют собой WFF. По определению, формула EXISTS var (form) принимает значение true в том и только в том случае, если в области определения переменной var найдется хотя бы одно значение (кортеж), для которого WFF form принимает значение true. Формула FORALL var (form) принимает значение true, если для всех значений переменной var из её области определения WFF form принимает значение true.

Базы данных Исчисление кортежей: кванторы, свободные и связанные переменные Лекция 6 Переменные, входящие в WFF, могут быть свободными или связанными. По определению, все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении WFF вида EXISTS var (form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с её участием, var является связанной переменной. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся область её определения.

Базы данных Исчисление кортежей: кванторы, свободные и связанные переменные Лекция 6 Например, результатами EXISTS СЛУ2 (СЛУ1.СЛУ_ЗАРП > СЛУ2.СЛУ_ЗАРП) и FORALL СЛУ2 (СЛУ1.СЛУ_ЗАРП СЛУ2.СЛУ_ЗАРП) будут:

Базы данных Исчисление кортежей: целевые списки и выражения реляционного исчисления Лекция 6 WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена атрибутов результирующего отношения. Этот компонент называется целевым списком (target list). Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид: var.attr, где var имя свободной переменной соответствующей WFF, а attr имя атрибута отношения, на котором определена переменная var ; var, что эквивалентно наличию подсписка var.attr 1, var.attr 2, …, var.attr n, где {attr 1, attr 2, …, attr n } включает имена всех атрибутов определяющего отношения; new_name = var.attr ; new_name новое имя соответствующего атрибута результирующего отношения.

Базы данных Исчисление кортежей: целевые списки и выражения реляционного исчисления Лекция 6 Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE WFF. Значением выражения является отношение, тело которого определяется WFF, а множество атрибутов и их имена целевым списком.

Базы данных Исчисление кортежей: целевые списки и выражения реляционного исчисления Лекция 6 Например, выражение реляционного исчисления кортежей, результат которого совпадает с результатом операции СЛУЖАЩИЕ DIVIDE BY НОМЕРА_ПРОЕКТОВ: СЛУ1, СЛУ2 RANGE IS СЛУЖАЩИЕ НОМЕР_ПРОЕКТА RANGE IS НОМЕРА_ПРОЕКТОВ СЛУ1.СЛУ_НОМЕР, СЛУ1.СЛУ_ИМЯ, СЛУ1.СЛУ_ЗАРП WHERE FORALL НОМЕР_ПРОЕКТА EXISTS СЛУ2 (СЛУ1.СЛУ_НОМЕР = СЛУ2.СЛУ_НОМЕР AND СЛУ1.ПРО_НОМ = НОМЕРА_ПРОЕКТОВ.ПРО_НОМ) СЛУ_НОМЕРСЛУ_ИМЯСЛУ_ЗАРП 2934Иванов Петров

Базы данных Исчисление доменов Лекция 6 В исчислении доменов областью определения переменных являются не отношения, а домены. Применительно к базе данных СЛУЖАЩИЕ-ПРОЕКТЫ можно говорить, например, о доменных переменных ИМЯ (значения допустимые имена) или НОСЛУ (значения допустимые номера служащих).

Базы данных Исчисление доменов: условия членства Лекция 6 Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного множества предикатов, позволяющих выражать так называемые условия членства. Если R это n-арное отношение с атрибутами a 1, a 2, …, a n, то условие членства имеет вид R (a i1 : v i1, a i2 : v i2, …, a im : v im ) (m n), где v ij это либо литерально задаваемая константа, либо имя доменной переменной. Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов. Если v ij константа, то на атрибут a ij накладывается жесткое условие, не зависящее от текущих значений доменных переменных; если же v ij имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной.

Базы данных Исчисление доменов: выражения исчисления доменов Лекция 6 Во всех остальных отношениях формулы и выражения исчисления доменов выглядят похожими на формулы и выражения исчисления кортежей. В частности, формулы могут включать кванторы, и различаются свободные и связанные вхождения доменных переменных. Реляционное исчисление доменов является основой большинства языков запросов, основанных на использовании форм.