Лекции по Основам ВТ
ько отношений.
Если необходимо в явном виде зафиксировать связь м/у объектами , то
она тоже выражается в виде отношения, в котором в качестве атрибутов
присутствуют идентификаторы взаимосвязанных объектов. Т.о. и объекты
предметной области и связи м/у ними отражаются в рмд посредством
одинаковых информационных конструкций, что значительно упрощает модель.
Система называется полностью реляционной , если она : 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...xk| (
(x1...xn)} (–формула , которая обладает свойством , что только ее
свободные переменные на доменах являются различными переменными.
Пример: {x1x2|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 являются переменными кортежами , (-арифметический оператор (><=) ,
i и j – номера или имена интересующих нас компонент ( столбцов в
соответствующих кортежах) ; s[i] – обозначение i –го компонента в
кортеже переменной s ; u[j] –обозначение j-го компонента в кортеже
переменной u. Пример: s[3]>= 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—тоже является формулой. Экземпляры переменных кортежей являются
| | скачать работу |
Лекции по Основам ВТ |