Лекции по Основам ВТ (стр. 12 из 15)

Атомами формул м/б: 1) R(x1...xk) , где R к-арная отношение xi, i=1...k –константа или переменная на некотором домене. Запись означает: атом R с отношением указывает значение тех xi, которые являются переменными и которые д/б выбраны т/о , чтобы x1...xk было кортежем отношения R.

2) x q y , в этой записи x и y константы или переменные на некотором домене . q– арифметический оператор сравнения . смысл атома x y заключается в том, что x и y представляют собой значения при которых атом истин .

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

Общая запись выражения с переменными на домене:{x1...xk| y (x1...xn)} y–формула , которая обладает свойством , что только ее свободные переменные на доменах являются различными переменными.

Пример: {x1x2|R1(x1x2)Ù("y)(ù R2(x1y)Ùù R2(x2y)} Означает множество таких кортежей в R1, что ни один из их компонентов , не является первым компонентом какого-либо отношения R2.

Реляционные исчисления с перменными кортежами.

Вид выражения: { t/.y. (t)} t относится к .y. (t) ; t—единственная свободная переменная –кортеж . Обозначить кортеж фиксированной длины , если необходимо указать арность кортежа , то ti—i –арность. Пси- это некоторая формула, построенная по специальным правилам.

Для обозначения переменных кортежей чаще пользуются прописными буквами.

Пример:{t(R1(t) U R2(t))} интересуют все кортежи t принадлежащие R1(t) или R2(t). запись справедлива когда R1(t) и R2(t) имеют одинаковую арность . Эта операция эквивалентна операции U в реляционной алгебре.

Формулы в реляционном исчислении строятся из атомов и совокупности операторов (арифметических и логических)

Атомы формул бывают 3-х типов: 1) R(t) , R – имя отношения. Атом означает, что t есть кортеж в отношении R. 2) S[i] q u[j] , где s и u являются переменными кортежами , q-арифметический оператор (><=) , i и j – номера или имена интересующих нас компонент ( столбцов в соответствующих кортежах) ; s[i] – обозначение i –го компонента в кортеже переменной s ; u[j] –обозначение j-го компонента в кортеже переменной u. Пример: s[3]>= u[5] 3-й компонент переменной s >= 5-го компонента переменной u. 3) s[i] q a равносильно a q s[i] ,где a-конст. пример: s[3]=70 3-й компонент кортежа s равен 70.

При записи формул используются понятия свободных и связанных переменных кортежей , это связано с применением в этих формулах кванторов.(" и $) Кванторы играют ту же роль , что и декларации в языках программирования.

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

Определение формул , а так же свободныхи связанных вхождений переменных кортежей.

1) каждый атом—есть формула , все вхождения переменных кортежей упомянутых в атоме являются свободными. 2) если y1 и y2—формулы , то справедливо: 1. y1 1Ç y2 являются истинными, 2. y1U y2 обе истинны и также являются формулами. В виде дополнения в литературе добавляют ù y1—тоже является формулой. Экземпляры переменных кортежей являются свободными или связанными. 3) если y - формула, то существует такая S(y), которая тоже является формулой ,т.е. y- "S(y) 4) если y-формула, то существует S(y) тоже формула. 5)Формула в случае необходимости может заключаться в ( ), порядок старшинства: 1-арифметические операторы сравнения; 2-кванторы всеобщности и существования; 3-логические операторы: не, и ,или (ù,Ù,Ú)

Теорема1: устанавливающая эквивалентность безопасных выражений в исчислении выражением в реляционной алгебре.

Формулировка: «если Е – выражение реляционной алгебры , то существует эквивалентное ему базисное выражение в реляционном исчислении с переменными кортежами» Для основных операций реляционной алгебры можно указать следующие соответствующие выражения реляционного исчисления на переменных кортежах. 1) R1UR2-{t/R1(t)UR2(t)} 2) (R1-R2)-{t/R1(t) Ù,ù R2(t)} читается: множество кортежей t, что t принадлежит R1 и не принадлежит R2 .

Выражение исчисления с переменными на доменах эквивалентны заданному выражению исчисления с переменными на кортежах.

{t/ y(t)}

1)если t является кортежем арности к , то вводится к новых переменных на доменах t1,t1...tk ; 2) атомы R(t) заменяются атомами R(t1,t2,...,tk) : R(t)-R(t1...tk); 3) каждое свободное вхождение t[i] заменяется на ti; 4) для каждого квантора существования или всеобщности вводится m переменных на доменах , где m –арность u . [$u],("u)-m-u1...um. в области действия этой квантификации действуют замены R(u)-R(U1...Um) ; U(i) - Ui ; ($ U)- ($U1)...($Um) ; ( "u)- ("U1)...("Um) ;5)выполняется построение выражения {t1...tk/ y (t1...tk} , y -это y в котором осуществлена замена переменных.

Теорема2: для каждого безопасного вырожения реляционного ичисления с переменными кортежами существует эквивалентное безопасное выражение реляционного исчисления на доменах

Теорема3: для каждого безопасного выражения реляционного исчисления с перменными на доменах существует эквивалентное ему выражение реляционной алгебры.

Дополнительные возможности языка манипулирования данными в реляционных системах.

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

Арифметические выражения: 1) арифметические вычисления и сравнения могут непосредственно включаться в формулы селекции реляционной алгебры выражений или в атомы в выражениях реляционного исчисления 2) команды присваивантя и печати 3) агрегатные функции –это функции применяемые к столбцам отношений , в результате выполнения которых вычисляется одна единственная величина .

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

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

Ограничение модели.

1) Отношения в БД обладают всеми свойствами множеств . Основным (жестким) ограничением является невозможность представления в отношении кортежей дубликатов. Оно означает, что каждое отношение имеет по крайней мере хотя бы один первичный ключ ( в крайнем случае он состоит из всех атрибутов)

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

2) При традиционной форме представления отношения порядок столбцов фиксирован, однако , если столбцы поименованы и при выполнении операций над данными пердставленными в отношении , обращаться к столбцам по их именам , то это ограничение снимается .

Назначение атрибутов в модели – можно задавать разнообразные ограничения в явном виде : можно специфицировать область значений атрибутов , задавая тип значений . Для задания более общих ограничений можно использовать предикаты .

ЯОД в реляционных СУБД обычно имеет развитые средства для описания явных ограничений целостности , т.е. он не затрагивает стандартов.

На практике ограничение целостности: ограничение на зависимости м/у атрибутами. Для явного задания ограничений целостности м/б использованы функциональные и ??? зависимости м/у атрибутами.

Функциональные зависимости : x,y - R атрибут y отношения r функционально зависит от атрибута x отношения R .

Если в каждый момент времени каждому значению атрибута x соостветствует тоже значение атрибута y . x-y читается: x зависит от y -- теорема о функциональной зависимости.

Свойствa из теоремы: аксиома 1)—свойство рефлексивности : если x Î u , yÎu , yÎx , то существует функциональная зависимость из x-y. Аксиома 2)—свойство пополнения : если x Î u , y Î u, z Î u , задана зависимость из x-y , которая принадлежит полному множеству функциональных зависимостей данного отношения , то справедлива формула : x Îz - yÎ z . Аксиома 3) --свойство транзитивности : если xÎu , yÎu , z Îu и задана зависимость x-y , y-z , то существует зависимость x-z . Аксиома 4)—свойство расширения : x Î u , y Î u : x-y ; z Î u : x и z -y

Многозначные зависимости.

Теорема для многозначной зависимости : многзначная зависимость существует , если при заданных значениях атрибутов , существует множество состоящее из нулей ( или более взаимных значений атрибутов y) , причем множество значений атрибутов y не связано со значениями атрибутов в отношении u-x-y . обозначение: x-y.

Аксиома 1) –дополнение для многозначной зависимости: если x прин u , y прин u , x- y , то имеет место многозначная зависимость x-u-x-y

Аксиома 2)—пополнение для многозначной зависимости : если x прин u, v прин u , w прин u, y прин u, v прин w , x прин y , то имеет место многозначная зависимость

W объединено k - v объединено y

Аксиома 3) – транзитивность для многозначной зависимости : если x прин u , y прин u , то имеет место многозначная зависимость x-y , y- x , то имеет место x-z-y .

Т.о. формальная проверка многозначной зависимости должна выполняться на множестве z всех возможных экземпляров кортежей рассматриваемого отношения.

КЛЮЧИ ОТНОШЕНИЙ

Формальное определение ключа.

Если R-схема отношения с атрибутами: A1..An, и множество F функциональных зависимостей X-подмножество множества атрибутов, то X называют ключом в случае выполнения следующих условий:

1. зависимость X-> A1..An принадлежит полному замыканию (F+) (полному множеству функциональных зависимостей), которое можно получить из F с помощью правил вывода;