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

соответствующей схеме этой БД.

  Прародитель всех иерархических БД является 1 модель СУБД Ака. Структурными единицами в этой БД являлись: поле, сегмент, физическая связь, логическая связь, физическая БД.

   Поле—поименованная наименьшая единица данных. Поле принимает символические и числовые значения. Сегмент—поименованная совокупность полей  Физическая/логическая связь—понятия групповых отношений.

   Главным сегментом группового отношения объявляется исходный, детальный сегмент—порожденная физическая БД—поименованная совокупнсть экземпляров сегментов и физических связей , образующих иерархическую структуру максимум 15 уровня. Количество сегментов в иерархической БД ограничено числом 255, количество полей 1000. Таблица2.

Сетевая модель данных.

СМД  базируется на графовой форме представления данных. Вершина графа используется для интерпретации  типов сущностей., а дуги – типов связей.

   При реализации моделей в различных СУБД , можно применять различные способы представления в памяти  системы  данных, описывающих связи м/у сущностями.

    Доминирующее влияние на развитие СМД в соответствии со стандартами СУБД  оказала группа Кодасил (стандарт ISO)  Модель Кодасил постоянно развивается , по мере совершенствования вычислительной техники. По мере появления новой версии , появляется новый стандарт.

   Типы структур в модели Кодасил.: элемент данных, агрегат, запись, набор, БД. Таблица3.  

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

   Допустим структура записей в различных системах БД различны ( в одних—это линейная последовательность полей , в других структурах возможна иерархическая структуризация записей)

   Почти во всех СУБД , поддерживающих сетевые модели, м/у парой типов записей м/б объявлены несколько типов связей. Направление и характер связей в сетевых моделях не являются очевидными, по сравнению с иерархическими моделями. Поэтому  имена и направления связей должны указываться как при графическом изображении БД , так и при ее непосредственном описании на языке обработки данных.  В большинстве современных СУБД беспроблемно реализуется сетевая модель.

  М/у каждой парой типов записей поддерживается отношение 1:М.

  Структуры сетевых БД строятся на основе следующих правил: БД может содержать любое количество типов записей и типов наборов; м/у двумя типами записей м/б определено любое количество типов наборов; тип записи м/б одновременно и владельцем и составным элементом нескольких различных типов наборов.

   Основные ограничения сетевой модели с т/з  реализации ее, является реализация трех типов отношений : 1:м , 1:1 , М:1. Вводят вспомогательный тип записи для поддержания отношения М:М и две связи 1:М и М:1.  Таблица 4.

  Системы с разнородными файлами.

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

   В таких системах файлы БД разделяются на 2 типа: основные (главные) и зависимые. Причем каждый файл может выступать в одном из этих качеств .

  Вход в систему м/б осуществлен только ч/з главные файлы . Различие м/у фалами оговаривается и указывается как при графическом изображении БД , так и при написании на ЯОД .

  В сетевых системах с разнородными файлами существуют различия на устранение связей м/у ними. А именно: можно соединить м/у собой файлы разных типов.Табл5

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

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

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

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

  Рмд находят активное применение в качестве виртуальных моделей при построении мультиагентных – мульимодельных систем (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

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

Теорема для многозначной зависимости : многзначная зависимость существует , если при заданных значениях атрибутов , существует множество состоящее из нулей ( или более взаимных значений атрибутов 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.перестройка набора отношений при введении новых типов данных, должна быть минимальной.

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