Тема_4 (1122340), страница 6
Текст из файла (страница 6)
Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(15)Переменные, входящие в WFF, могут быть свободными илиПравильнопостроенные формулы (12)связаннымиПо определению, все переменные, входящие в WFF, припостроении которой не использовались кванторы, являютсясвободнымиФактически, это означает, что если для какого-то набора значенийсвободных кортежных переменных при вычислении WFF полученозначение true, то эти значения кортежных переменных могутвходить в результирующее отношениеЕсли же имя переменной использовано сразу после квантора припостроении WFF вида EXISTS var (form) или FORALL var (form), то вэтой WFF и во всех WFF, построенных с ее участием, var являетсясвязанной переменнойЭто означает, что такая переменная не видна за пределамиминимальной WFF, связавшей эту переменнуюПри вычислении значения такой WFF используется не однозначение связанной переменной, а вся область ее определения08.10.201085С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(16)Пусть здесьи далее СЛУ1и СЛУ2(13)представляют собой двеПравильнопостроенныеформулыкортежные переменные, определенные на отношенииСЛУЖАЩИЕТогда WFFEXISTS СЛУ2 (СЛУ1.СЛУ_ЗАРП > СЛУ2.СЛУ_ЗАРП)для текущего кортежа переменной СЛУ1 принимаетзначение true в том и только в том случае, если во всемотношении СЛУЖАЩИЕ найдется такой кортеж(ассоциированный с переменной СЛУ2), чтобы значение егоатрибута СЛУ_ЗАРП удовлетворяло внутреннему условиюсравненияЛегко видеть, что эта формула принимает значение true длятех и только тех значений кортежной переменной СЛУ1,которые соответствуют служащим, не получающимминимальную зарплату08.10.201086С.Д. Кузнецов.
Базы данных.РеляционРеляционное исчисление кортежей(17)Правильнопостроенные формулымножество(14)Вот соответствующее08.10.2010кортежей87С.Д. Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(18)Правильнопостроеннаяформулыформула (15)ПравильнопостроенныеFORALL СЛУ2 (СЛУ1.СЛУ_ЗАРП ≥ СЛУ2.СЛУ_ЗАРП)для текущего кортежа переменной СЛУ1 принимаетзначение true в том и только в том случае, если для всехкортежей отношения СЛУЖАЩИЕ (связанных с переменнойСЛУ2) значения атрибута СЛУ_ЗАРП удовлетворяютусловию сравненияФормула принимает значение true только для тех значенийкортежной переменной СЛУ1, которые соответствуютслужащим, получающим максимальную зарплату.Соответствующее множество кортежей:08.10.201088С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(19)Очевидно, что показанные отношения соответствуют условиям обеихНо как в данном случае можно реализовать систему, которая по заданнойформуле производит правильный результат?Наиболее очевидным способом интерпретации обеих обсуждавшихсявыше формул является следующий:Правильнопостроенные формулы (16)формулв некотором порядке просматривать область определения свободной кортежнойпеременной СЛУ1;для каждого очередного кортежа из области определения СЛУ1 просматриватьобласть определения связанной переменной СЛУ2 до тех пор, пока не будетустановлено истинностное значение формулы для данного кортежа СЛУ1в случае наличия квантора существования процесс просмотра для СЛУ2 можноостановить после нахождения первого кортежа, для которого значением подформулы,находящейся под знаком квантора, станет true;при наличии квантора всеобщности необходимо просмотреть всю область определенияСЛУ2).Мы снова получаем два цикла, как и при интерпретации WFF с двумясвободными переменнымиНо в данном случае во внешнем цикле обязательно просматриваетсяобласть определения свободной переменной.08.10.201089С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(20)На самомпостроенныеделе, правильнееговоритьне о свободных иПравильноформулы(17)связанных переменных, а о свободных и связанныхвхождениях переменныхЕсли переменная var является связанной в WFF form, то вовсех WFF, включающих form, вне form может использоватьсявхождение того же имени переменной var, которое можетбыть свободным или связанным, но в любом случае неимеет никакого отношения к вхождению переменной var вWFF formВот пример:EXISTS СЛУ2 (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМAND СЛУ1.СЛУ_НОМЕР ≠ СЛУ2.СЛУ_НОМЕР)AND FORALL СЛУ2(IF СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМTHEN СЛУ1.СЛУ_ЗАРП = СЛУ2.СЛУ_ЗАРП)08.10.201090С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(21)Эта формула принимает значение true только для тех значенийПравильнопостроенныеформулы(18) служащим,переменнойСЛУ1, которыесоответствуютучаствующим в проектах с более чем одним участником, причемвсе участники проекта получают одну и ту же зарплатуЗдесь мы имеем два связанных вхождения переменной СЛУ2 ссовершенно разным смысломГрубо говоря, для текущего значения переменной СЛУ1переменная СЛУ2 два раза «пробежит» свою область определенияпервый раз при вычислении части формулы с кванторомсуществования,второй при вычислении части с квантором всеобщностиКстати, к тому же результату приведет следующая формула содним квантором всеобщности:FORALL СЛУ2 (IF (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ ANDСЛУ1.СЛУ_НОМЕР ≠ СЛУ2.СЛУ_НОМЕР)THEN СЛУ1.СЛУ_ЗАРП = СЛУ2.СЛУ_ЗАРП)08.10.201091С.Д. Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(22)Легко заметить, что кванторы можно трактовать как булевские функциисвязанной кортежной переменнойС тем же успехом можно ввести в реляционное исчисление числовыефункции над множествами, такие, какПравильнопостроенныеформулы(функции, принимающиезначенияtrue или(19)false) над множеством значенийMIN (минимальное значение),MAX (максимальное значение),AVG (среднее значение) и т.
д.В этом случае можно было бы написать, например, WFFСЛУ1.СЛУ_ЗАРП > MIN СЛУ2.СЛУ_ЗАРП (СЛУ1.ПРО_НОМ =СЛУ2.ПРО_НОМ),в области истинности которой содержатся все кортежи отношенияСЛУЖАЩИЕ, соответствующие тем служащим, которые получаютзаработную плату, превышающую минимальную зарплату служащих,участвующих в том же проектеПонятно, что для получения результирующего отношения можноинтерпретировать формулу таким же образом, как в обсуждавшемся вышеслучае наличия кванторов08.10.201092С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(23)WFF обеспечивают средства формулировки условия выборки изЧтобы можно было использовать исчисление для реальной работыс базами данных, требуется еще один компонент, которыйопределяет набор и имена атрибутов результирующего отношенияЭтот компонент называется целевым списком (target list)Целевой список строится из целевых элементов, каждый изкоторых может представляться одним из следующих способов:Целевыеспискибазыи выраженияотношенийданных реляционного исчисления (1)var.attr, где var – имя свободной переменной соответствующей WFF, аattr – имя атрибута отношения, на котором определена переменная var;var, что эквивалентно наличию подсписка var.attr1, var.attr2, ..., var.attrn,где множество {attr1, attr2, ..., attrn} включает имена всех атрибутовопределяющего отношения;new_name = var.attr; new_name – новое имя соответствующего атрибутарезультирующего отношения08.10.201093С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(24)Последнийтребуетсяв тех исчисленияслучаях, когдаЦелевыесписки варианти выраженияреляционного(2) в WFFиспользуется несколько свободных переменных содинаковой областью определенияФактически применение целевого списка к областиистинности WFF эквивалентно действию алгебраическойоперации проекции, а последний из приведенных вариантовпредставляет собой некоторую разновидностьалгебраической операции переименования атрибута.Выражением реляционного исчисления кортежейназывается конструкция вида target_list WHERE WFFЗначением выражения является отношение, тело которогоопределяется WFF, а множество атрибутов и их имена –целевым списком08.10.201094С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(25)В качестве простого примера покажем выражение реляционногоЦелевыесписки и выражения реляционного исчисления (3)исчисления кортежей, результат которого совпадает с результатомоперации СЛУЖАЩИЕ DIVIDE BY НОМЕРА_ПРОЕКТОВ:СЛУ1, СЛУ2 RANGE IS СЛУЖАЩИЕНОМЕР_ПРОЕКТА RANGE IS НОМЕРА_ПРОЕКТОВСЛУ1.СЛУ_НОМЕР, СЛУ1.СЛУ_ИМЯ, СЛУ1.СЛУ_ЗАРПWHERE FORALL НОМЕР_ПРОЕКТА EXISTS СЛУ2(СЛУ1.СЛУ_НОМЕР = СЛУ2.СЛУ_НОМЕР ANDСЛУ1.ПРО_НОМ = НОМЕР_ПРОЕКТА.ПРО_НОМ)Результатом этого выражения является отношение, совпадающее срезультатом операции СЛУЖАЩИЕ DIVIDE BY НОМЕРА_ПРОЕКТОВ08.10.201095С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление доменов (1)В исчислении доменов областью определенияпеременных являются не отношения, а доменыВ каждый момент времени переменнаяисчисления домена принимает некотороезначение из множества значений этого доменаПрименительно к базе данных СЛУЖАЩИЕПРОЕКТЫ можно говорить, например, одоменных переменныхИМЯ (значения – допустимые имена) илиНОСЛУ (значения – допустимые номера служащих)08.10.201096С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление доменов (2)Условия членства (1)Основным формальным отличием исчисления доменов отисчисления кортежей является наличие дополнительногомножества предикатов, позволяющих выражать такназываемые условия членстваЕсли R – это n-арное отношение с заголовком{<X1, T1>, <X2, T2>,…, <Xn, Tn>},то условие членства имеет видR (Xi1 : vi1, Xi2 : vi2, ..., Xim : vim)(m ≤ n, {Xij} ⊂ {Xk}),где vij – этолибо литерально задаваемая константа домена (или типа) Tij,либо имя некоторой доменной переменной, определенной надомене (или типе) Tij.08.10.201097С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление доменов (3)Условия членства (2)Условие членства принимает значение true в том и только втом случае, если в отношении R существует кортеж,содержащий указанные значения указанных атрибутовЕсли vij – константа, то на атрибут Xij накладывается жесткое условие, независящее от текущих значений доменных переменных;если же vij – имя доменной переменной, то условие членства может принимать разные значения приразных значениях этой переменнойДля большей ясности приведем пару примеровДля простоты будем считать, что определены доменныепеременные, имена которых совпадают с именами атрибутовотношения СЛУЖАЩИЕ, а в случае, когда требуетсянесколько доменных переменных, определенных на одномдомене, мы будем добавлять в конце имени цифры08.10.201098С.Д.
Кузнецов. Базы данных.РеляционРеляционное исчисление доменов (4)Условия членства (3)WFF исчисления доменовСЛУЖАЩИЕ (СЛУ_НОМ:2934,СЛУ_ИМЯ:’Иванов’,СЛУ_ЗАРП:22400.00, ПРО_НОМ:1)примет значение true в том и только в томслучае, когда в теле отношения СЛУЖАЩИЕсодержится кортеж {<СЛУ_НОМ, 2934>,<СЛУ_ИМЯ, ‘Иванов’>, <СЛУ_ЗАРП, 22400.00>,<ПРО_НОМ, 1>} (имена доменов опущены)Соответствующие значения доменныхпеременных образуют область истинности этойWFF08.10.201099С.Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
