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

присутствуют идентификаторы взаимосвязанных объектов. Т.о. и объекты

предметной области и связи м/у ними отражаются в рмд посредством

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

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

удаления и модификации данных в БД.

4.перестройка набора отношений при введении новых типов данных, должна

быть минимальной.

5.разброс времени ответа (время реакции системы) на различные запросы

к БД должны быть минимальным (доли секунд, мкс).

Существуют определенные трудности на практике, связанные с

выполнением операций включения, удаления и модификации данных в БД при

неправильном проектировании БД (В данное время должно выполняться с

помощью case-технологий.).

Пусть существуют реляционные БД со следующей схемой и экземпляром

отношения: поставка (индекс, название поставщика, адрес, товар, цена).

Адрес поставщика на практике будет повторяться для каждого

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

БД, связанные с каким-либо изменением в БД. Если у поставщика изменился

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

всех картежах, где оно встретилось. Если бы этого не происходило в

реальных БД, то в противном случае БД стала бы противоречивой, и

нарушилась бы целостность картины данных БД.

1.Аномалия удаления

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

существует поставка от одного поставщика. В этом случае в системе

теряется адрес и название поставщика (хотя с ним может существовать

договор и т.д).

2.Аномалия включения

Возникает в том случае, когда с поставщиком заключается договор, но

поставок от поставщика не было, в данном случае нельзя включать в БД

название поставщика и его адрес, так как нельзя полностью сформировать

картеж (нет данных о поставщиках).

Для того чтобы решить эти проблемы, выполняется нормализация исходных

схем отношения проекта, их композиция и декомпозиция, и назначение

ключей для каждого отношения по определенным правилам нормализации.

Введены 5 уровней схем нормализации отношений.

Поднимаются согласно правилам вложенности по возрастанию номеров.

СХЕМА.

Если находится в 4 НФ, то и находится в 3 УНФ, 3 НФ, 2 НФ, 1 НФ.

1 НФ.

Схема R находится в 1 НФ тогда и только тогда, когда все входящие в

нее атрибуты являются атомарными.

2 НФ.

Если X-ключ отношения R, Y принадлежит X, А является непервичным

атрибутом отношения R, то говорят что в отношении R имеет место

частичная зависимость (неполная функциональная зависимость) X->A и Y->A.

Схема отношения R находится во 2 НФ, если она находится в 1 НФ, и каждый

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

отношения, находящегося во 2 НФ.Может обладать аномалиями для операции

включения, удаления и модификации БД.

3 НФ.

Схема R находится в 3 НФ, если не существует ключа X для R множества,

атрибута Y принадлежит R и непервичного атрибута А из R таких, что

выполняется следующее: X->Y, Y->A, Y-/>X (для R).

Схема R находится в 3 НФ, если она находится во 2 НФ, и каждый

непервичный атрибут нетранзитивно (не напрямую) зависит от первичного

ключа. В тех случаях, когда отношение имеет только 1 ключ и в нем

отсутствуют многозначные зависимости, 3 НФ освобождается от избыточности

и освобождается от аномалий включения, удаления и модификации БД. В тех

случаях, когда в отношении отсутствует многозначные зависимости, но

существует 2 и более возможных ключа. 3 НФ может иметь аномалии

операций. В этом случае для снятия их рассматривается 3 УНФ (НФ Бойса-

Кодда).

4 НФ.

Если в отношении R присутствуют многозначные зависимости, то схема

отношения должна находится в 4 НФ. От 3 НФ отличается тем, что

существует многозначная зависимость из X->->Y {0}, Y-подмножество X, но

X содержит какой-либо ключ отношения R.

5 НФ (Проекционно-соединительная).

Отношения находятся в этой форме тогда и только тогда, когда каждая

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

отношения R. Декомпозиция схем отношений на ряд подсхем. Нормализация

выполняется декомпозицией схем отношений.

Если R={A1..An} P={R1..Rk}

Композиция R1 U R2 U..U Rk={A1..An}

МЕТОДЫ ФИЗИЧЕСКОЙ ОРГАНИЗАЦИИ ДАННЫХ.

Физичиские структуры данных показывают каким образом данные отражаются

в среде хранения. При отражении данных с определенной логической

структурой, с одной стороны должна сохранятся их симантика, а с другой

должна обеспечиваться эффективность обработки данных. На физические

структуры оказывает влияние АБД и запоминает устройства, так как

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

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

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

однозначно определено, элемент имеет степень закрепления. Иногда

структура БД становится гибкой, когда в ключ вводится логика, такие

структуры становятся вычисляемыми или рандомизированными. В

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

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

ними в памяти, а также порядок, согласно которому определяется следующий

элемент. По способу отображения связей между элементами различают

последовательно-смежные, списковые структуры.

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

другом, располагаясь в смежных участках памяти. В списковых - связи

между элементами данных передаются посредством адресных указателей. Для

отражения связей между элементами данных используются символические

указатели.

Символическая связь – повторение значения поля, по которому

производится связывание. Обычно связывающий компонент – идентификатор

данных. Связи между элементами данных отражаются с помощью битовых

структур. В этом случае кроме файла, содержащего сведения об объектах

создаются 1 или несколько битовых структур (битовых векторов или

матриц), показывающих взаимоотношения элементов основного файла.

Совокупность индекса и индексного массива является индексной структурой.

В БД обычно используют довольно сложные многоуровневые логические

структуры данных. Сокращение объема памяти в БД занимаются

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

физических и логических структур данных тесно связано между собой.

Последовательная организация хранения данных (ПОХД).

ПОХД обладает следующими преимуществами:

1.отсутствие дополнительной адресной информации и плотное размещение

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

2.возможность использования любых носителей информации.

3.сокращение времени обработки при условии, что порядок размещение на

носителе совпадает с требованием в порядке обработки.

4.простота организации данных и манипулирование ими, так как идет

увеличение объема памяти и уменьшение цены, то значимость 1 и 2 фактора

снижается.

Последовательные структуры данных имеют недостатки:

1.неудобство корректировки.

2.необходимость разворачивания нелинейных логических структур в

линейные.

3.трудности в обеспечении адекватного, интегрированного отображения

предметной области.

4.длительность выборочного поиска.

5.адаптация новых элементов данных последовательную структуру должно

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

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

В последнее время в связи с широким распространением реляционной БД,

использование последовательных данных в файлах увеличивается. Многие

реляционные СУБД предусматривают организацию хранения каждого отношения

данных в качестве видимого файла.

Списковая организация хранения данных.

Заключается в использование адресных указателей для связей элементов

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

хранением, с объектной, собственной, ассоциативной, адресной

информацией, однонаправленные и двунаправленные списки. Такая

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

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

элементы данных в единую структуру – однородный список. На одном и том

же множестве элементов может быть задано несколько связей, каждая из

которых выделяет подмножество элементов, это списки – многосвязные. Если

информация в списках одного типа, то информация называется гомогенной.

Если информация разнородна, то список называется гетерогенным.

СХЕМА.

Многосвязные списки широко распространены, так как отображение в БД

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

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

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

различных запросов и сокращении в следствии этого числа просматриваемых

элементов. Кроме связывания однотипных используются в БД разнородные

(гетерогенные) структуры, соединяющие разнотипные элементы данных.

При создании БД возможны различные организации однородных и

гетерогенных структур. В некоторых БД каждому из типов элементов может

ставиться отдельная отдельная совокупность (файл). Такая структура –

многофайловая структура.

Списковая организация обладает преимуществами:

1.возможность естественным путем передавать сложные логические

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

добавление и анулирование элементов в списках производится без

физического перемещения элементов путем изменения адреса элементов, при

этом память может быть повторно использована вновь добавляемым

элементом. Новые элементы могут быть привязаны к любому месту памяти.

2.позволяют динамически наращивать состав БД без существенного

изменения существующих ее частей.

3.устраняют дублирование данных (избыточность), позволяют на одном и

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

4.просто могут быть организованы в любой прямоадресной памяти.

НЕДОСТАТКИ:

1. Большой расход памяти на указатели.

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

обработки данных.

3. Потеря адреса связи в каком-либо элементе списка, делает

недоступным всю оставшуюся часть структуры, а искажение адреса приводит

к аварийным ситуациям.

4. Списковая структура нуждается в сложном управлении свободной

памяти.

5. Эффект дробления памяти приводит к необходимости реорганизации

массива.

СИМВОЛИЧЕСКИЕ УКАЗАТЕЛИ. (СУ)

В любой БД устанавливаются СУ, если они автоматически поддерживают

СУБД.

СУ имеют ряд преимуществ перед адресными:

1. Позволяют производить независимую реорганизацию связанных массивов.

2. Повышают семантическую самостоятельность каждой из связанных

совокупностей.

3. Могут быть реализованы в памяти любого типа.

НЕДОСТАТКИ:

1. Расходуется больше времени на поиск и корректировку данных.

2. Требуется больше памяти, чем адресным указателям.

ИНДЕКСНАЯ СТРУКТУРА.

Понятие индекса используется по-разному.

Цель использования индекса – ускорение поиска. В сложных структурах

данных индексы могут использоваться в других целях: для повышения

устойчивости структуры, сокращения дублирования, для обеспечения

быстрого доступа по разным путям к одним и тем же хранимым данным.

Различают структуры с плотной и разряженной индексацией.

При плотной, каждой записи этого файла соответствует элемент индекса.

При

разряженной элементы индекса соответствуют группе записи

индексированного файла. При организации БД преимущество плотной

индексации.

Характеристика индексных структур – способ организации индексного

массива и связаные с ним особенности корректировки структуры.

При разряженной индексации –индексируемый массив должен быть частично

упорядочен. Плотная не предъявляет требований к организации

индексируемого массива. Распределение памяти для расширенного файла –

важно. Выделение специальной области в памяти, их связывает записью,

переплетая в цепочку, как следствие – замедляет процесс обработки данных

в БД, требует ее периодической реорганизации, кроме индексации по

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

индексация – вторичная инвертированная. Она производится как по одному,

так и по сов-ти полей. Рандомизированный

способ доступа.

Быстрый непосретственный доступ по ключу к нужному экземпляру записи.

При загрузке БД и в процессе ее корректировки. Современные СУБД могут

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

отдает на выбор самому пользователю. Пользователь будет делать это с

помощью входного языка среды ЯОД и ЯМД.

Рандомизированный способ хранения предназначен для хранения файловых

структур.

Недостатки прямого доступа к памяти.

1.Записи в памяти различают не в порядке их логического, следовательно

последняя обработка данных медленная.

2. Значительно замедляется время работы БД, при появлении большого

числа синонимов в БД устранение этого эффекта – открытая адресация и

метод цепочек .

При открытой адресации место для синонима ищется в той же области, в

которой размещенны основные записи

Алгоритм поиска свободного места в БД.

Последующий просмотр памяти до свободного места.

При использование метода цепочек, синонимной записи могут

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

располагаться в специальной области переполнений. Длинные цепочки

синонимов увеличивают времена обработки данных. Для большинства

современных алгоритм рандомизированное количество синонимов зависит от

объема памяти, выделенной под файл целиком, поэтому при распределение

памяти выделяется объем на 10 – 25 % больше чем требуется на хранение

данных. Просмотр синонимов БД требует достаточно много времени, для

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

обеспечивает быструю обработку в СУБД ORACLE при доступе записи

переполнение происходит автоматическим переключением с прямого доступа

на метод инвертированных списков. Недостаток прямого доступа к данным

является то, что этот доступ обеспечивает быструю обработку по тому

полю, по которому происходит рандомизация. Основной путь компенсации

этого недостатка – использование комбинированных гибридных гетерогенных

структур данных.

Проектирование структуры БД

Должно включать определенные ее состав и структуры

Проект внешнего информационного обеспечения, технический процесс

пребанковской подготовки, по необходимости для создания БД, а также

организованных методичных и инструктивных материалов.

В современной литературе проект СБД – определение структуры БД и

описание ее на ЯОД конкретизирует СУБД. СУБД поддерживает несемантичные

структуры данных и имеют достаточно жесткие ограничения на

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

информация различает два подхода от предметной области и от запроса.

Подход от предметной области означает описание объектов, отображенных в

инфармационной системе части реального мира и связей между ними без

относительных потребностей пользователя. Подход называется объектным или

процессным.

В подходе от запроса основным источником информации в предметной

области является потребности пользователей. Этот подход называется

функциональным. Преимущество: объективность, системное отображение

предметной области, наличие устойчивой информационной модели,

возможность реализации большого числа приложений, в том числе и заранее

незапланированной.

Недостаток: трудность отбора объективной информации, подлежащий

фиксации БД. Функциональный подход ориентирован на реализацию текущих

запросов пользователя, не учитывая перспектив развития системы.При

использовании этого подхода могут возникнуть трудности между взглядами

различных пользователей. Однако учет запросов позволяет улучшить

характеристики функциональных БД.

Многоуровневость проектирования БД объясняется разницей между

исходной моделью предметной области и той моделью, которая может быть

быстро и эффективно обработана современными программными средствами.С

повышением интеллекта число промежуточных моделей БД должно уменьшаться

. Существует определенная связь между степенью общности модели

поддерживаемой СУБД и числом уровневой моделей, используемых в

проектировании. В зависимости от подхода проект БД эта связь слабая или

сильная среди ряда методов проектирования. Основная идея заключается в

последнем “окружении” исходящей модели с переходом от модели к модели

другого класса. Наблюдается тесная связь между числом уровней моделей и

степенью универсальности использования систем проектирования БД. Чем

ниже степень универсальности систем проектирования БД, тем требуется

меньше уровней моделей.

ТАБЛИЦА.

Проектирование БД - переход от исходного описания модели предметной

области к схеме БД. Для задания моделей употребляются языки высокого

уровня и внутренние языки СУБД.

Построение датологической модели БД.

Глобальная датологическая модель (ДМ) представляет собой отрожение

общего содержания БД, структурированную на логическом уровне и

ориентированную на конкретную СУБД. Любая СУБД оперирует с допустимыми

для нее типами логических структур. Все ДМ различаются наименованиями

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

высокого уровня из состоящих структур младшего уровня) и возможностями

просмотра модели. Любая СУБД накладывает количественное ограничение на

логическую структуру БД, а это в свою очередь оказывает влияние на

проект ДМ. Поэтому прежде чем приступить к посроению ДМ надо тщательно

изучить СУБД, уточнить ее ограничения, определить основные факторы,

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

существующими методиками проектирования в конкретной СУБД.

Если для данной СУБД имеется система автоматизации СУБД CASE-ALLE –

Средство проектирования БД, то с целью оценки качества проекта и

целенаправленности воздействия на созданную структуру БД, желательно

сформировать алгоритм проектирования положенный в ее основу.

При проектировании ДМ БД используется графическая (диаграммо -

логическая) структура и аналитическая (описание на ЯОД схем, подсхем,

форм ее представления БД).

При ручном проектировании построение ДМ начинают с графического

построения структуры БД со всевозможными внутренними и внешними связями.

При автоматизированном проектировании, наоборот получается

аналитическое представление структуры, а затем по этому представлению по

желанию и требованию пользователя воссоздается графическое

представление.

ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ СТРУКТУРЫ БД.

Диаграммы логической структуры БД должны быть наглядными, легко

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

Они должны нести полную информационную нагрузку о логической структуре

БД, давать возможность различать все типы данных и структур, допустимых

в данной системе, обеспечивать взаимооднозначные соответствия между

этими сруктурами и описаниями на ЯОД. Направление связей между

элементами структур указывается на диаграммах только в тех случаях, если

оно однозначно неопределенно типом модели. Все элементы ДМ, которые

должны быть поименованы при написании на ЯОД, должны быть поименованы

при графическом построении ее структуры.

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

принято. Это вызвано тем, что реляционная модель связи в явном виде не

задаются, с другой стороны этот вызвано тем, что в последнее время в

практическом приложении не было таких структур БД, которое было бы

проанализировано с помощью реляционной структурой БД.

ОСОБЕННОСТИ ПРОЕКТИРОВАНИЯ БД.

На проектирование ДМ кроме ограниченных СУБД, накладываемых на

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

физической организации данных. Так если в СУБД с иерархической

логической структурой данных допускались только физически

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

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

выделять такие ветви в отдельные деревья.

Алгоритмы построения логической структуры БД для сетевых систем, в

которых доступ к данным возможен через любую вершину, и систем, в

которых доступы разнородны (выделяет основные и зависимые типы данных и

доступ) к записям зависимых файлов возможен только через основные файлы.

Часто логическое и физическое проектирование БД выполняется в

интерактивном режиме.

При проектирование логические структуры БД следует учитывать общую

семантику ЯОД используемую в конкретной системе.

Кроме факторов обусловленных особенностью конкретной СУБД необходимо

особо рассматривать отображаемую в СУБД предметную область и

характеристики самого пользователя. Алгоритм проектирования логической

структуры БД зависит от вида инфологической модели подхода к проектному

использованию СУБД. Более того, для одной и той же СУБД могут быть

предложены различные алгоритмические проектирования БД.

Проектирование структурных БД имеет особенности:

1.Минимум логической единицы: элементу данных, поле и т. д. Семантика

для всех систем одинакова и, как правило, соответствует либо

идентифицированному объекту, либо свойству процесса.

2. Группировка элементов в более высоких уровней и определение связей

между ними производится в результате совместного анализа ограниченной

СУБД, особенности предметной области потребности пользователя с учетом

ограничений на ресурс.

3. Совместимость типов объектов подлежат отражению в БД и

совместимость их свойств, которые фиксируются для конкретного объекта в

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

этом этапе может быть приведена предварительная классификация.

4. При проектирование логической структуры БД присутствуют этапы

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

СУБД и проверки адекватности получения ДМ в исходные модели.

5. Для каждого конкретного СУБД может быть задан набор правил и

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

Число допустимых для заданных исходных данных обычно бывает сравнительно

велико, поэтому необходим аппарат, оптимизирующий данные, решающий

структуру данной модели.

6. Отображение связи между элементами на уровне ДМ может выполняться

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

путем объявления связей, путем введения дополнительного связующего

элемента. Последняя ситуация подкрепляет структуру БД обходя те

ограничения накладываемые конкретным СУБД.

7. Логическая структура БД может передавать не только связи между

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

в процессе обработки информации в БД, что может являться препятствием

для проектирования ДМ БД.

Особенность организации распределенных БД (РБД).

Наиболее интересным в РБД является размещение данных в узлах сети (без

дублирования, с частичным и полностью избыточным). Стоимость хранимых

данных минимальна для РБД без дублирования. Однако если учитывать не

только затраты на хранение, но и суммарные затраты на передачу и

хранение данных, то наиболее приемлемые частично дублированные РБД и

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

на запросы, повысить надежность и защищенность системы. Как полностью,

так и избыточно системы должны иметь определенный механизм,

обеспечивающий равенство всех копий описания одинаковой сущности.

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

наличие дублей в системе, а также стратегия обновления, определяющая в

лучшем случае - за кем закреплена функция в каждом из дублей, а также

каким образом учитываются временные задержки при внесении изменений в

копии, каким образом выбирается оптимальный поток информации.

Задача выбора информационной структуры может для РБД решаться на

различных этапах ее жизненного цикла при первоначальном проектировании

системы, при наличии сформировавшейся сети пользователей, при сложном

составе структуры РБД. В первом случае ставится глобальная задача

определения конфигурации сети и размещения данных по ее узлам.

Чаще всего РБД создается на базе сложившейся сети, что является

сильным ограничением при решении различных прикладных задач. Время

реакции системы сильно тормозит. На распределенные данные по узлам сети

влияют следующие факторы: объем, частота и место возникновения

информации.

Характеристика запросов (частота, сложность, время возникновения,

ограничение доступа, объем передаваемой информации, типы запросов и

т.д).

Характеристика технических средств обработки и передачи данных, и

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

сети.

Задача распределения данных сильно усложняется, если она решается

совместно по распределенным узлам сети и связана напрямую с программой

запросов. Сложность возникает, когда неоднородные ЭВМ

Распределение данных может быть проведено либо в соответствии со

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

данных во всех узлах сети одинакова. Различают значения данных,

например, однотипные отчетные данные могут храниться в локальных БД,

имеющих эдентичную структуру и распределение.

Такое распределение может быть при использовании однотипных СУБД в

разных узлах РБД. При распределении в соответствии со структурой данных

в локальные БД различают и по составу, и по структуре.Например, каждая

из служебных предприятий может иметь локальные БД соответствующего

содержания, которые могут быть объединены в единую структуру и

образовывать единую систему. Основные вопросы при проектировании РБД

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

информации в системе.

Возможны следующие варианты поиска:

1. Пользователь взаимодействует с ближними БД. Если требуемая

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

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

потоками запросов информации и требует большое время на поиск.

2. Пользователь взаимодействует со соответствующей БД. Если информации

нет, то по структуре информации описывает размещение данных в РБД,

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

происходит обращение к этому узлу. В этом случае предполагается хранение

структурной информации в каждом узле. Объем структурной информации можно

уменьшить, если в каждой БД хранить сведения не о всех массивах в РБД, а

только лишь о тех, которые могут обращаться к опонентам прикрепленных к

данному узлу. Этот вариант характеризуется большим объемом информации,

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

минимальны.

3. Одна из БД выделяется как главная или управляемая (в ней содержится

вся структурная информация). Пользователь обращается в ближние БД, если

информации не обнаружено, то информация идет либо в управляемую БД, либо

управляемый узел. После нахождения адреса хранимой информации происходит

обращение к соответствующей БД.

По сравнению с другим вариантом объем структурной информации

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

требование надежности, усиливается роль управляемой БД.

Структурная и другая служебная информация содержится в сетевом

словаре-справочнике. В нем должна быть информация о размещении данных в

узлах сети, общая логическая структура БД,стандарт БД В каждом из узлов

содержится информация характеризующая структуру данных, частоту и режим

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

пользователей. В зависимости от принятой в РБД стратегии поиска

различают соответствующие им справочные структуры (местная локально -

распределенная, центральная, распределено – центральная или

комбинированная).

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