Модуль 1. Математические основы баз данных и знаний 1. - презентация

1 Модуль 1. Математические основы баз данных и знаний 1

2 Лекция 6 Базисные средства манипулирования реляционными данными: реляционное исчисление 1. Исчисление кортежей 2. Исчисление доменов 2

3 1. Исчисление кортежей Имеются: Отношение СЛУЖАЩИЕ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ} Отношение ПРОЕКТЫ {ПРО_НОМ, ПРОЕКТ_РУК, ПРО_ЗАРП} 3

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

5 Запрос через средства реляционной алгебры: (СЛУЖАЩИЕ JOIN ПРОЕКТЫ WHERE (СЛУ_ИМЯ = ПРОЕКТ_РУК AND ПРО_ЗАРП > )) PROJECT (СЛУ_ИМЯ, СЛУ_НОМ) 5 1. Исчисление кортежей

6 Расшифровка запроса: выполнить эквисоединение отношений СЛУЖАЩИЕ и ПРОЕКТЫ по условию СЛУ_ИМЯ = ПРОЕКТ_РУК; ограничить полученное отношение по условию ПРО_ЗАРП > ; спроецировать результат предыдущей операции на атрибут СЛУ_ИМЯ, СЛУ_НОМ Исчисление кортежей

7 Запрос через средства реляционного исчисления: определения переменных: RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ RANGE ПРОЕКТ IS ПРОЕКТЫ выражение СЛУЖАЩИЙ.СЛУ_ИМЯ, СЛУЖАЩИЙ.СЛУ_НОМ WHERE EXISTS (СЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУК AND ПРОЕКТ.ПРО_ЗАРП > ) 7 1. Исчисление кортежей

8 Расшифровка запроса: выдать значения СЛУ_ИМЯ и СЛУ_НОМ для каждого кортежа служащих такого, что существует кортеж проектов со значением ПРОЕКТ_РУК, совпадающим со значением СЛУ_НОМ этого кортежа служащих, и значением ПРО_ЗАРП, большим Исчисление кортежей

9 кортежная переменная оператор RANGE - определение кортежной переменной RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ Ссылка на значение атрибута переменной СЛУЖАЩИЙ.СЛУ_ИМЯ 9 1. Исчисление кортежей

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

11 11 1. Исчисление кортежей

12 12 1. Исчисление кортежей IF СЛУЖАЩИЙ.СЛУ_ИМЯ = 'Иванов THEN (СЛУЖАЩИЙ.СЛУ_ЗАРП >= AND СЛУЖАЩИЙ.ПРО_НОМ = 1) Через IF … THEN обозначается логическая функция – импликация По определению, IF a THEN b эквивалентно NOT a OR b

13 13 1. Исчисление кортежей формула будет принимать значение true для следующих значений кортежной переменной СЛУЖАЩИЙ СЛУ_НОМЕРСЛУ_ИМЯСЛУ_ЗАРППРО_НОМ 2934Иванов Петров Сидоров Федоров Иванова Петров Сидоренко Федоренко Иваненко

14 результат эквивалентен алгебраической операции СЛУЖАЩИЕ WHERE (NOT (СЛУЖАЩИЙ.СЛУ_ИМЯ = 'Иванов') OR (СЛУЖАЩИЙ.СЛУ_ЗАРП >= AND СЛУЖАЩИЙ.ПРО_НОМ = 1) Исчисление кортежей

15 15 1. Исчисление кортежей кортежная переменная ПРОЕКТ : RANGE ПРОЕКТ IS ПРОЕКТЫ правильно построенная формула: СЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУК СЛУЖАЩИЕПРОЕКТЫ СЛУ_НОМ ЕР СЛУ_ИМЯ СЛУ_ЗАР П ПРО_НОМ ПРОЕКТ_ РУК 2934Иванов Иванов 2941Иваненко Иваненко 2934Иванов Иванов

16 16 Если form – это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) FORALL var (form) представляют собой WFF 1.Исчисление кортежей Кванторы, свободные и связанные переменные

17 17 формула EXISTS var (form) принимает значение true в том и только в том случае, если в области определения переменной var найдется хотя бы одно значение (кортеж), для которого WFF form принимает значение true 1. Исчисление кортежей

18 18 Формула FORALL var (form) принимает значение true, если для всех значений переменной var из ее области определения WFF form принимает значение true 1. Исчисление кортежей

19 19 все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными если имя переменной использовано сразу после квантора при построении WFF вида EXISTS var (form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием, var является связанной переменной. 1. Исчисление кортежей

20 20 Пусть СЛУ1 и СЛУ2 - кортежные переменные, определенные на отношении СЛУЖАЩИЕ. Тогда WFF EXISTS СЛУ2 (СЛУ1.СЛУ_ЗАРП > СЛУ2.СЛУ_ЗАРП) для текущего кортежа переменной СЛУ1 принимает значение true в том и только в том случае, если во всем отношении СЛУЖАЩИЕ найдется такой кортеж (ассоциированный с переменной СЛУ2), чтобы значение его атрибута СЛУ_ЗАРП удовлетворяло внутреннему условию сравнения 1. Исчисление кортежей

21 21 1. Исчисление кортежей

22 22 1. Исчисление кортежей

23 23 1.Исчисление кортежей Целевые списки (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 – новое имя соответствующего атрибута результирующего отношения

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

25 25 Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного множества предикатов, позволяющих выражать так называемые условия членства 2. Исчисление доменов

26 26 Если 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 – это либо литерально задаваемая константа, либо имя доменной переменной. 2. Исчисление доменов

27 Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов Исчисление доменов

28 Если v ij – константа, то на атрибут a ij накладывается жесткое условие, не зависящее от текущих значений доменных переменных; если же v ij – имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной Исчисление доменов

29 29 2. Исчисление доменов WFF исчисления доменов СЛУЖАЩИЕ (СЛУ_НОМ:2934, СЛУ_ИМЯ:'Иванов', СЛУ_ЗАРП: , ПРО_НОМ:1) примет значение true в том и только в том случае, когда в теле отношения СЛУЖАЩИЕ содержится кортеж

30 30 2. Исчисление доменов WFF исчисления доменов СЛУЖАЩИЕ (СЛУ_НОМ:2934, СЛУ_ИМЯ:'Иванов', СЛУ_ЗАРП: , ПРО_НОМ:ПРО_НОМ) примет значение true для всех комбинаций явно заданных значений и допустимых значений переменной ПРО_НОМ Область значений

31 31 запрос "Выдать номера и имена служащих, не получающих минимальную заработную плату": СЛУ_НОМ, СЛУ_ИМЯ WHERE EXISTS СЛУ_ЗАРП1(СЛУЖАЩИЕ (СЛУ_ЗАРП1) AND СЛУЖАЩИЕ (СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП) AND СЛУ_ЗАРП > СЛУ_ЗАРП1) 2. Исчисление доменов СЛУ_ЗАРП1) 2. Исчисление доменов">