Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Решёткой отмечены ключевые атрибуты. Совокупность ключевых атрибутов является ключом сущности.

Абстракции проектирования

Проектировщик пользуется, в основном, тремя абстракциями (либо осознанно, или нет):

1. агрегация - объединение реквизитов в отдельный экземпляр (кортеж);

2. обобщение - объединение агрегаций в сущность;

3. ассоциация - связь между сущностями.

Разработка спецификация будущих приложений

Приложение - это программа, разрабатываемая в процессе проектирования ИС.

Спецификация программы - это входные и выходные данные и алгоритм связи между ними.

В настоящее время есть несколько способов описания спецификации. Основные:

• структурированный естественный язык;

• визуальные языки описания спецификаций.

Структурированный естественный язык

Конструкция - либо элемент ВЫПОЛНИТЬ действие, либо одна из трёх следующих:

• последовательность конструкций:

конструкция

конструкция

...

конструкция

• конструкция выбора:

ЕСЛИ условие

ТО конструкция

ИНАЧЕ конструкция

КОНЕЦ ЕСЛИ

• конструкция итерации:

ДЛЯ условия

конструкция

конец ДЛЯ

Лекция №6 - Этап логического проектирования

Этап концептуального проектирования

Разработка спецификация будущих приложений

Структурированный естественный язык

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

Спецификация процесса 1.1.2а из DFD "банкомат".

@Вход: Разрешение/отказ ПЦ-Б

@Выход: Признак разрешения для банкомата (0 - нет, 1 - да, 2 - ожидание)

@Спецификация процесс: Проверка разрешения ПЦ-Б

ЕСЛИ разрешение/отказ ПЦ-Б = true ТО

выйти(0)

ИНАЧЕ

выдать сообщение об ошибке

ЕСЛИ ошибка в пароле ТО

проверить счётчик1 на максимум,

запросить пароль,

увеличить счётчик1,

обновить данные транзакции,

повторить функцию "предварительная проверка карты, составление запроса в ПЦ",

выйти(2)

ИНАЧЕ

ЕСЛИ ошибка в сумме ТО

проверить счётчик2 на максимум,

запросить сумму,

увеличить счётчик2,

обновить данные транзакции

ИНАЧЕ

удалить карту из банкомата,

выйти(1)

КОНЕЦ ЕСЛИ

КОНЕЦ ЕСЛИ

КОНЕЦ ЕСЛИ

@Конец спецификации

Визуальные языки разработки спецификаций

Они же FlowForm.

Конструкция - это:

• один элемент "выполнить действие" или просто "действие";

• последовательность конструкций;

• выбор между конструкциями;

• итерация конструкций.

Пример для FlowForm

Описать спецификацию процесса 1.1.2а из DFD "банкомат".

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

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

Рассмотрим на примере Oracle Designer.

Разработка контекстных диаграмм потоков данных

Process Modeler.

К каждому процессу может быть прикреплён мультимедиа-контент, показывающий, что там происходит.

Процессы:

1. изготовление;

2. доставка;

3. приёмы хранения и доставка потребителю.

Разработка диаграммы сущность-связь

Построение DFD и FHD

В DFD можно осуществить привязку потоков к именам и атрибутам сущностей, определённых на предыдущем шаге.

FHD - Function Hierarchy Diagram, формируется на основе DFD. В неё можно включать новые процессы, и они автоматически появятся в DFD (но без связей).

Разработка даталогической схемы БД и приложений

Design Editor.

На этом этапе происходит:

1. генерация даталогической схемы БД на основе инфологической. Строится Data Diagrams;

2. генерация модулей. Строится Module Diagrams.

Сгенерированные формы затем можно изменять в Module Logic Navigator и писать скрипты для обработки событий.

Этап логического проектирования

Задачи этапа:

1. оптимизация схемы БД и генерация даталогической схемы с помощью CASE-средств;

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

Методы индексации данных в реляционных БД

Индекс - некоторая структура, обеспечивающая быстрый поиск данных в БД.

Типы индексов:

• хэш-индекс;

• B-индекс.

Хэш-индекс

Имеет следующую структуру:

Описание:

1. запись данных помещается в таблицу БД;

2. значение ключа q хэшируется, и, тем самым, вычисляется номер раздела i;

3. в i раздел индекса помещается q (без изменений) и p (указатель на запись в БД).

Предположим, что выполняется запрос, и по значению ключа a = q необходимо считать запись.

Доступ к записи можно описать с помощью следующей цепочки: q→h(q)=i→ чтение i раздела хэш-индекса →(q,p)→ чтение по p записи из таблицы БД.

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

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

Лекция №7 - Индексация данных

Этап логического проектирования

Методы индексации данных в реляционных БД

B-индексы

Строятся для следующих атрибутов:

• первичный ключ. Значение атрибутов в индексе уникально;

• альтернативный ключ. Значение атрибутов в индексе уникально;

• инвертированный ключ - произвольный атрибут или набор атрибутов. Значения атрибутов в индексе могут повторяться.

Типы B-индексов:

• обычные индексы - B-tree;

• битовые индексы - Bit Mapped Index;

• реверсивные индексы - Reverse Key Index;

• индекс-таблица - Table Index.

B-tree

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

<

значение атрибута(ов) - mean,

идентификатор записи таблицы БД - rowid

>

B - то есть бинарным - называется потому, что при переполнении блока индекса (они имеют ограниченный размер) он расщепляется на два примерно равных блока (появляется новый), а в блок предыдущего уровня добавляется указатель на новый.

Индексы строятся для конкретного атрибута(ов) конкретной таблицы.

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

rowid имеет сложную структуру: AABCDD.AAY.AB7890.056 - 18 байт.

где:

AABCDD - идентификатор объекта;

AAY - относительный идентификатор файла;

AB7890 - блок внутри файла;

056 - запись внутри блока.

Рассмотрим определение числа уровней в B-деревьеях.

Пусть:

V - число записей в таблице БД;

k - максимальное число записей в одном блоке индекса;

l - число уровней индекса.

Тогда:

Vk - число блоков самого низшего, листового уровня;

Vk2 - число блоков l−1 уровня;

...

Vkl=1 - число блоков первого уровня.

Тогда число уровней:

l=logkV

Оценим объём индекса на листовом уровне. Будем предполагать, что все блоки на этом уровне заполнены.

Введём следующие обозначения:

V - число записей в таблице БД;

Lq - длина индексируемого атрибута;

Lr - длина указателя на запись.

Получаем числов блоков

Q=V⋅(Lq+Lr)

Предположим, задана следующая таблица:

T1

И выдаётся запрос с условием

SELECT * FROM T1

WHERE q = 'A' AND S = 'B'

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

1)

1. система определяет идентификаторы записей по условию q = 'A', используя индекс для q.

2. определяется список идентификаторов записей по условию S = 'B', используя индекс для S.

3. полученные списки пересекаются и там ищется, обычно вложенными циклами. На это требуется время.

2)

1. для поиска записи используется один из индексов: или q, или S;

2. читаются записи;

3. результат определяется программно.

Преимущества B-деревьев:

• при обновлении записи в таблице блокируется только сама обновляемая запись;

• очень хорошо изучены, существуют эффективные алгоритмы реализации.

Недостатки B-деревьев:

• достаточно большой объём, занимаемый индексом;

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

Bit Mapped Index

Структура битового индекса такая же, как и у B-дерева. Отличаются они структурой записи блока листового уровня.

У битового индекса она такова:

<

значение атрибута(ов) - mean,

начальный идентификатор записи - start_rowid,

конечный идентификатор записи - end_rowid,

сегмент двоичной карты - bitmap_segment

>

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

Эта запись означает, что 14, 15, 18 и 20 записи имееют значение атрибута q равное 'A'.

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

Введём следующие обозначения:

V - число записей в таблице БД;

Lq - длина индексируемого атрибута;

Lr - длина указателя на запись;

Lb - длина сегмента bitmap.

Получаем числов блоков

Q=V8⋅Lb⋅(Lq+2⋅Lr+Lb)

Предположим, задана следующая таблица:

T1

И выдаётся запрос с условием

SELECT * FROM T1

WHERE q = 'A' AND S = 'B'

Предположим, что запись блока листового уровня для индекса по атрибуту q имеет вид 'A' 13 20 bitmap_segment1, а для индекса по атрибуту S имеет вид 'B' 13 20 bitmap_segment2.

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

Также скорость проявляется при инвертировании условия запроса: если надо искать не равенство, а неравенство атрибута, то достаточно только инвертировать сегмент, а в B-дереве надо просматривать опять всю таблицу.

Преимущества битового индекса:

• занимает меньший объём, чем B-дерево;

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

Недостаток битового индекса:

• при обновлении одной записи блокируются все записи, связанные с сегментом. Если модифицируется 14 запись, то блокируются записи с 13 по 20, например.

Лекция №8 - SQL

Этап логического проектирования

Методы индексации данных в реляционных БД

Реверсивные индексы

Запись на листовом уровне индекса имеет вид:

<

реверсивные значения индексируемого атрибута - mean,

идентификатор записи – rowid

>

Преимущество реверсивного индекса:

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

Это связано с тем, что окончание слова более равномерно распределено по буквам алфавита, чего его начало (это кто-то доказал).

Пусть для хранения индекса слов используется кластер, состоящий из 5 серверов:

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

Индекс таблиц

Является B-деревьями, и структура записи на листовом уровне имеет вид:

<

ключ таблицы - KEY,

остальные поля записи

>

Преимущество индекса таблиц:

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

Недостатки индекса таблиц:

• резко увеличивается объём индекса;

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

После оптимизации схемы БД, выбора индексируемых атрибутов, характеристик атрибутов и их таблиц выполняется генерация DDL-сценария с помощью CASE-средств (ERwin Data Modeler, например).

DDL-сценарий содержит создание объектов БД (таблицы, индексы, триггеры). Сценарий выполняется средствами СУБД. После этого можно используется язык манипулирования данными.

Некоторые возможности языка SQL

Является общесистемным:

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

• является средством взаимосвязи между серверами (в случае с подзапросами);

• используется почти во всех СУБД с архитектурой клиент-сервер.

Проиллюстрируем язык SQL на примере следующей БД. Поставщик поставляет детали для изделия в данном количестве.

Схема базы данных (таблицы S, P, J, SPJ) в виде ER-диаграммы:

Характеристики

Список файлов лекций