Реферат: Лекции по Основам ВТ

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

  Реляционная модель данных.

Рмд широко используется при построении БД . Они выступают не только в роли даталогических моделей , непосредственно поддерживающих конкретную СУБД , но и качестве вспомогательных промежуточных  моделей при проектировании БД .

  Рмд находят активное применение в качестве виртуальных моделей при построении мультиагентных – мульимодельных систем (internet – технологии)

   Информационные единицы в реляционной модели : домены, атрибуты, отношения

Атрибуты—элементарные информационные единицы. Домен представляет собой ПУЛ (составная единица) значений из которых извлекаются фактические значения атрибутов. Отношение в рмд – двумерная таблица, граф которой является наименьшим атрибутом , а значение элементов каждого из столбцов данной таблицы извлекается из соответствующих доменов.

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

   Отношения в реляционной модели д/б нормализованы . Существует 5 нормальных форм.  Домены не всегда фиксируются в БД в явном виде.

    Характерная особенность реляционной модели: связи м/у отношениями устанавливаются не явном виде , а динамически , по равенству значений соответствующих атрибутов.

   В реляционной модели каждому объекту предметной области соответствует одно или несколько отношений.

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

   Система называется полностью реляционной , если она : 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= d 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 q y  , в этой записи x и y константы или переменные на некотором домене . q– арифметический  оператор сравнения . смысл атома   x y заключается в том, что x и y представляют собой значения при которых атом истин .

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

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

Пример:  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

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