00-00001 (Лекции по Основам ВТ), страница 10

Заключается в использование адресных указателей для связей элементов данных. Различают списковую организацию с совместным и раздельным хранением, с объектной, собственной, ассоциативной, адресной информацией, однонаправленные и двунаправленные списки. Такая классификация списковых структур традиционная. Взависимости от характера связывания элементов, списковая структура может связывать однотипные элементы данных в единую структуру – однородный список. На одном и том же множестве элементов может быть задано несколько связей, каждая из которых выделяет подмножество элементов, это списки – многосвязные. Если информация в списках одного типа, то информация называется гомогенной. Если информация разнородна, то список называется гетерогенным.

СХЕМА.

Многосвязные списки широко распространены, так как отображение в БД предметной области требует много связей. C другими такие структуры просты в реализации, позволяющие сократить дублирование данных, уменьшить время обработки данных за счет выделения подмножеств для различных запросов и сокращении в следствии этого числа просматриваемых элементов. Кроме связывания однотипных используются в БД разнородные (гетерогенные) структуры, соединяющие разнотипные элементы данных.

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

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

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

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

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

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

НЕДОСТАТКИ:

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

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

3. Потеря адреса связи в каком-либо элементе списка, делает недоступным всю оставшуюся часть структуры, а искажение адреса приводит к аварийным ситуациям.

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

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

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

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

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

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

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

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

НЕДОСТАТКИ:

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

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

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

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

Цель использования индекса – ускорение поиска. В сложных структурах данных индексы могут использоваться в других целях: для повышения устойчивости структуры, сокращения дублирования, для обеспечения быстрого доступа по разным путям к одним и тем же хранимым данным. Различают структуры с плотной и разряженной индексацией.

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

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

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

При разряженной индексации –индексируемый массив должен быть частично упорядочен. Плотная не предъявляет требований к организации индексируемого массива. Распределение памяти для расширенного файла – важно. Выделение специальной области в памяти, их связывает записью, переплетая в цепочку, как следствие – замедляет процесс обработки данных в БД, требует ее периодической реорганизации, кроме индексации по ключивой записи плотная индексация по любому полю записи. Такая индексация – вторичная инвертированная. Она производится как по одному, так и по сов-ти полей. Рандомизированный способ доступа.

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

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

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

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

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

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

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

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

При использование метода цепочек, синонимной записи могут располагаться в той же области, что и основные записи, а также располагаться в специальной области переполнений. Длинные цепочки синонимов увеличивают времена обработки данных. Для большинства современных алгоритм рандомизированное количество синонимов зависит от объема памяти, выделенной под файл целиком, поэтому при распределение памяти выделяется объем на 10 – 25 % больше чем требуется на хранение данных. Просмотр синонимов БД требует достаточно много времени, для обработки синонимов применяются специальные методы организации данных, обеспечивает быструю обработку в СУБД ORACLE при доступе записи переполнение происходит автоматическим переключением с прямого доступа на метод инвертированных списков. Недостаток прямого доступа к данным является то, что этот доступ обеспечивает быструю обработку по тому полю, по которому происходит рандомизация. Основной путь компенсации этого недостатка – использование комбинированных гибридных гетерогенных структур данных.

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

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

Проект внешнего информационного обеспечения, технический процесс пребанковской подготовки, по необходимости для создания БД, а также организованных методичных и инструктивных материалов.

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

В подходе от запроса основным источником информации в предметной области является потребности пользователей. Этот подход называется функциональным. Преимущество: объективность, системное отображение предметной области, наличие устойчивой информационной модели, возможность реализации большого числа приложений, в том числе и заранее незапланированной.

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

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

ТАБЛИЦА.

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

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

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

Если для данной СУБД имеется система автоматизации СУБД CASE-ALLE – Средство проектирования БД, то с целью оценки качества проекта и целенаправленности воздействия на созданную структуру БД, желательно сформировать алгоритм проектирования положенный в ее основу.

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

При ручном проектировании построение ДМ начинают с графического построения структуры БД со всевозможными внутренними и внешними связями.

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

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

Диаграммы логической структуры БД должны быть наглядными, легко читаемыми, стандартизированными (не допускать неоднозначных толкований). Они должны нести полную информационную нагрузку о логической структуре БД, давать возможность различать все типы данных и структур, допустимых в данной системе, обеспечивать взаимооднозначные соответствия между этими сруктурами и описаниями на ЯОД. Направление связей между элементами структур указывается на диаграммах только в тех случаях, если оно однозначно неопределенно типом модели. Все элементы ДМ, которые должны быть поименованы при написании на ЯОД, должны быть поименованы при графическом построении ее структуры.

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

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

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

Алгоритмы построения логической структуры БД для сетевых систем, в которых доступ к данным возможен через любую вершину, и систем, в которых доступы разнородны (выделяет основные и зависимые типы данных и доступ) к записям зависимых файлов возможен только через основные файлы. Часто логическое и физическое проектирование БД выполняется в интерактивном режиме.

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

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

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

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

2. Группировка элементов в более высоких уровней и определение связей между ними производится в результате совместного анализа ограниченной СУБД, особенности предметной области потребности пользователя с учетом ограничений на ресурс.