Лекции по Основам ВТ
свободными или связанными. 3) если ( - формула, то существует такая
S((), которая тоже является формулой ,т.е. (( (S(() 4) если (-формула,
то существует S(() тоже формула. 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/ ((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/ ( (t1...tk}
, ( -это ( в котором осуществлена замена переменных.
Теорема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 с
помощью правил вывода;
2. ни для какого собственного подмножества X зависимость Y из
атрибутовY-> A1..An,Y принадлежит X , не принадлежит полному замыканию
F+.
Условие (2) ставит вопрос о минимальности ключа. Данный ключ только
тогда будет являться ключом отношений, когда он является минимальным
(max ссылок связей в отношениях). В противном случае ключом будет 1 или
более элементов из его подмножеств.
ОПР. (о первичных атрибутах).
Атрибут A является первичным тогда и только тогда, когда он входит в
состав любого ключа (первичного или возможного) в отношении R.В
противном случае – атрибут непервичный.
Нормализация отношений (подразумевается неизбыточность базы)
Задача группировки атрибутов в отношениях, при условии, что набор
возможных отношений заранее не фиксируется, допускает большое количество
различных вариантов этих отношений и приводит к проблеме выбора
рационального варианта из множества альтернативных вариантов схемы
отношений. Рациональные варианты группировки атрибутов в отношении
должны отвечать следующим требованиям:
1.выбрать для отношений первичные (и возможные) ключи, которые должны
быть минимальными.
2.выбрать состав отношений базы, который должен быть минимальным
(отличающийся минимальной избыточностью атрибутов).
3.не должно быть трудностей при выполнении операций включения,
удаления и модификации данных в БД.
4.перестройка набора отношений при введении новых типов данных, должна
быть минимальной.
5.разброс времени ответа (время реакции системы) на различные запросы
к БД должны быть минимальным (доли секунд, мкс).
Существуют определенные трудности на практике, связанные с
выполнением операций включения, удаления и модификации данных в БД при
неправильном проектировании БД (В данное время должно выполняться с
помощью case-технологий.).
Пусть существуют реляционные БД со следующей схемой и экземпляром
отношения: поставка (индекс, название поставщика, адрес, товар, цена).
Адрес поставщика на практике будет повторяться для каждого
поставляемого товара. Такие ситуации называются аномалиями модификации в
БД, связанные с каким-либо изменением в БД. Если у поставщика изменился
адрес, то должны выполняться соответствующие изменения данных адресов во
всех картежах, где оно встретилось. Если бы этого не происходило в
реальных БД, то в противном случае БД стала бы противоречивой, и
нарушилас
| |  скачать работу |
Лекции по Основам ВТ |
