Лекции по Основам ВТ

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

Система называется полностью реляционной , если она : 1

поддерживает структурные аспекты реляционной модели ; 2 выполняет

соответствующие ей правила включения , коррекции , исключения; 3система

обладает подъязыком данных , по меньшей мере таким же мощным как алгебра

отношений. Система в которой выполняются 1,2 условия , но не

выполняется 3 называются полуреляционными.

Различают бинарные рмд и рмд допускающие отношения произвольных

степеней—более известны.

В реляционных системах используются языки манипулирования различных

типов: языки основанные на реляционной алгебре , реляционных

исчислениях, языки , базирующиеся на концепции отображения.

Могут широко применятся процедурные языки, которые манипулируют

отдельными картежеми отношений.

Пусть существует декартово произведение доменов Д1...Дк его можно

представить Д1...Дк=Д1*Д2...Дк , где Д1={a11, a12,...,a1i,...,a1n}...

Дк={ak1,ak2,...,aki,...,akn}

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

одному из каждого домена di , имеющего вид: (d1i,d2i...dkik)

Например: Д1={A,2} Д2={B,C} Д3={4,5,D}. Задача: требуется найти

декартово произведение доменов. Д=Д1*Д2*Д3={(A,B,4) , (A,B,5), (A,B,D),

(A,C,4), (A,C,5), (A,C,D), (2,B,4), (2,B,5), (2,B,D), (2,C,4), (2,C,5),

(2,C,D)}

Отношение R называется подмножеством декартового произведения Д1...Дк

(R->Д1 ,Д2...Дк) Отношение R, определенное на множествах Д1...Дк , есть

некоторое множество кортежей арности к, т.е. элементарных отношений

являющихся кортежами.

Схема кортежного отношения на доменах. Таблица6.

В ряде случаев отношение удобно представлять как таблицу, где каждая

строка есть кортеж, а каждый столбец соответствует тому же компоненту

декартового произведения.

Такие таблицы обладают следующими свойствами : 1 порядок столбцов

фиксирован 2 порядок строк безразличен 3 любые 2 строки различаются хотя

бы одним элементом 4 строки и столбцы таблицы могут обрабатываться в

любой последовательности .

Список имен атрибутов отношений называется схемой отношения.

Если отношение является R и его схема имеет атрибуты А1...Ак , то

схема отношения обозначается в БД следующим образом: R(A1,...,Ak)

Существует аналогия м/у схемой отношения и ? , м/у кортежем и

записью , м/у отношением и файлом.

Одной из возможных реализаций отношения является файл записи ,

формат которого соответствует схеме отношения .

Реляционные БД содержат конечное множество отношений экземпляров:

R1(A11,A12,....,A1k1) ,R2(A21,A22,...,A2k2) ,..., Rm(Rm1,Rm2,...Rmk)

Выполнение операций над отношениями.

Для получения информации из отношения необходим язык манипулирования

данными , выполняющий соответствующие операции над отношениями.

Наиболее важным в ЯМД является раздел формирования запросов . Т.к.

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

отношениями , необходимо решить вопрос о требуемой выразительности языка

запросов.

Для этих целей были разработаны 3 абстрактных теоретических языка: 1

реляционная алгебра ;2 реляционное исчисление с переменными кортежами; 3

реляционное исчисление с переменными доменами.

Языки запроса 1-о типа –алгебраические языки . Они позволяют

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

отношениям.

Языки 2-о и 3-о типов—это языки исчисления, которые позволяют

выражать запросы путем спецификации предиката , которому должны

удовлетворять требуемые кортежи (домены). Эти языки служат эталоном для

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

Самым распространенным языком запросов является SQL , разработан

Кодасил в 1970 г. Также есть ISBL и QBE (по структуре похожие на SQL)

Эти языки обеспечивают не только функции соответствия

теоретического языка или их комбинаций, но и реализуют некоторые

дополнительные комбинации –операции, а именно: арифметические операции ,

команды присваивания и печати.

Реляционная алгебра.

При определении реляционной алгебры и ее операций предполагается , что

порядок столбцов в отношении фиксирован, а сами отношения конечны.

Основные операции:

1 объединение отношений R=R1uR2. Операция применяется к отношениям той

же арности . Таблица 7.

2 разность отношений R=R1-R2 разностью R1-R2 называется множество

кортежей принадлежащих только R1 и не принадлежащих R2 Отношения R1 R2

R д/б одинаковой арности.

3 декартово произведение отношений R=R1*R2 . Если отношение R1 имеет

арность к1, а отношение R2 арности к2 , то декартовым произведением

R1*R2 называется множество кортежей арности к1+к2 , причем первые к1

–элемент образуют кортежи из отношения R1, а последние к2 –элементов

образованы кортежами из отношения R2. R1*R2((k1+k2)

4 проекция отношения R1 на компоненты i1,i2,...,ir (R1(i1,...,ir)

Запись: R=п i1,i2, ...,ir (R1) , где i1...ir- номера столбцов отношения

R1 . Операция проекции отношения заключается в том ,что из отношения R1

выбираются указанные столбцы и компоненты в указанном порядке.

5 селекция отношения R1 по формуле R , R= ( f(R1) , где F –это форма ,

которая м/б образована а) опероидами , являющиеся номерами столбцов б)

логическими операторами : и , или , не . в) арифметическими операторами

сравнения.. В формуле м/б использованы скобки .

6 пересечение отношений R=R1 ( R2 =R1-(R1-R2)

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

В реляционных исчислениях с переменными доменами не существует

переменных кортежей . Вместо них существуют переменные на доменах.

В остальном реляционное исчисление с переменными на доменах строятся

так же как переменные на кортежах , с теми же операторами.

Атомами формул м/б: 1) R(x1...xk) , где R к-арная отношение xi,

i=1...k –константа или переменная на некотором домене. Запись означает:

атом R с отношением указывает значение тех xi, которые являются

переменными и которые д/б выбраны т/о , чтобы x1...xk было кортежем

отношения R.

2) x ( y , в этой записи x и y константы или переменные на некотором

домене . (– арифметический оператор сравнения . смысл атома x y

заключается в том, что x и y представляют собой значения при которых

атом истин .

формулы в реляционном исчислении с переменными на доменах

используют логические связки и, или, не и кванторы всеобщности и

существования.

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

свободные переменные на доменах являются различными переменными.

Пример: R1(x1x2)(((y)(( R2(x1y)(( R2(x2y) Означает множество

таких кортежей в R1, что ни один из их компонентов , не является

первым компонентом какого-либо отношения R2.

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

Вид выражения: { t/.(. (t)} t относится к .(. (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] ( u[j] , где s и

u являются переменными кортежами , (-арифметический оператор (>= u[5] 3-й компонент переменной s >= 5-го

компонента переменной u. 3) s[i] ( a равносильно a ( s[i] ,где a-

конст. пример: s[3]=70 3-й компонент кортежа s равен 70.

При записи формул используются понятия свободных и связанных

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

кванторов.(( и () Кванторы играют ту же роль , что и декларации в

языках программирования.

Понятие свободных переменных аналогично понятию глобальных

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

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

процедуре.

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

переменных кортежей.

1) каждый атом—есть формула , все вхождения переменных кортежей

упомянутых в атоме являются свободными. 2) если (1 и (2—формулы , то

справедливо: 1. (1 1( (2 являются истинными, 2. (1U (2 обе истинны и

также являются формулами. В виде дополнения в литературе добавляют (

(1—тоже является формулой. Экземпляры переменных кортежей являются

свободными или связанными. 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.не должно быть трудностей при выполнении операций включения,

Страницы: 1, 2, 3, 4, 5, 6, 7, 8