Методология общесистемного проектирования (МОП).

Лекция 1

Модели проектирования распределенных систем обработки данных (РСОД).

Пример РСОД:

Router необходим для гашения broadcast рассылок.

Предположим, что с WS в Санкт-Петербурге формируется следующий запрос к БД: НАЙТИ КЛИЕНТОВ БАНКА, У КОТОРЫХ ОСТАТОК НА СЧЕТЕ В САНКТ-ПЕТЕРБУРГЕ >=2000 у.е., А В МОСКВЕ >=1000 у.е. В виде SQL оператора запрос поступает на БД Сервера 2 и там оптимизируется, при этом выполняются следующие задачи:

1. Формирование подзапроса к БД Сервера 1 (НАЙТИ КЛИЕНТОВ У КОТОРЫХ ОСТАТОК >=1000 у.е. И ИМЕЮЩИХ СЧЕТ В САНКТ-ПЕТЕРБУРГЕ). Результат возвращается на БД Сервера 2.

2. Формирование подзапроса к БД Сервера 2 (НАЙТИ КЛИЕНТОВ, У КОТОРЫХ НА СЧЕТЕ В САНКТ-ПЕТЕРБУРГЕ ИМЕЕТСЯ >=2000 у.е.). Этот запрос выполняется на Сервере 2.

3. Полученные результаты на этапах 1 и 2 соединяются по общим атрибутам.

4. Результат возвращается на станцию, подавшую запрос.

РСОД – система, в которой ее данные и/или программа располагается в разных узлах (серверах) сети и обеспечивает прозрачный (клиент не видит реализации) доступ к данным.

В настоящее время существует два подхода к проектированию РСОД:

1. Структурный

2. Объектно-ориентированный

Два принципа структурного подхода:

1. Общая задача проектирования декомпозируется на подзадачи по иерархии сверху вниз.

2. Процедурный подход программирования.

Два принципа объектно-ориентированного подхода:

1. Наличие объектов и связей между ними.

2. Используется ООП, а также объектные СУБД.

Недостатки объектно-ориентированного подхода:

1. Некоторые ПО очень трудно представить в виде объектов (экономика, медицина)

2. Существуют трудности в детальном описании схемы БД в нотации UML.

Данный курс ориентирован на структурный подход!!!

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

1. Каскадная модель (использовалась до середины 80х)

2. Спиральная модель (используется по настоящее время)

Каскадная модель проектирования СОД.

Выявление потребностей конечных пользователей.

Концептуальный проект.

Архитектура системы.

Логическое проектирование.

Комплексная отладка.

6. Сопровождение.

Пилотный проект

Краткое описание этапов каскадного проектирования.

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

Пример:

d22=f2(d12,d21)=f2(f1(d11),d21)

2. В функциональном графе данные и процессы объединены и в принципе его достаточно для реализации будущей системы (см. формулу к рисунку), но современные компьютеры есть машины Фон-Неймана, где предполагается разделение процессов и данных.

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

Пример: (Инфологическая модель БД в нотации Чена)

Спецификация процессов - входные и выходные данные процессов, а также алгоритмическая связь между ними. Для описания спецификации существуют различные методы: структурированный естественный язык (часто используется), язык проектирования спецификации Flow-Form (визуальные языки).

Концептуальный проект не зависит от архитектуры!!!

Лекция 2

3. выбор архитектуры:

- Модель доступа к данным

- Комплекс технических средств (выбор «железа»)

- Общесистемные пакеты

-Тиражирование данных

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

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

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

Достоинства каскадной модели:

- проста, естественна, имеет некоторую привязку к ГОСТу

Недостатки:

- достаточно продолжительный цикл разработки по времени (система морально устаревает)

- доработка системы связана с большим объемом перепрограммирования (из-за слабого использования CASE-средств)

Результаты исследований Д.Мартина (сер. 80х)

1я диаграмма: распределение ошибок и просчетов по этапам проектирования, выявленных при сопровождении системы

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

3я диаграмма: распределение трудозатрат по этапам проектирования

Почти половина трудозатрат приходится на устранение ошибок, допущенных на первых 2х этапах

На основании исследований Мартин сформулировал законы:

1. закон неопределенности в информатике:

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

2. чем больше времени прошло с момента совершения ошибки до момента ее обнаружения, тем больше средств необходимо для ее устранения (смотри диаграмму 2)

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

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

Спиральная модель проектирования

Содержание этапов совпадает с аналогичными в каскадной модели, но в отличие от нее, этапы реализуются с помощью CASE- средств ( Computer Aided Software System Design) – использование этих средств позволяет существенно снизить время реализации витка спирали проектирования подсистем, но это профессиональные средства, непредназначенные для конечных пользователей.

CASE- средства – этапы применения:

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

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

3. с помощью языков 4GL приложение дорабатывается, пишутся скрипты и обработчики

Выявление информационных потребностей конечного пользователя

Используются 2 типа диаграмм:

- SADT (Structure Analysis and Design Technology)

- DFD (Data Flow Diagram)

SADT диаграммы

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

DFD

Используются для описания функционирования АС предприятия, т.е. машинной обработки

Нотация Гейна-Саксона

Общая схема выявления информационных потребностей конечных пользователей с использованием DFD

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

Для листовых процессов разрабатываются спецификации программ.

Лекция 3

Пример построения DFD- диаграммы

Задача

Разработать фрагменты DFD-диаграммы системы, организующей работу банкомата по обслуживанию клиента по его пластиковой карте.

Предпосылки:

1) Пластиковая карта является дебетовой (можно снять деньги)

2) Используется карта с магнитной полосой, без чипа.

3) Авторизацию карт выполняет банк-эмитент (проверку реквизитов).

4) Банкомат, процессинговый центр и традиционная банковская система работает в режиме online(запрос-ответ)

1. Контекстная диаграмма.

2. Детализация процесса «обслужить»

После ввода пластиковой карты, PIN-кода и суммы формируется запрос Б-ПЦ в процессиговом центре, который является связующим звеном между банкоматом и традиционной банковской системой. ПЦ формирует запрос (ПЦ-БЭ) в банк-эмитент. Банк-эмитент анализирует реквизиты пластиковой карты (PIN-код, сумма) и выдает разрешение БЭ-ПЦ. Процессинговый центр транслирует это разрешение в разрешение ПЦ-Б, которое передается банкомату. Банкомат выполняет требуемое действие (выдает деньги). После этого банкомат дает подтверждение в процессинговый центр (подтверждение Б-ПЦ).

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

Замечание:

1) Платежная система-это ассоциация банков, объединившихся с целью выпуска и обслуживания пластиковых карт (Visa, Maestro…)

2) Банк может быть участником нескольких платежных систем.

3) Банкоматы, процессинговые центры и банковские системы обслуживания карт образуют распределенную систему. Её работа прозрачна для клиента (он не знает о транзакциях).

3. Детализация процесса «банкомат» (1.1)

Тип платежной системы, номер карты, срок действия карты, ИД банка-эмитента, ИД банкомата, PIN-код и сумма объединяются в данные транзакций, которые запоминаются в хранилище 2. Эти данные используются при формировании запроса Б-ПЦ (1.1.2) для выполнения требуемых операций (1.1.3-1.1.5), а так же для составления подтверждения в ПЦ (1.1.6)

4. Детализация процесса в процессинговом центре (1.2)

Процессинговый центр выполняет верификацию запроса от банкомата (1.2.1), формирует запрос в банк-эмитент (1.2.2), обрабатывает разрешение от банка-эмитента (1.2.3), а так же передает платежные документы в расчетный банк (1.2.4)

Схема расчетов между банками

Для расчетов между банками используются корреспондентские счета ЛОРО и НОСТРО.

Расчетный банк – банк, в который поступили документы из процессингового центра (корреспондирующий).

Банк-эквайер – собственник банкомата.

2-3: НОСТРО-счет – корреспондентский счет расчетного банка открытый в банке-эмитенте.

ЛОРО-счет – счет расчетного банка открытый в нем для обслуживания банка-эмитента.

5-8: ЛОРО и НОСТРО счета, открытые для взаимных расчетов между расчетным банком и банком-эквайером.

Д – дебет – снятие

К – кредит – зачисление.

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

1) Проводка (д1,к1). Дебет по карт-счету, кредит по НОСТРО-счету в банке-эмитенте.

2) проводка (д2,к2). Дебет по ЛОРО-счету расчетного банка, кредит по ЛОРО-счету расчетного банка для банка-эквайера.

3) Проводка (д3,к3). Дебет по НОСТРО-счету банка-эквайера и кредит по счету обслуживаемого банкомата.

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

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

По запросу ПЦ-БЭ выполняется проверка реквизитов карты и выдается разрешение БЭ-ПЦ на выполнение операции.

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

Примечание:

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

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

2) в рассмотренных диаграммах проводки по ЛОРО и НОСТРО счетам выполняются по каждой операции в банкомате, что очень не рационально, поэтому часто ля расчета используются клиринговые центры.

Лекция 4

Клиринговый центр.

Обязательства – эта та сумма, которая перечислена банком другому банку.

Она может быть равна нулю.

Требования – сумма, которую другой банк должен данному банку.

∆ ₂ = Т₁-О₂ - долг банка 2 банку 1

∆ ₁ = Т₂ – О₁ – долг банка 1 банку 2

1) если ∆ ₁ =∆ ₂ то происходит взаиморасчет и никаких платежей не осуществляется.

2) если ∆ ₁ > ∆ ₂ Банку 2 предоставляется кредит клиринговым центром и гасится долг. Кредит равен ∆ ₁ – ∆ ₂

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

1) Designer 6i (Oracle)

Этот продукт позволяет автоматизировать все основные этапы витка разработки автоматизированной системы (этапы 2-6) кроме этапа выбора архитектуры.

Недостатки: разработанный пилотный проект может функционировать только в среде Oracle

2) Silverrun, PRO IV

Эта пара так же позволяет автоматизировать этапы 2-6 витка АС, но с помощью этих продуктов можно генерировать пакет для различных платформ (Oracle, Informix, Sybase)

3) BPwin

С помощью него можно строить DFD диаграммы, генерировать отчеты, имеет связь с пакетом Erwin на уровне импорта-экспорта данных.

Лабораторная работа № 1

1) с помощью пакета BPwin разработать DFD-диаграмму системы, организующей работу банкомата по обслуживанию клиента по его пластиковой карте (см. лекцию.)

2) сгенерировать отчет диаграмм Object report.

Требования к отчету:

1. Рисунки DFD-диаграмм и их краткое описание

2. Привести отчет Diagram Object Report

Литература Маклаков С.В. «Создание информационных систем».

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

На этом этапе решаются следующие задачи:

1. Разрабатывается инфологическая схема БД

2. Разрабатывается спецификация будущих прикладных задач.

Проектирование инфологической схемы БД.

Для описания схем БД используется диаграмма «сущность- связь» (ERD Entity – relationship diagram)

Для разработки ERD используется следующая нотация:

1. Нотация Чена (используется для ручного проектирования информационных схем)

2. Нотация Барнера (используется для машинного проектирования схем БД Oracle)

3. Нотация IDE F1x (ERwin, PowerDesigner) ERwin позволят создавать инфологические схемы, а потом автоматически генерировать даталогические модели для более чем 20 СУБД.

имя

Описание инфологический схемы БД в нотации Чена.

– независимая сущность. Эта сущность может присутствовать в схеме БД в 2х случаях:

-сущность не является дочерней

-она является дочерней, но связанна с родительской сущностью, не идентифицирующей связью.

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

Блок-схема: решение: имя

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

Характеристики связей приведены в следующей таблице.

	Тип связи
Свойства	Идентифицирующая	Неидентифицирующая
Обозначения на диаграмме Гена	Глагольная форма со знаком *	Глагольная форма без знака *
Куда добавляются ключ родительской сущности при создании дочерней 1:М (1 – родительская; М - дочерняя)	К ключевым атрибутам дочерней сущности	К не ключевым атрибутам дочерней сущности
Пример ссылочной целостности: 1. child delete 2.child insert 3. child update 4.parent delete 5. parent insert 6. parent update

Пример построения инфологической схемы БД

Задача:

Описать инфологическую схему фрагмента БД процессингового центра в нотации Чена. См. диаграмму DFD детализированный процесс 1.2

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

Примечание:

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

2) Отсутствие звездочки в обозначении связи означает, что ключ родительской сущности (1) добавляется не к ключевым атрибутам (м). Это следует делать, если ключевые атрибуты дочерней сущности в совокупности являются уникальными.

3) Не идентифицирующая связь является предпочтительной, так как позволяет минимизировать число атрибутов в ключе дочерней сущности.

Лекция 5

Действия (1) и (2) обеспечивают возможность связи сущностей по общим атрибутам, также обеспечивают возможность объединения сущностей без потерь. Указанные средства часто выполняются автоматически.

Атрибуты сущностей БД.

Платежная система

# Ключ платежной системы

Наименование

Лимит наличных

Банк	# Ключ Банка БИК Наименование Адрес к/с в РКЦ № Лицензии

Банкомат

# Ключ Банкомата

Ключ банка v

№ Банкомата

Лимит Банкомата

Текущее число банкнот

Бок	# Ключ БОК Ключ платёжной системы v Ключ Банка v Ключ Банкомата v

Журнал транзакций

# Номер операции

# Дата

# Ключ банкомата v

Номер пластиковой карты

Банк иметент

Сумма

Схема проводки

# Номер проводки транзакции

# Ключ Бок

Ключ банка(дебет) v

Признак счёта дебет (0-лора, 1-Ностра, 2 –карт – счёт)

Ключ банка(кредит) v

Признак счёта кредит (0-лора, 1-Ностра, 2 –карт – счёт)

Формула расчёта суммы

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

# - Ключевые атрибуты

v – атрибуты наследованные от родительских сущностей

Пример формирования платёжного документа в расчётный банк по атрибутам «Схема проводки».

Пусть записи «Схема проводки» имеют следующий вид:

· Номер проводки

· Ключ БОК

· Ключ Сбербанка

· 2 – карт-счёт

· ключ Банка Москвы

· 2 – счёт по обслуживанию банкомата

· 102 – 100% сумма + 2% комиссия

Предположим, пользователь карточки сбербанка запросил в банкомате Банка Москвы сумму равную 1000, тогда процессинговый центр на основании описания записи сформирует следующий платежный документ, который будет передан в расчётный банк.

ДЕБЕТ: Бик сбербанка

Номер пластиковой карты

КРЕДИТ: Бик Банка Москвы

Номер банкомата

СУММА: 1020руб.

Отличия нотации Чена от ErWin

Нотация Чена

ErWin

1. Обозначение сущности

2. Обозначение связи

а)Идентифицирующая

б) неидентифицирующая

в)М:М

Logical

Phisical

3) Категоризация сущностей

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

Агрегация – это объединение реквизитов в отдельный экземпляр.

Реквизиты Код01 VISA Лимит 2000

Агрегат

Обобщение – это объединение агрегатов в сущность.

Агрегат

Сущность

Ассоциация – это связь между сущностями

Лабораторная работа №2

1. Разработать с помощью ErWin Logical(инфологическую) схему БД процессингового центра.

2. Разработать physical (даталогичекскую) схему БД для oracle 8i/

3. Сгенерировать DDL сценарий с описанием объектов БД

Отчёт

Рисунки со схемами и их краткое описание и последовательность разработки. В приложении DDL – сценарий.

Лекция 6

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

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

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

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

2. Визуальные языки описания (flow - форм).

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

Программу любой сложности можно описать с помощью трёх конструкций:

1. Последовательность конструкций.

конструкция

…

конструкция

2. Конструкция выбора.

ЕСЛИ условие, ТО

конструкция

ИНАЧЕ

конструкция

КОНЕЦ ЕСЛИ

3. Конструкция итерации.

ДЛЯ условие

конструкция

КОНЕЦ ДЛЯ

Здесь Конструкция – это либо элемент ВЫПОЛНИТЬ действие,

либо одна из вышеперечисленных конструкций 1-3.

Часто слово ВЫПОЛНИТЬ опускают.

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

Задача: Описать спецификации процесса «проверка разрешения» (процесс 1.1.2 на диаграмме потоков данных «Банкомат»).

Описание спецификации:

@ ВХОД Разрешение ПЦ-Б

@ ВЫХОД Признак разрешения для банкомата

(0 – есть разрешение, 1 – нет, 2 – ожидание разрешения от ПЦ)

@ СПЕЦ. ПРОЦ. Проверка разрешения ПЦ-Б

ЕСЛИ Разрешение ПЦ-Б = true, ТО

выйти(0)

ИНАЧЕ выдать сообщение об ошибке

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

проверить счётчик_1 на max,

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

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

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

«повторить функцию предварительной проверки карты и состояния запроса в ПЦ» (1.1.2),

выйти(2)

ИНАЧЕ

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

проверить счётчик_2 на max,

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

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

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

«повторить функцию предварительной проверки карты и состояния запроса в ПЦ» (1.1.2),

выйти(2)

ИНАЧЕ

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

КОНЕЦ ЕСЛИ

1. SELECT по которому заполняется таблица;

2. Требования к клавишам;

3. Требования к редактированию полей

Нажатие клавиши Ввод

…

Нажатие клавиши Выйти

…

Визуальные языки проектирования спецификаций (flow - форм)

Элементы языка flow-форм:

конструкция

…

конструкция

ЕСЛИ

условие

ТО

конструкция

ИНАЧЕ

конструкция

ДЛЯ

условие

конструкция

Здесь Конструкция – это либо элемент ВЫПОЛНИТЬ действие,

либо одна из вышеперечисленных конструкций 1-3

с учётом графического изображения.

Часто слово ВЫПОЛНИТЬ опускают.

Пример использования flow – форм.

Задача: см. предыдущий пример. В виде flow – форм.

Описание спецификации:

ЕСЛИ

Разрешение ПЦ-Б = true

ТО

выйти(0)

ИНАЧЕ

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

ЕСЛИ

ошибка в пароле

ТО

проверить счётчик_1 на max,

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

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

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

«повторить функцию предварительной проверки карты и состояния запроса в ПЦ» (1.1.2),

выйти(2)

ИНАЧЕ

ЕСЛИ

ошибка в сумме

ТО

проверить счётчик_2 на max,

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

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

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

«повторить функцию предварительной проверки карты и состояния запроса в ПЦ» (1.1.2),

выйти(2)

ИНАЧЕ

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

выход(1)

Организация проектирования систем с помощью пакета Designer 2000/6i

Процесс проектирования включает следующее шаги:

1. Разработка контекстной диаграммы потоков данных Process Modeler

Наглядное описание поведения системы

С каждым процессом или потоком данных можно связать объект мультимедиа (например микрофильм).

2. Разработка диаграммы Сущность-Связь (диаграмма Бахмена)

3. Разработка диаграмм потоков данных (DFD) и диаграмм Function Hierarchy Diagram (FHD).

Function Hierarchy Diagram (FHD) автоматически генерируется на основе контекстных диаграмм потоков данных и диаграмм, разработанных на шаге 3. FDH используется для описания будущих меню системы.

Пример FHD

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

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

Шаги:

1. Генерация даталогической схемы БД.

Data Diagrams. Уточнение характеристик таблиц, индексов…

2. Генерация модуля.

Module Diagrams. Схема генерации модулей:

Модулю соответствует 1 DFD. Система выделяет хранилище, привязки, атрибуты в потоках данных и генерирует форму.

Процесс DFD (процесс 1)

Module Logic Navigator генерирует скрипты, обрабатывающие те или иные события.

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

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

На основании спецификации программы разрабатываются коды в выбранной оболочке программирования.

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

Решаются задачи:

1. Выполняется оптимизация схемы БД.

2. Уточняются характеристики таблиц и атрибутов (имена, типы полей, индексы).

3. С помощью CASE-средств выполняется генерация схемы БД (DDL-сценарий).

Оптимизация схемы БД

Основная задача – разработать алгоритм «хорошей» БД.

Основы реляционной алгебры

1. Определение схемы отношений

Схема отношения – поименованное множество атрибутов.

R = (A₁, … A_n)

A_i = (i =1,n)

Пример:

R = (имя₁, адрес, товар, цена) = (A₁, A_2, A_3, A₄)

имя – id поставщика;

адрес – адрес поставщика;

товар – наименование поставляемого товара;

цена – цена за единицу поставляемого товара;

(имя, товар) – ключ схемы отношения.

Степень схемы отношения – количество атрибутов в схеме.

Лекция 7

Отношение (экземпляр отношений) – конкретная таблица с заданной схемой отношения.

Отношения будем обозначать строчными буквами.

Схему отношения будем обозначать заглавными буквами.

Пример

имя	адрес	товар	цена
АО «х»	г. Москва, ул. у, д. z	сахар	25
АО «х1»	г. Москва, ул. у1, д. z 1	карамель	30

Схема отношения

отношения

Кортеж – строка отношения.

Определение схемы БД

Пусть А – множество всех атрибутов предметной области (универсальная схема отношения).

R1, … , Rn – схемы отношения такие, что .

В этом случае говорят, что r = (R1, … , Rn) – схема БД.

Пример

А = (имя, адрес, товар, цена)

R1 = (имя, адрес)

R2 = (имя, товар, цена)

R1 È R2 = А

Следовательно, r = (R1, R2) – схема БД.

Основная задача последующего изложения – построение «хорошей» схемы БД.

Пример «плохой» схемы БД

Предположим задана универсальная схема отношения.

А = (имя, адрес, товар, цена)

R1 = А

Поэтому r = (R1) – схема БД.

Она обладает следующими недостатками:

1. избыточность

Адрес поставщика повторяется для каждого поставляемого им товара.

2. потенциальная противоречивость

При изменении адреса поставщика его необходимо изменить во всех строках отношения, куда он входит.

3. аномалия включения записи

Для данной схемы отношения R1 пара атрибутов (имя, товар) – ключ.

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

4. аномалия удаления

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

Первопричина этих недостатков состоит в том, что схема отношения не находится в 3-ей нормальной форме. Это одно из свойств «хорошей» схемы БД.

Пример «хорошей» схемы БД

А = (имя, адрес, товар, цена)

R1 = (имя, адрес)

R2 = (имя, товар, цена)

r = R1 È R2

В этом случае схема БД r не обладает вышеуказанными недостатками. Это означает, что R1 и R2 находятся в 3-ей нормальной форме.

Основные операции реляционной алгебры

1. Объединение 2-х отношений

r3 = r1 È r2 – отношение, каждый кортеж которого принадлежит либо отношению r1, либо r2.

A1	A2
1	2
3	4

r1 =

A1	A2
5	6
1	2

r2 =

A1	A2
1	2
3	4
5	6

r3 =

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

r1 и r2 должны обладать одинаковыми схемами отношения.

2. Разность отношений

r3 = r1 - r2 – отношение, каждый кортеж которого принадлежит отношению r1, но не принадлежит r2.

r1, r2 – см. выше

A1	A2
3	4

r3 =

3. Пересечение отношений

r3 = r1 Ç r2 – отношение, каждый экземпляр которого принадлежит и отношению r1, и отношению r2.

r1, r2 – см. выше

A1	A2
1	2

r3 =

4. Декартово произведение

Пусть R и S – две схемы отношения со степенями k1 и k2 (степень – число атрибутов в схеме отношения).

r, s – соответствующие экземпляры отношений.

Тогда t = r ´ s – декартово произведение, т.е. отношение со степенью k1 + k2, каждый кортеж которого получается путем конкатенации кортежей из r и s.

Порядок кортежей в отношениях r и s неважно.

A1	A2
1	2
3	4

r =

A1	A3
5	6
7	8

s =

R.A1	R.A2	S.A1	S.A3
1	2	5	6
1	2	7	8
3	4	5	6
3	4	7	8

t = r ´ s =

5. Проекция отношений на некоторое подмножество атрибутов

- отношение, каждый кортеж которого состоит из значений атрибутов A₁..A_kкортежа из r.

A₁	A₂	A₃	A₄
1	2	3	4
7	8	9	10
3	4	5	6
3	4	7	6

r =

A₁	A₂
1	4
7	10
3	6

6. Селекция

-отношение, каждый кортеж которого принадлежит r и удовлетворяет условию F.

A₁	A₂
1	2
9	8
3	3

r =

A₁	A₂
1	2
3	3

7. Естественное соединение

, r и s – экземпляры отношений со схемами R и S.

Определение следует из правил его построения:

1) построить декартово произведение ;

2) из декартова произведения выбрать кортежи, удовлетворяющие условию:

- атрибуты, общие в схемах отношений R и S.

3) удалить дублирующиеся столбцы и получим требуемое отношение t.

A₁	A₂	A₃
1	2	3
4	6	7

r =

A₁	A₂	A₄
1	2	7
8	9	10

s =

Построить соединение


1	2	3	1	2	7	√
1	2	3	8	9	10
4	6	7	1	2	7
4	6	7	8	9	10

1) =

A₁	A₂	A₃	A₄
1	2	3	7

3) t =

Теория нормализаций схем отношений

1) Функциональная зависимость

Пусть R определение функциональной зависимости. - универсальная схема отношений, т.е. схема состоит из всех атрибутов предметной области.

X и Y – некое подмножество этой схемы;

X →Y (Х функционально определяет Y), если в любом экземпляре r не существует двух кортежей, совпадающих по атрибутам Х и не совпадают по атрибутам Y.

Пример

Задана универсальная схема отношений:

R=(имя, адрес, товар, цена)= (А₁, А₂, А₃, А₄)

и функциональные зависимости:

А₁→ А_2,А₁ А₃→ А₄

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

A₁	A₂	A₃	A₄
АО «Х»	г. Москва, ул. y, д. z	Сахар	25
АО «Х»	г. Москва, ул. y, д. z	Карамель	30
АО «Х»	г. Москва, ул. y, д. z	Пастила	40

r =

А₁ А₃→ А₄имеет место, так как нет кортежей, которые совпадали бы по этой паре атрибутов (по X и Y).

2) Замыкание множества функциональных зависимостей

Пусть R – универсальная схема отношения;

F – заданное множество функциональных зависимостей на этой схеме.

Замыканием F назовем множество функциональных зависимостей, которые логически следуют из F.

Функциональная зависимость логически следует из F, если её можно получить с помощью аксиом Армстронга. Обозначается F⁺.

Аксиомы Армстронга (правила вывода)

1) Аксиомы рефлексивности

Если , то X →Y

2) Аксиома пополнения

Пусть X →Y, (Z может быть Ø)

Тогда (XZ →YZ)

3) Аксиома транзитивности

Если X →Y, Y→Z, то X →Z

Лекция 8

Пример построения замыкания.

(А,В,С)

F=(АàB, BàС)

F⁺-?

1) Построение тривиальных функциональных зависимостей:

AàA, BàB, CàC, ABàA, ABàB, ACàA, ACàC, BCàC, BCàB, ABCàA, ABCàC, ABCàB, ABCàAC, ABCàAB, ABCàBC, ABCàABC, ABàAB, ACàAC, BCàBC

2) Используем вторую аксиому Армстронга

AàAB

АСàBC

BàBC

ABàAC

ACàABC

ABàABC

3) Используем третью аксиому Армстронга

Т.к. АàB, BàС, то AàC

Аналогично, ABàBC, AàAC, AàABC

Лемма

Справедливы следующие правила:

1) Правило объединения

Если множество атрибутов Х определяет множество атрибутов У (XàY) и XàZ, то XàYZ

2) Правило декомпозиции:

Если XàY, ZÍY, то XàZ

3) Правило псевдотранзитивности:

Если XàY, WYàZ,то WXàZ

Доказательство:

1. XàХY (пополняем атрибутом Х первую зависимость)

XYàYZ (пополняем атрибутом Y вторую зависимость)

По третьей аксиоме Армстронга получаем XàYZ

2. Т.к. XàY, ZÍY, то по первой аксиоме Армстронга YàZ. Тогда по 3 аксиоме получаем: XàZ

3. WXàWY (пополняем атрибутом W первую зависимость)

WYàZ (по условию). Тогда по 3 аксиоме получаем: WXàZ

Теорема

Аксиомы Армстронга являются надежными и полными.

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

Полнота: если имеет место функциональная зависимость XàY, то она обязательно может быть выведена с помощью аксиом Армстронга.

Количество функциональных зависимостей, входящих в замыкание F⁺, может быть очень велико, даже если число исходных функциональных зависимостей незначительно.

Пример

F={XàA₁…. XàA_n}

Из правила объединения следует, что справедлива функциональная зависимость XàY, где Y- произвольное подмножество множества (A_1…. A_n). Таких комбинаций может быть 2ⁿ.

Поэтому в теории нормализации схем отношений напрямую замыкание F⁺не строится, но есть подход, позволяющий определить, принадлежит ли функциональная зависимость XàY замыканию F⁺. Этот подход основывается на понятии замыкания множества атрибутов.

Замыкание множества атрибутов.

Пусть R- универсальная схема отношений. Замыканием множества атрибутов Х, принадлежащего R (XÍR), называется множество атрибутов A_i_1…. A_ik, таких, что справедливо следующее выражение:

(XàA_i₁…. XàA_ik) ÍF⁺.

Замыкание множества атрибутов обозначается через Х⁺.

Правило

Чтобы проверить, принадлежит ли функциональная зависимость XàY замыканию F⁺ (XàY ÍF⁺), сначала строят Х⁺и если Y Í Х⁺, то значит XàY Í F⁺.

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

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

Это итерационная процедура, включающая следующие шаги:

i:=0, X₀⁺=X – замыкание множества атрибутов на i-ом шаге.
Положить X⁺_i+1:= X⁺_iÈV, где V – множеств атрибутов такое, что в F имеется функциональная зависимость Y→Z, для которых YÍ X⁺_i , а VÍZ.
X⁺_i+1= X⁺_i– это есть X⁺:= X⁺_i, иначе i:=i+1 и перейти к шагу 2.

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

R=(A,B,C,D,E,G),

F=(AB→C, C→A, BC→D. ACD→B, D→EG, BE→C, CG→BD, CE→AG)

X=BD, X⁺ - ?

X₀⁺≔BD
и 3. Оформим в виде таблицы:

i	Y→Z, для которых YÍ X⁺_i	VÍZ	X⁺_i+1≔ X⁺_iÈV
0	D→EG	EG	EGBD X⁺₁
1	BE→C	C	EGBDC X⁺₂
2	C→A, BC→D, CG→BD, CE→AG	A	EGBDCA X⁺₃
3	AB→C, ACD→B		EGBDCA X⁺₄

Т.о. (BD)⁺ = EGBDCA ^*Þ

(BD→E, BD→G, BD→B, BD→C, BD→D, BD→A) Ì F^+
**

* и ** эквивалентны.

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

Определение покрытия. Пусть F и G - множества функциональных зависимостей. G называют покрытием F, если их замыкания совпадают. G⁺= F⁺

Определение минимального покрытия. Покрытие G называется минимальным, если оно содержит:

a) минимальное число функциональных зависимостей

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

Алгоритм построение минимального покрытия G для множества функциональных зависимостей F.

1) Кажду функциональную зависимость из F заменить на совокупность функциональных зависимостей, каждая из которых содержит 1 атрибут в правой части. Полученное множество функциональных зависимостей обозначим через G.

2) Для каждой функциональной зависимости (X→A)ÎG выполнить следующие дествия:

a. Проверить, принадлежит ли данная функциональная зависимость (G-X→A)⁺ и если да, то исключить её из G (т.к. её можно вывести из меньшего числа функциональных зависимостей).

Примечание. Чтобы выполнить эту проверку, необходимо построить замыкание множества атрибутов на множестве функциональных зависимостей (G-X→A) и если AÎ(G-X→A)⁺ и проверить, принадлежит ли A…

b. Для каждого собственного подмножества Z<X проверить Z→AÎG⁺ , и если да, то заменитьт зависимость X→A на Z→A (с меньшим числом атрибутов), повторить п.2b, где вместо X→A выступает Z→A.

Примечение. Чтобы проверить, принадлежит ли Z→AÎG⁺, необходимо построить Z⁺ для множества функциональных зависимостей G и проверить AÎG⁺ , и если да, что по определению Z→AÎG⁺

3) Зависимости в G с одинаковой левой частью объединить в 1 функциональную зависимость (см. правило объединения доказанных выше лемм).

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

Пример построения минимального покрытия.

Пусть задана универсальная схема отношений R=(A,B,C,D)

F=AB→CD, BC→A, BC→D, C→D.

Построить минимальное покрытие G от F.

1) Заменить каждую функциональную зависимость (правило декомпозиции) G=(AB→D, AB→C, BC→A, BC→D, C→D).

AB→D, G-AB→D=(AB→C, BC→A, BC→D, C→D)

(AB)⁺=ABCD (D принадлежит замыканию Þ AB→DÎ(G-AB→D)⁺Þ эту зависимость можно исключить, она может быть выведена из меньшего числа).

G=(AB→C, BC→A, BC→D, C→D).

2) AB→C, G-AB→C=(BC→A, BC→D, C→D). Можем ли вывести эту зависимость из меньшего числа.

(AB)⁺=AB, AB→CÏ(G-AB→C)⁺

3) BC→A, G-BC→A= (AB→C, BC→D, C→D)

(BC)⁺=BCD – A не вошло Þ BC→A нельзя вывести Þ BC→AÏ(G-BC→A)⁺

4) BC→D, G-BC→D=(AB→C, BC→D, C→D).

(BC)⁺= BCAD Þ BC→DÎ(G-BC→D)⁺, т.е. мы эту зависимость можем исключить. G= (AB→C, BC→A, C→D).

5) Рассмотрим C→D. Можно ли эту зависимость вывести из меньшего числа.

C→D, G-C→D=(AB→D, BC→A). C⁺=C ÞC→DÏ(G-C→D)⁺.

1) G=(AB→C, BC→A, C→D)^*

AB→C

a. A→C, A⁺=A ÞA→CÏG⁺

b. B→C, B⁺=B Þ B→C ÏG⁺

2) BC→A. Таким же образом можно убедиться, что

B→AÏG⁺

C→AÏG⁺

Таким образом, * - минимальное покрытие и рассмотренный алгоритм – основа построения хорошей схемы БД.

Лекция 9

Свойства «хорошей» схемы БД

Схема БД называется «хорошей», если она обладает следующими свойствами:

1. Свойством соединения без потерь.

2. Свойством сохранения зависимости.

3. Свойством нормализации схем отношений схемы БД.

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

Свойство соединения без потерь

Определение свойства соединения без потерь

Пусть – схема БД (т.е. , где A – универсальная схема отношения). Схема БД обладает свойством соединения без потерь, если для любого экземпляра отношения r универсальной схемы отношений A выполняется следующее равенство:

где – проекция отношения r на множество атрибутов R_i (определение проекции дано в предыдущей лекции), – операция естественного соединения.

Пример схемы БД, не обладающей свойством соединения без потерь.

Пусть – универсальная схема отношения, – схема БД, а – функциональная зависимость.

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

Пусть ,

тогда

; ;

Пример схемы БД, обладающей свойством соединения без потерь.

Пусть – универсальная схема отношения, – схема БД, а – функциональная зависимость.

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

;

; ;

Теорема: пусть – схема БД, а F – множество функциональных зависимостей на универсальной схеме отношения.

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

1) ;

2) .

(Теорема без доказательства.)

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

;

(), т.к. из F (по условию).

Следствие из теоремы: пусть R₁ и R₂ – две сущности инфологической схемы БД, которые связаны между собой.

Схема БД обладает свойством соединения без потерь, если общие атрибуты R₁ и R₂ содержат ключ одной из этих сущностей.

Пример:

Обладает ли свойством соединения без потерь?

Воспользуемся теоремой:

;

, т.к. имеет место (т.к. A – ключ R₁).

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

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

Свойство сохранения зависимости

Определение проекции множества функциональных зависимостей F на схему отношения R_i.

Пусть – схема БД, F – исходное множество функциональных зависимостей.

Проекцией F на R_i называется множество функциональных зависимостей таких, что имеет место следующее включение: .

Проекция F на R_i обозначается: .

Определение свойства сохранения зависимости

Схема БД ρ обладает свойством сохранения зависимости, если справедливо следующее равенство:

Данное выражение читается следующим образом:

1) Берется .

2) Полученные функциональные зависимости объединяются.

3) Для этих зависимостей строится замыкание (применяются аксиомы Армстронга).

4) Полученное множество функциональных зависимостей сравнивается с F⁺.

Пример схемы БД, не обладающей свойством сохранения зависимости.

Пусть – универсальная схема отношения, – схема БД, а – функциональная зависимость.

Доказать, что ρ не обладает свойством сохранения зависимости.

;

Найдем такую функциональную зависимость, которая принадлежит F⁺, но не принадлежит левой части выражения в определении свойства сохранения зависимости. И тем самым докажем, что ρ не обладает свойством соединения без потерь.

В качестве такой зависимости имеем:

(по определению). (**)

. (*)

Для доказательства последнего утверждения требуется построить на объединенном множестве функциональных зависимостей и проверить ?

, но .

Это доказывает утверждение (*).

(*) и (**) доказывают утверждение задачи (что ρ не обладает свойством сохранения зависимости), т.е. .

Пример схемы БД, обладающей свойством сохранения зависимости.

Пусть – универсальная схема отношения, – схема БД, а – функциональная зависимость.

Доказать, что ρ обладает свойством сохранения зависимости.

– все зависимости, полученные из F с помощью аксиом Армстронга.

Т.о. равенство доказано и данная схема БД обладает свойством сохранения зависимости.

Свойство нормализации схем отношений

Определение ключа

Пусть – некоторая схема отношения, F – множество функциональных зависимостей на этой схеме.

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

1) .

2) .

Т.е. ключ содержит в себе минимальное число атрибутов, обладающих свойством 1.

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

Лекция 10

Алгоритм построения ключа (основывается на определении ключа)

1. , – ключ на 0 шаге.

2. ДЛЯ по числу атрибутов в ,

ЕСЛИ , то , , , выйти из цикла

КОНЕЦ ДЛЯ

3. ЕСЛИ – возросло, то перейти к п. 2 алгоритма

ИНАЧЕ – ключ схемы отношения .

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

Определение 1.

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

Определение 2.

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

Пример построения ключа

Дано:

– универсальная схема отношения;

– функциональные зависимости.

Задача:

Х – ключ R?

Решение:

1. ,

2. , , ,

3. – возросло

, , ,

3. – возросло

3. – не возросло, – ключ.

Примечание:

В данном варианте – это не единственный ключ (AB – тоже ключ). Всё зависит от последовательности просмотра атрибутов.

– тоже ключ;

ABC – первичные атрибуты;

D – не первичный атрибут.

Определение 3НФ (3-я нормальная форма).

Схема отношения R находится в 3НФ, если не существует ключа X, множества , и не первичного атрибута H () для которых выполнялись бы следующие условия:

Примечание: Из определения следует, что если можно подобрать X, Y и H для которых выполняются условия 1–3, то схема отношения не находится в 3НФ.

Пример доказательства, что схема отношения не находится в 3НФ

Дано:

Используя определение 3НФ доказать, что схема отношения не находится в 3НФ.

– универсальная схема отношения;

– функциональные зависимости.

Задача:

Доказать что R не находится в 3НФ.

Решение:

Определим ключ.

1. ,

, , ,

3. – возросло

, , ,

3. – возросло

3. – не возросло, – ключ схемы отношения.

Примечание: Можно показать, что он единственный.

Выбираем X, Y, H.

– не первичный атрибут.

Проверяем условия 1–3, которые указаны в определении 3НФ.

1. , так как (первая аксиома рефлексивности Армстронга);

2. , так как (по условию задачи);

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

, поэтому .

Таким образом удалось построить тройку X, Y, H, для которой выполнялись бы условия 1–3 из определения 3НФ.

Поэтому R не находится в 3НФ и обладает всеми аномалиями.

Пример доказательства, что схема отношения находится в 3НФ

Дано:

Используя определение 3НФ доказать, что схема отношения находится в 3НФ.

– универсальная схема отношения;

– функциональные зависимости;

– схема БД.

Задача:

Доказать что R₁, R₂ находятся в 3НФ.

Решение:

а) – ключ, так как по условию задачи;

б) подберём Y для которого ,

();

в) Здесь нельзя подобрать не первичный атрибут H, который (единственный не первичный атрибут – B, но ).

Мы не сумели подобрать X, Y, H для которых были бы справедливы условия 1–3 из определения 3НФ, следовательно, по определению, R₁ находится в 3НФ.

1) – ключ

2) найдём Y для которого ,

Легко можно убедиться, что таким условиями удовлетворяют следующие Y-ки:

а) A

б) C

в) D

г) AD

д) CD

3) Попытаемся подобрать не первичный атрибут H, для которого , .

Единственным претендентом является D, так как AC – ключ, D – не первичный.

а) , но , потому что , , (D не входит в AB)

б) , но , потому что , ,

в-д) не проходят, так как здесь не первичный атрибут (D) .

Методом логических исключений мы пришли к выводу, что здесь нельзя подобрать X, Y, H для которых были бы справедливы условия 1–3 из определения 3НФ, следовательно, по определению, R₁ находится в 3НФ.

Поэтому вывод – R₂ находится в 3НФ.

Алгоритм построения «хорошей» схемы БД

Дано:

– универсальная схема отношения;

F – исходное множество функциональных зависимостей на R.

Задача:

Построить «хорошую» схему БД. – ?

Решение:

Определить минимальное покрытие G для функциональных зависимостей F (см. предыдущие лекции).
Каждую функциональную зависимость V вида из G заменить на VW (объединить атрибуты левой и правой частей). Получившееся множество схем отношений обозначить Q.
Если , то добавить в схему отношения и выйти из алгоритма, ( – «хорошая» схема БД).

Иначе перейти к пункту 5.

Добавить в в качестве схем отношений все те одиночные атрибуты, которые не вошли ни в одну из схем из Q.
Добавить в все схемы отношений из Q.

Примечание: после выполнения пунктов алгоритма 1-6 схема БД обладает Свойством Сохранения Зависимостей, и каждая её схема отношения находится в 3НФ.

Если ни одна из схем отношений в не содержит в себе ключ для универсальной схемы отношения R, то добавить в какой-нибудь ключ для R в качестве схемы отношения.

Примечание: после выполнения всех 7 пунктов алгоритма схема БД обладает всеми свойствами «хорошей» схемы БД:

1) Свойство Соединения Без Потерь;

2) Свойство Сохранения Зависимостей;

3) Каждая схема отношения в находится в 3НФ.

7-е условие слишком жесткое (надо найти ключ для универсальной схемы отношения – а в ней бывают сотни атрибутов).

Примечание: 7-ой пункт предполагает, что, в принципе, при разработке таблиц в БД, будут соединены все таблицы из , но на практике такого не бывает, поэтому его можно ослабить:

7. Если в запросах к БД соединяет не все схемы отношений из , а только из подмножества , , …, , то в можно добавить ключи для Q₁, Q₂, …, Q_k в качестве новых схем отношений. (Если, конечно, эти ключи не содержатся уже ни в одной из схем отношения из ).

Лекция 11

Пример построения хорошей схемы БД

(в этом же стиле первая задача курсовой работы).

Пусть R=(имя, адрес, товар, цена)=(А,В,С,D)

F=(A→B, BC→D, AC→D, B→A)

Задача:

Построить хорошую схему БД – ρ.

Воспользуемся алгоритмом:

ρ=Ø
Воспользуемся алгоритмом построения минимального покрытия

G=(A→B, BC→D, AC→D, B→A)

2.2.1.1 A→B, G – A→B=(BC→D, AC→D, B→A)
(A)⁺=A, A→B(G – A→B)⁺

2.2.1.2 BC→D, G – BC→D=(A→B, AC→D, B→A)

(BC)⁺=BCAD è BC→D(G – BC→D)⁺ è Данную функциональную зависимость исключаем из G

G=(A→B, AC→D, B→A)

2.2.1.3 AC→D, G – AC→D=(A→B, B→A)

(AC)⁺=ACB è AC→D(G – AC→D)⁺

2.2.1.4 B→A, G – B→A=(A→B, AC→D)

(B)⁺=B, B→A(G – B→A)⁺ è

G=(A→B, AC→D, B→A)

2.2.2 В дальнейшем замыкания множества атрибутов рассматривается для G

2.2.2.1 AC→D

a) A→D

(A)⁺=AB, A→D(G)⁺ - (Если это верно, то можно заменить AC→D на A→D. Док-во:AC→A, A→D è AC→D, тогда AC→D можно заменить на A→D )

b) C→D

(C)⁺=C , C→D (G)⁺

G=(A→B, AC→D, B→A) – минимальное покрытие.

Q=(AB, ACD, BA) = (AB, ACD)
Нужно убедиться, что RQ. Так оно и есть: R = ABCD Q = (AB, ACD).
---
ρ = (AB, ACD).
Определим ключ для R

7.1. i:=0; x₀=BACD (изменение в последовательности символов связано с известным заранее результатом )

7.2. (ACD)⁺ = ACDB = R, x₁ = ACD, i++;

7.3. i==1;

7.2. (CD)⁺ = CD ≠ R

(AD)⁺ = ADB ≠ R

(AC)⁺ = ACBD = R, x₂=AC, i++;

7.3. i==2;

7.2. (C)⁺ = C ≠ R;

(A)⁺ = A ≠ R;

7.3. i==2;

x = x₂= AC – ключ R.

ACACD в ρ = (AB, ACD) è В ρ ничего не надо добавлять, и поэтому ρ = (AB, ACD) – хорошая схема БД.

Первое задание курсовой работы.

Дана универсальная схема отношений:

R =( A – читаемый курс, В – преподаватель, С – час начала занятия, D – аудитория, E – студент, T – оценка по курсу)

Задано множество физических зависимостей:

F = (CD→B – в аудитории одновременно может быть только один преподаватель,

AC→D – каждый курс одновременно может читаться только в одной аудитории,

CE→A – каждый студент одновременно может слушать только один курс,

A→B – каждый курс ведет только один преподаватель,

CD→A – в аудитории одновременно может читаться только один курс,

CB→D – преподаватель одновременно может находиться только в одной аудитории,

AE→T – по каждому курсу каждый студент имеет только одну оценку,

CE→D – студент в один момент времени может находиться только в одной аудитории.

)

Задача: Построить хорошую базу данных (ρ).

Примечание:

Приложение к пункту 7 не учитывать.

Преимущества и недостатки построения хорошей схемы БД.

Преимущества «+»

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

Недостатки «-»

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

Указанные недостатки сдерживают применение рассмотренного метода на практике.

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

Практические приемы нормализации схем отношения.

1) Приведение схемы отношения к первой нормальной форме.

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

2) Приведение схемы отношения ко второй нормальной форме.

Схема отношения находится во второй нормальной форме, если не существует ключа Х, множества атрибутов YX * и не первичного атрибута HY, для которых были бы справедливы следующие свойства.

· X→YF⁺

· Y→HF⁺

· Y→XF⁺

(Это определение очень напоминает определение третьей нормальной формы, отличие только в *)

X=A₁A₂

Y=A₁ X(A₁→A_i…A_j)

H – один из атрибутов A_i…A_j

Так как получилось подобрать X, Y, H è R₁ – не находится во второй нормальной форме.

3) Приведение схемы отношения к третьей нормальной форме.

X=A – ключ.

Y=A₂ R₁(A₂→A_i…A_j)

H=A_i…A_j

Так как подобрали X, Y, H è R₁≠ Третьей нормальной форме.

Лекция 12

X=A1A5 – схема отношений R1 (A5 – кат. вектор)

Y=A1(A1→A2A3A4)

H(A2,A3,A4)

A3→A4

Не в 1,2,3 НФ.

Задача нормализовать данную таблицу.

Каждая схема будет в 3НФ, если каждый сотрудник занимает 1 должность на предприятии. Если это не так, то в исходной таблицу R1 входит другая схема, состоящая из других атрибутов.

В этом случае схему БД необходимо преобразовать, т.к. R1 не находится в 1 НФ.

Оптимизации (“на пальцах”)

Без потерь – правильные SQL запросы
A→B аномалия отсутствие противоречивости, включения
потенциальной избыточности.

На этом мы завершим теорию “Марксизма и Ленинизма” (Дословно;-))

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

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

Различают следующие типы Индексов:

Хэш – индекс
B – индекс

Включения записи в БД

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

h(q)=i – номер хэш индекса

И в этот раздел (i) помещается запись (q,P), где это указатель на индекс БД.

q→h(q)=i→

Чтение i-ого раздела хэш-индекса→

Поиск записи (q, P) в i-ом разделе по ключу q→

Чтение блока из таблицы БД по указателю P→

Поиск в блоке требуемой записи.

Для того, чтобы прочитать требуемое №2 обращение к диску.

B – индексы.

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

Для первичного ключа. (Primary Key)
Для альтернативного ключа. (AK – другой уникальный ключ)
Для произвольного набора атрибутов. (IK – инвертированные списки)

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

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

Какие существуют

Различают следующие типы B- индексов.

Обычные B-индексы (B-деревья)
Битовые индексы (Bit Mappend)
Реверсивыне индексы (Reverse Key Index)
Индекс Таблицы (Индекс Таблицы)

Структура

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

<Значение индекс. Атрибута (mean) идентификатор записи табл. БД (rowid)>

При переполнении таблицы делятся пополам – B – деревья.

Если нужно ‘B’ →

читаю ‘A’ – 1 уровень. ≠Г
читаю, например, ‘Г’ дальше в 1 уровне ≠B и лексикографически это больше, чем ‘B’→
Возврящаюсь назад к ‘А’ и иду на 2 уровень
Читаю на II уровне ‘A’ ≠’B’
‘B’=’B’ → конец.

(q, rowid)

Значение инд. Атрибута

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

Если мест нет, то блок листового уровня расширяется на 2.

Ниняя часть старого блока переписывается в нижнюю часть нового блока и в блоке более верхнего уровня создается mean – указатель.

Предположим необходимо найти записи со значением индексного атрибута = q.

Раз просматриватся индекс, начиная с 1 уровня и на каждом уровне q<= mean из указателя читается информация следующего уровня, просматривается и т. д.

Когда будет считан блок листового уровня q=mean.

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

ROWID

00001<3aA идентификатор файла БД.

0007 – номер блока.

0002 – номер записи.

Данный пример указывает, что 0002, 0003 имеет значение индекс атрибута с А.

Определение числа уровней в обычном

Число уровней является переменным и определяется из того, что число блоков в индексе на 1 уровне всегда =1.

V – число записей в таблице БД.
К – маx число записей в 1-одном блоке индекса
L- число уровней в индексе

Все переполнены уровни, сколько уровней?

V/K – количество блоков листового уровня.
V/K - число блоков индекса на L-1 уровне.

V/K=1 – число блоков в индексе на 1 уровне.

L = logV

Преимущества и недостатки обычных B – деревьев

Преимущества:

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

Недостатки:

Достаточно большой объем внешней памяти, занимаемой индексом

Рассчитаем объем, занимаемый листовыми блоками обычного B-индекса.

V – число записей в таблице БД.
I – мощность индекс. атрибута (число различных значений)
L- длина индекс. атриб. В схеме таблицы
L- длина идентификатора записи (rowid)

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

Тогда объем этих блоков Q=V(L+ L)

Лекция 13

Недостатки обычных В-деревьев:

- большое время выполнения операций над списками с индексированными записями

Пример

Пусть условие поиска в БД имеет следующий вид:

q = ‘A’ AND s = ‘B’

	q		s

	A		B

Индексы строятся для атрибутов какой-либо 1 таблицы. Предположим, что атрибуты q и s индексированы. Поиск требуемых записей в индексе осуществляется следующим образом:

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

q=’A’ –

2) используя индекс для s система идентификаторы записей, у которых s=’B’.

s=’b’ – {rowid}_s=’_B’

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

{rowid}_q=’A’{rowid}_s=’B’

4) Используя полученные идентификаторы записи читаются из БД

При выполнении 3 пункта СУБД организует вложенные циклы для просмотра и определения пересечений списков. На это тратится достаточно много времени.

Примечание.

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

Битовые индексы

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

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

< значение индексируемого атрибута (mean), - их может быть несколько

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

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

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

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

‘A’	13	20	01100101
mean	start_rowid	end_rowid	bitmap_segment

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

В битовой маске каждый бит соответствует записи из указанного интервала. Битовая маска означает, что 14,15, 18 и 20 записи БД имеют значение атрибута q = ‘A’.

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

1) Битовый индекс занимает меньший объем памяти, чем обычное В-дерево.

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

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

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

Lr – длина идентификатора записи (rowid)

Lb – длина битового сегмента двоичной карты

Требуемый объем вычисляется по формуле:

, где = длина записи блока листового уровня битового индекса. Q << объема памяти блоков листового уровня для В-дерева.

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

Каждая запись листового уровня описывает примерно 8Lb записей в таблице БД.

2) Быстрое выполнение операций с сегментами двоичной карты

Задано то же условие поиска, оценим качественно время его выполнения

Предположим, что атрибуты q и s индексированы с помощью битовых индексов.

	q		s

	A		B

‘A’

bitmap_segment

‘B’

bitmap_segment

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

1) Выделяется bitmap_segment₁. (Индексы по s читаются в битовый сегмент bitmap_segment₁)

2) Выделяется bitmap_segment_{2 (}Индексы по s читаются в битовый сегмент bitmap_segment₂)

3) Определяется результирующий битовый сегмент двоичной карты

bitmap_segment₁ bitmap_segment_2
=bitmap_segment₃

4) Определяется список идентификаторов записей, удовлетворяющих условиям. На интервал (13, 20) накладывается заданная маска (13,20) {bitmap_segment}₃

При выполнении 3 операции выполняется логическое пересечение битовых массивов, это можно выполнить 1 ассемблерной командой (системе не требуется выполнять вложенных циклов)

Недостаток битовых индексов

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

Например, если обновляется только 14 запись, блокируются записи с 13 по 20.

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

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

< реверсивное значение индексируемого атрибута (mean),

идентификатор записи (rowid)>

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

приток ->	котирп	01
пример ->	ремирп	02

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

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

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

В данном примере нагрузка на сервер снижается в 2 раза.

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

По своей структуре индекс-таблицы являются В-деревьями, но в блоке листового уровня вместо идентификатора записи хранятся атрибуты этой записи.

код	остальные атрибуты записи

mean

Преимущество: из индекса читается сама запись (это сокращает врем доступа к данным)

Недостаток: резко осложняется процедура ведения индекса (индекс и БД едины)

После оптимизации схемы БД, после выбора индексируемых атрибутов, их характеристик выполняется генерация DDL сценария с помощью CASE-средств (ErWin, например). В этом сценарии в основном сохраняются операторы создания различных объектов (таблицы, хранимые процедуры и т.д.) После этого файл с DDL-сценарием прогоняется на сервере БД с помощью соответствующих утилит (например, в Oracle команда @ в утилите SQL+). В результате создаются требуемые объекты, к которым затем можно обращаться с помощью языка манипулирования данными (в основном SQL).

Специальная обработка текстовых полей (атрибутов) БД

Целью дальнейшего рассмотрения является следующее: показать, как с помощью ТФЯ можно строить небольшие трансляторы.

Лекция 14

Элементы теории формальных языков

Определения

Алфавит – непустое конечное множество символов.
Цепочка – конечная последовательность символов алфавита.
Конкатенация двух цепочек x и y - это цепочка z, которая получается путём приписывания в конец цепочки x символов цепочки y.
Произведение двух множеств цепочек x и y - это .
Степень алфавита А определяется следующим образом:

Здесь: Λ- пустой символ, А – сам алфавит, _ -произведение двух множеств цепочек (смотри п.4).
Усечённая итерация алфавита А определяется следующим образом:
Итерация алфавита А определяется следующим образом:
, где Λ –пустой символ.

Пример построения итерации алфавита А

Задание

А=(a,b) – алфавит

Определить А^*.

Решение

А^*= (Λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb…)

A¹ A² A³

Определение грамматики

Правило – выражение вида
::= u, где U – символ алфавита, u – цепочка символов алфавита.

::= читается как «есть по определению».

Грамматикой G(z) называется непустое конечное множество правил, где символ <z> должен встречаться в левой части, по крайней мере, одного из правил. Этот символ называется начальным символом.

Все символы, которые встречаются и в левой, и в правой частях грамматики, образуют словарь V.

Символы, которые встречаются в левых частях правил, называются нетерминальными. Их множество обозначается N.

Все остальные символы словаря, не входящие в N, называются терминальными. Их множество обозначается T.

Множество правил с одинаковой левой частью, например,

::=x

::=y

…

::=z

сокращенно записывают ::=x|y|…|z.

Читается «Символ U есть по определению либо x, либо y, либо …, либо z».

Пример грамматики

Задание

Написать грамматику натурального числа (0 не входит в множество натуральных чисел).

<Z>::=<чс> , здесь <чс> - нетерминальный символ «число» (1)

<чс>::=<цифра>|<чс>|<цифра1> (2)

<цифра>::=1|2|…|9 (3)

<цифра1>::=0|<цифра> (4)

N={<Z>, <чс>, <цифра>, <цифра1>}

T={0,1,…,9}

Язык, описываемый грамматикой

1. Пусть G(<z>) – грамматика. Говорят, что цепочка v непосредственно порождает цепочку w, если можно записать следующее равенство
v=xy, w=xuy, где ::=u, a x и y – некоторые цепочки (они могут быть пустыми).

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

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

Цепочка v			Цепочка w			№ правила
x	<U>	y	x	u	y	№ правила
	<z>			<чс>		1
	<чс>			<чс><цифра1>		2
	<чс>	<цифра1>		<цифра>	<цифра1>	2
	<цифра1>	<цифра1>		2	<цифра1>	3
2	<цифра1>			2	0	4

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

2. Вывод цепочки w из цепочки v.

Говорят, что цепочка v порождает цепочку w (w выводится из v), если существует следующая последовательность непосредственных выводов

Если v≠w, то (непосредственная выводимость)

Если v=w или , то вводят следующее обозначение

Общее правило вывода

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

Из предыдущего примера следует, что

3. Пусть G(z) - грамматика. Цепочка x называется сентенциональной формой, если она выводится из начального символа, то есть

4. Предложение языка – это сентенциональная форма, состоящая только из терминальных символов.

5. Язык – это множество предложений, то есть цепочек, выводимых из начального символа <z> и состоящих из терминальных символов.

где Т⁺- усеченная итерация множества терминальных символов.

Синтаксические деревья

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

Синтаксическое дерево строится только для вывода предложения.

На основе грамматики натуральных чисел можно построить следующий вывод.

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

Куст узла – родительский узел и множество подчинённых ему дочерних узлов.

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

Дочерним узлам куста соответствуют символы цепочки u, при этом должно существовать правило ::=u.

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

Концевые листовые узлы – узлы, не имеющие куста.

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

Нисходящие распознаватели

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

Левосторонняя и правосторонняя рекурсия

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

::=…|x|…

то есть в какой-либо альтернативе первый символ – это нетерминальный символ U, стоящий в левой части правил.

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

::=…| x |…

то есть в какой-либо альтернативе самый первый символ – это нетерминальный символ, стоящий в левой части правил.

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

Способы устранения левосторонней рекурсии

Продемонстрируем на примере грамматики арифметического выражения.

Она имеет вид:

<Z>::=<E>	(1)
<E>::=<T>\|<E>+<T>\|<E>-<T>	(2)
<T>::=<F>\|<T>*<F>\|<T>/<F>	(3)
<F>::=(<E>)\|i	(4)

Здесь i – либо константа, либо переменная со знаком или без.

В этой грамматике для простоты не учитывается возведение в степень. Здесь (2) и (3) правила имеют левостороннюю рекурсию.

Существует два способа избавления от левосторонней рекурсии.

1. Замена левосторонней рекурсии на правостороннюю.

Правила (2) и (3) можно переписать следующим образом.

<E>::=<T>\|<T>+<E>\|<T>-<E>	(2a)
<T>::=<F>\|<F>*<T>\|<F>/<T>	(3a)

Правила (2а) и (3а) эквивалентны правилам (2) и(3).

2. Замена нетерминальных символов в правой части правила на символы, обозначающие «хвост».

Правила (2) и (3) можно переписать следующим образом.

<E>::=<T>{+<T>; -<T>}	(2б)
<T>::=<F>{*<F>; /<F>}	(3б)

Например, правило (2б) читается следующим образом «Нетерминальный символ <E> есть по определению нетерминальный символ <T>, за которым возможен «хвост», состоящий из смеси цепочек +<T> и -<T>».

Фигурными скобками обозначается «хвост».

Правила (2б) и (3б) эквивалентны правилам (2) и (3).

Лекция 15

Общие правила (рекомендации) для разработки нисходящих распознавателей.

1. Во всех правилах грамматики избавиться от левосторонней рекурсии

( см. предыдущую лекцию)

2. Для каждого правила ::= u разработать программу, которая будет удовлетворять следующим требованиям:

А. Программа должна либо определить «u» (т .е. требуемые операции), либо сообщить о невозможности это сделать.

Б. Если при разборе «u» встречается нетерминальный символ <X> (u=…<X>…), то для анализа этого нетерминального символа <X> необходимо передать управление программе, связанной с правилом: <X>::=x.

В. При отрицательном ответе после анализа нетерминального символа <X> программа разбора цепочки «u» должна либо проанализировать альтернативный вариант(в цепочке «u» где-то встречается альтернатива u::= …<X>| альтернатива), либо выдать сообщение об ошибке.

Г. В начале управление должно быть передано программе :<Z>::=…, где <Z>- начальный символ.

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

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

Предположим задана грамматика арифметического выражения:

<Z>::=<E>
<E>::=<T> | <E> + <T> | <E> - <T>
<T>::=<F> | <T> * <F>| <T> / <F>
<F>::=(<E>) | i, где I либо const, либо идентификатор.

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

1) правила 2 и 3 имеют левостороннюю рекурсию => избавляемся от неё:

1. <Z>::=<E>

2.<E>::=<T> | { (+|-) <T>}

3.<T>::=<F> | {( *| /) <F>}

4.<F>::=(<E>) | i

2) каждому правилу поставим в соответствие функцию fi. Каждая из этих функций имеет следующий прототип:

int fi(char **u, double *d);

*u- указатель на текущий символ разбираемого арифметического выражения.

*d- текущее значение числа рассчитанное при вызове функции.

int – каждая функция возвращает код ошибки( 0- нет ошибки; 1- ошибка, прекратить вычисления)

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

1)char **u:

2)char *u:

Схема взаимодействия функций fi в соответствии со сформулированными правилами (рекомендациями).

Реализация функций f1, f2, f3, f4.

Для обработки ошибки будем использовать следующий макрос:

#define fun(a) if (a) return(1)

f1:

*u – указатель на начальный символ арифметического выражениях;

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

int f1 (char **u, double *d)

{

return(f2(u, d)); // реализация безусловного перехода 1

}

f2:

int f2(char **u, double *d)

{

double d1;

fun (f3(u, d)); // реализация безусловного перехода 2

while (1) // реализация «хвоста»

{

*u+=strspn(*u, “ “); // продвинуть указатель за пробел

switch (**u)

{

case’+’:

(*u)++; // перейти за «+»

fun (f3(u, &d1)); // обращение к f3 если встречается «+»

*d+=d1;

break;

case’-’:

(*u)++; // перейти за «-»

fun (f3(u, &d1)); // обращение к f3 если встречается «-»

*d-=d1;

break;

defalt: // больше нет символов хвоста

return(0);

}

f3:

int f3(char **u, double *d)

{

double d1;

fun (f3(u, d));

while (1)

{

*u+=strspn(*u, “ “);

switch (**u)

{

case’*’:

(*u)++;

fun (f4(u, &d1));

*d*=d1;

break;

case’/’:

(*u)++;

fun (f4(u, &d1));

*d/=d1;

break;

defalt:

return(0);

}

f4:

int f3(char **u, double *d)

{

*u+=strspn(*u, “ ”);

if (**u==’(’)

{

(*u)++;

fun (f2(u, d ));

*u+=strspn(*u,” “);

if (**u!=”)“)

return (1);

else

{

(*u)++;

return (0);

}

//Разбор альтернативы (вычисление i)

разбор I (const или идентификатор)

if ( ошибка)

return(1);

else

{

*d=число, полученное после разбора

return(0);

}

Синтаксическое дерево строится неявно. Дерево образует последовательность вызовов функций f1-f4.

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

25 + (A+B) / C*D

Лекция 16

Восходящие распознаватели

Восходящие распознаватели - это транслятор, которое строит синтаксическое дерево сверху- вниз.

Основа - дочерние узлы какого-либо куста синтаксического дерева.

Восходящие распознаватели выполняют следующую последовательность шагов:

1- Выполняют поиск основы Х

2- Выполняют поиск правила грамматики:

::= х;

3- Привязывают х к нетерминальному символу и таким образом строят куст

синтаксического дерева.

Алгоритм продолжается, начиная с пункта 1.

В дальнейшем восходящие распознаватели рассматривают на примере операторных грамматик.

Грамматика G(<Z>) называют операторной, если ни одно из ее правил не записано в следующем виде:

::= <V> <W>, то есть никакая правая часть любого правила не содержит двух соседних нетерминальных символов.

Примеры: грамматика арифметического выражения;

Условие поиска в операторе SELECT.

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

1- Отношения между операторами грамматики (операторы- терминальные символы, которые разделяют нетерминальные символы в правых частях правил команд).

2- Необходимо определить числовые функции предшествования f и g.

I. Рассмотрим отношения между операторами:

Можно выделить 3 типа отношений между операторами:

1- отношение: r◦<s: означает оператор r непосредственно предшествует оператору S но перед оператором r вначале надо вычислить S.

Пример:

а) для арифметических выражений:

+◦<* а+в*с (+ это r; * это s)

б) для логических выражений: Или ◦< и

OR ◦<AND A=3 OR B= 2 AND C<5

2- отношение: r◦>s Оператор r непосредственно предшествует S и перед определением S необходимо вычислить r.

Пример:

а) для арифметических выражений:

а + в - с (+ это r, - это s)

б) для логических выражений: OR ◦> OR

	r		s
A=3	OR	B =2	OR	C <3

3- отношение: r◦ = s Означает, что оператор r непосредственно предшествует S; r и S необходимо в дальнейшем исключить из рассмотрения:

а) (◦= ) для арифметического выражения

r		s
(	а	)

б) для логического (◦ =)

r		s
(	а	)

II. Определим функции предшествования:

Числовые функции f и g называются функциями предшествования, если они удовлетворяют условиям:

1- Отношение r◦<S эквивалентно f(r)<g(s)

2- Отношение r◦<s эквивалентно f(r) > g(s)

3- Если r◦=s эквивалентно f(r) = g(s)

Примеры отношений между операторами и функции предшествования для грамматики арифметического выражения

Пусть задана грамматика арифметического выражения:

1) <Z>::=<E>

2) <T> ::= <F> | <T> * <F> | <T>/<F>

<F>::= (<E>)i

Здесь не учитывается возведение в степень, i- константа или идентификатор. Здесь операторами являются +, -, *, /, ( ).

Определим отношения

s r	+	-	*	/	(	)	‘\0’
+	◦>	◦>	◦<	◦<	◦<	◦<	◦<
-	◦>	◦>	◦<	◦<	◦<	◦>	◦>
*	◦>	◦>	◦>	◦>	◦<	◦>	◦>
/	◦>	◦>	◦>	◦>	◦<	◦>	◦>
(	<◦	◦<	◦<	◦<	◦<	◦=	ошибка
)	◦>	◦>	◦>	◦>	ошибка )(	◦>	◦>

между операторами, сведем эти отношения в таблицу.

‘0’- конец строки

По концу строки должны выполняться операторы.

Функции предшествования

Функций предшествования для данной грамматики может быть очень много. Ниже приведен 1 пример для функций предшествования f и g.

	f	g
+	10	9
-	10	9
*	12	11
/	12	11
(	8	13
)	12	8
‘\0’		0

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

Например:

1) +◦<*

f(+)= 10 , g(*)=11

f(+) < g(*)

2) + ◦ > +

f(+) = 10, g(+)=9

f(+)=g(+)

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

1) Создать 2 стека: Stack1 для операторов, Stack2 для операндов.

Примерная структура Stack1:

s1	f(s1)	g(s1)	Адрес программы обработки оператора s1
…	…	…	…

2) Начать или продолжить разбор строки: s2- текущий символ предложения

3) Если s2 это операнд (число), то преобразовать его и поместить в Stack2 и перейти к пункту 2 алгоритма.

4) Здесь s2 это оператор и пусть s1 последний оператор в стеке Stack1.

Возможны варианты:

а) Если f(s1)<g(s2), то добавить s2 в Stack1 и перейти к пункту 2 алгоритма.

б) Если f(s1)>g(s2), то выполнить следующие действия:

I. вызвать программу обработки последнего оператора в Stack1, эта программа должна выполнять следующие действия:

- выполнить операцию s1

- сжать Stack1, то есть удалить оператор S1 из Stack1.

- сжать Stack2, то есть удалить 2 операнда, над которыми выполнялась операция S1 в Stack2

- поместить результат выполнения операции S1 в Stack2

II. Если s2 конец строки и стек Stack1 пуст, то завершить выполнение алгоритма, иначе к пункту 4 алгоритма.

в) Если f(s1)=g(s2), то удалить из стека Stack1 оператор s1 и перейти к пункту 2 алгоритма.

Пример изменения стеков Stack1 и Stack2 для арифметического выражения

1. Задано арифметическое выражение: А+В*С

	операторы	операнды
	Stack1	Stack2
1		А
2	+	А
3	+	В А
4	+ +	В А	s2=’*’ выполняется п.4а алгоритма
	* +	С В А
	+	С*В А	s2=’\0’ выполняется п.4б алгоритма (s1=’*’)
		А+С*В	s2=’\0’ выполняется п.4б алгоритма, вызывается функция (s1=’+’)

2 задача курсовой работы

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

На вход распознавателя передается строка с предложением грамматики. Использовать или структурированный язык или flow form.

Максимально 2 страницы.

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

Некоторые особенности языка SQL

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

1- Этот язык являтся языком описания и манипулирования данными.

2- Выступает как средство взаимодействия серверов в распределенных БД.

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

Существуют стандарты:

1. В начале SQL92 (SQL2)

2.Сейчас действует SQL99 (SQL3)

Он включает в себя стандарт SQL92 и расширения для объектных реляционных СУБД.

Лекция 17

Пример схемы БД, используемой для иллюстрации приложения на SQL

r=(S,P,J,SPJ)

S- ”Поставщик”;

- номер;

- ФИО поставщика;

- состояние его счета;

- город проживания и центральный офис

P- “Деталь”(описание поставляемой детали);

- номер детали(ключ атр.);

- название;

- цвет;

- вес(в фунтах);

- город(изготовления детали);

J- “Изделие”;

- номер_изделия(ключ атр.);

- название;

- город(изготовления);

SPJ- “Сборка”;

- номер_поставщика(поставляющий деталь, ключ атр.);

- номер детали(поставляемой поставщиком, ключ атр.);

- номер_изделия(в которое входит деталь, ключ атр.);

- количество(количество деталей в поставке);

Запись в таблицу SPJ.

ER диаграмма имеет вид:

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

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

В основном будем изучать язык манипулирования данными. Он имеет 4 оператора:

- Select- поиск и чтение записи из БД.

- Update – обновление существующих записей в БД.

- Insert – включение новых записей в таблицу БД.

- Delete – удаление записи из БД.

SQL относится к классу непроцедурных языков. То есть в операторах указано, что нужно сделать, но не как это сделать. Но часто этот непроцедурный язык используется в процедурных языках.

Возникает проблема импеданса- несоответствия модели языка SQL и модели проц. языков. Эта проблема решается с помощью курсоров.

Существует 3 варианта применения SQL в процедурных языках:

1) API-интерфейс (применяется специальная функция, в качестве аргумента указывается строка с SQL- предложением)

2) SQL- операторы встраиваются в проц. языки(PRO*C= C+SQL; SQLy=java+SQL)

3) Как обычные операторы процедурного языка, но возвращающие множество записей образованных с помощью курсора.(PL/SQL(Oracle))

Оператор SELECT.

Упрощенный синтаксис:

SELECT[DISTINCT] атрибут(ы)

FROM таблица(ы)

[WHERE условие]

[GROUP BY атрибут(ы)[HAVING условие 1]]

[ORDER BY атрибут(ы)];

Оператор SELECT моделирует выполнение операции реляционной алгебры ( селеция, проекция, декартово произведение и т. д.) В результате выполнения этого оператора строим новую таблицу, содержащую выбранные записи.

Порядок выполнения:

На логическом уровне.

1) Из исходной таблицы, указываемой за ключевым словом FROM, выбираются записи удовлетворяющие условию, указанному за ключевым словом WHERE.(Это операция селекции).

2) Из выбранных на 1-м шаге записей выделяются атрибуты, которые перечислены за ключевым словом SELECT.

Это операция проекции

Если больше ничего не указано, то это и будет результат выполнения оператора SELECT.

3) Если в предложении указано ключевое слово GROUP BY, то записи, полученные на 2-м шаге, группируются по атрибутам, указанным за этим ключевым словом. В группу входят записи с одинаковыми значениями для этих атрибутов. Для каждой группы проверяется условие 1, указанное за ключевым словом HAVING. Далее рассматриваются группы, удовлетворяющие этому условию. В результирующую таблицу помещается одна запись из каждой группы.

4) Если в предложении SELECT есть ключевое слово ORDER BY, то результирующая таблица упорядочивается по атрибутам, указанным за ORDER BY.

Варианты использования SELECT:

Запросы, не использующие соединение таблиц.

Простая выборка – запрос, где используются только 2 ключевых слова: SELECT и FROM.

Пример 1:

Выдать номера всех поставляемых деталей, в ПО это таблица (S,P, J,SPJ).

Номер поставщика	Номер детали	Номер изделия	Количество
S1	P1	Y1	200
S2	P1	Y4	700
S3	P3	Y4	1000
S4	P3	Y2	720

a) Поиск без исключения дубликатов.

Решение:

SELECT номер_детали FROM SPJ.

В реальных СУБД кириллица не допускается. Поэтому кириллицу заменяют на латиницу.

Результат:

Номер_детали: P1, P1, P3, P3

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

b) С исключением дублирования.

SELECT DISTINCT номер_детали FROM SPJ;

Результат: P1, P3.

Пример 2:

Выдать полные характеристики всех поставок (вывести всю таблицу SPJ).

SELECT * FROM SPJ.

*- все атрибуты таблицы.

Результат: вся таблица SPJ.

Выборка вычисленных значений.

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

Пример 1:

Выдать номера и веса деталей в граммах, если в таблице P вес детали задан в фунтах.

Таблица P

Номер	Название	Цвет	Вес	Город
P1	Болт	Черный	0,1	Париж
P2	Гайка	Черный	0,05	Париж

SELECT номер_детали, ‘вес в граммах’, вес * 454 FROM P;

Результат:

Номер детали вес в граммах вес*454

P1 0.1 45.40

P2 0.05 22.70

Выборка с ограничением.

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

Пример:

Выдать номера поставщиков, которые живут в Париже и имеют состояние более 20y.e.

Таблица S

Номер	Имя	Состояние	Город
51	Смит	5	Париж
52	Пит	25	Париж

SELECT номер FROM S WHERE город=’париж’ AND состояние>20;

Результат: 52.

В условие поиска, указываемое за ключевым слово WHERE, можно включать арифметические операторы сравнения( =, >, >=, <, <=, !<, !>, !<=, !>=); булевы операторы(AND, OR, NOT); опр-ые конструкции (BETWEEN, LIKE, IN); для указания порядка вычисления ().

Лекция 18

Пример:

Выдать номера поставщиков, которые имеют состояние от 10 до 20 у. е..

Рассмотрим таблицу S.

Решение:

Возможно два варианта:

1. SELECT номер_поставщика

FROM S

WHERE состояние >= 10 AND

состояние <= 20;

2. SELECT номер_поставщика

FROM S

WHERE состояние BETWEEN 10 AND 20;

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

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

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

2. Используется восходящий распознаватель. В стек операторов помещаются операторы AND, OR, NOT, (, ), а в стек операндов, списки идентификаторов записи (rowid), удовлетворяющих арифметическим условиям или ключевым конструкциям.

Пример:

WHERE A = 5 AND B = 3 (предположим что по атрибутам A и B существуют индексы)

Тогда заполнение стека показано в таблице.

операнды	операторы
{rowid}_A=5
{rowid}_A=5	AND
{rowid}_A=5 {rowid}_B=3	AND
{rowid}_{A=5, B=3}

4. Выборка с упорядочиванием.

Для выборки параметров с упорядочиванием по любым атрибутам используется ключевое слово ORDER BY. За ним должен следовать список атрибутов:

атрибут_1 [тип-порядка], атрибут_2 [тип_порядка] …

, где тип_порядка – либо ASC (упорядочивание по возрастанию, используется по умолчанию), либо DESC (упорядочивание по убыванию).

Упорядочивание результирующей таблицы производится следующим образом:

- результирующая таблица упорядочивается по атрибуту_1;

- те записи, которые имеют одинаковые значения по атрибуту_1, упорядочиваются по атрибуту_2 и т.д.;

Пример:

Выдать номера поставщиков, города их проживания и состояния с именем «Смит»

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

Пример исходной таблицы:

таблица S

номер поставщика	имя	состояние	город
S4	Смит	25	Манчестер
S1	Смит	25	Лондон
S2	Смит	50	Лондон
S3	Смит	40	Манчестер

Решение:

SELECT номер_поставщика, город, состояние

FROM S

WHERE имя = ‘Смит’

ORDER BY город, состояние DESC;

Результат:

номер_поставщика	город	состояние
S2	Лондон	50
S1	Лондон	25
S3	Манчестер	40
S4	Манчестер	25

5. Выборка с использованием конструкции “LIKE”.

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

атрибут LIKE строковая_константа

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

· ‘_’ – произвольная одиночная литера;

· ‘%’(*) – любая последовательность литер;

· остальные литеры обозначат сами себя;

Пример:

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

Решение:

SELECT номер_поставщика

FROM S

WHERE город LIKE `Л_о%`;

6. Ключевое слово IN.

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

Пример:

Выдать названия городов и имена поставщиков, состояние которых равно либо 40, либо 25, либо 60, либо 70.

Решение:

SELECT город, имя

FROM S

WHERE состояние IN (40,25,60,70);

2. Запросы, использующие соединение таблиц.

1. Простое соединение (тета-соединение).

Пример:

Выдать все комбинации о поставщиках и деталях, которые соответственно проживают и изготовляются в одном городе. (Поставщик не обязательно поставляет деталь).

Пример таблиц S и P.

Таблица S.

номер_поставщика	имя	состояние	город
S1	Смит	25	Лондон
S2	Джонс	10	Париж
S3	Блейк	15	Чикаго

Таблица P.

номер_детали	название	цвет	вес	город
P1	болт	черный	0,01	Лондон
P2	гайка	черный	0,02	Париж

Решение:

SELECT S.*, P.*

FROM S, P

WHERE S.город = P.город;

Примечание: S.* - список всех атрибутов таблицы S.

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

Результат:

номер_

поставщика

имя

состояние

город

номер_

детали

название

цвет

вес

город

Смит

Лондон

болт

черный

0,01

Лондон

Джонс

Париж

гайка

черный

0,02

Париж

Этот запрос моделирует операцию тета-соединения (не удаляются дублирующиеся столбцы).

2. Соединение с дополнительным условием.

Пример:

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

Решение:

SELECT S.номер_поставщика, P.номер_детали

FROM S, P

WHERE S.город = P.город AND P.состояние > 10;

Результат:

номер_поставщика	номер_детали
S1	P1

3. Соединение 3 таблиц.

Пример:

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

Таблица SPJ.

номер_поставщика	номер_детали	номер_изделия	количество
S1	P1	J1	10⁶
S1	P2	J1	10⁵
S2	P2	J2	10⁴
S3	P1	J3	10⁷

Решение:

SELECT S.город, P.город

FROM S, SPJ

WHERE S.номер_поставщика = SPJ.номер_поставщика AND

SPJ.номер_детали = P.номер_детали;

4. Соединение таблицы с ней самой.

Пример:

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

Решение:

SELECT PS1.номер_поставщика, PS2.номер_поставщика

FROM S PS1, S PS2

WHERE PS1.город = PS2.город AND

PS1.номер_поставщика < PS2.номер_поставщика;

Результат:

PS1.номер_поставщика	PS2.номер_поставщика
S1	S3

Ниже приведены конструкции, которые можно использовать как самостоятельные запросы, так и в выражениях FROM.

1. Декартово произведение.

Формат:

табл.1 CROSS JOIN табл.2

Пример:

S CROSS JOIN SPJ

- каждая запись из S соединяется с записью SPJ.

2. Тета-соединение.

Формат:

табл.1 JOIN табл.2 ON условие_соединения

Пример:

S JOIN SPJ ON S.номер_поставщика = SPJ.номер_поставщика

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

3 Естественное соединение:

Формат:

Табл. 1 NATURAL JOIN Табл. 2;

Пример:

S NATURAL JOIN SPJ;

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

Лекция 19

III Подзапросы.

Подзапрос представляет собой выражение

SELECT … FROM … WHERE …,

которое вложено в другое аналогичное выражение.

1. Простой подзапрос.

Пример:

Выдать номера поставщиков, которые поставляют детали с номерос P2.

Примеры таблиц:

ном_пост	имя	сост	город
S1	Смит	15	Лондон
S2	Джонс	10	Париж

SPG

ном_пост	ном_дет	ном_изд	количество
S1	P1	J1	100
S2	P2	J1	100
S3	P3	J3	100

Решение:

SELECT имя

FROM S

WHERE номер_поставщ IN

(SELECT номер_поставщи

FROM SPJ

WHERE номер_детали = ‘P2’);

Вначале обрабатывается внутренний подзапрос. Здесь определяются номера поставщиков, которые поставляют детали с номером P2. Затем выполняется внешний запрос, где номер поставщика из каждой записи таблицы S проверяется на принадлежность ранее найденному множеству.

В принципе подзапрос возвращает множество {S2}. Этому условию удовлетворяет вторая запись в таблице S. è

Результат:

имя

Джонс

2. Запрос с несколькими уровнями вложенности подзапросов.

Пример:

Выдать имена поставщиков, которые поставляют, по крайней мере, одну красную деталь.

Примеры таблиц S и SPG см. в предыдущем примере.

Пример таблицы P.

ном_дет	название	вес	город	цвет
S1	Болт	0.01	Лондон	красный
S2	гайка	0.02	Париж	красный
S3	винт	0.03	Лондон	черный

Решение:

SELECT имя

FROM S

WHERE номер_поставщ IN

(SELECT номер_поставщика

FROM SPJ

WHERE номер_детали = IN

SELECT номер_детали

FROM P

WHERE цвет = ‘красный’));

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

Самый внутренний подзапрос возвращает {P1,P2}

Следующий подзапрос возвращает {S1,S2}

Результат:

имя

Смит

Джонс

3. Коррелированный подзапрос.

Пример:

Выдать номера поставщиков, которые поставляют детали с номером P2.

Решение:

SELECT имя

FROM S

WHERE ‘P2’ IN

(SELECT номер_детали

FROM SPJ

WHERE номер_поставщика = S.номер_поставщика);

Если атрибут используется без префикса (в данном случае номер_поставщика), то он принадлежит таблице, указанной за ключевым словом FROM соответствующего подзапроса.

Здесь внутренний подзапрос зависит от внешнего.

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

- просматриваются все записи таблицы S

- для каждой записи выполняется внутренний подзапрос.

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

4. Использование одной и той же таблицы во внешнем и внутреннем запросах.

Пример:

Выдать номера поставщиков, которые поставляют по крайней мере одну деталь, поставляемую поставщиком с номером S2.

Решение:

SELECT номер_поставщика

FROM SPJ

WHERE номер_детали IN

(SELECT номер_детали

FROM SPJ

WHERE номер_поставщика = ‘S2’);

5. Подзапросы можно использовать в качестве таблицы в выражении FROM.

Пример:

Выдать номера поставщиков, которые поставляют по крайней мере одну красную деталь.

Решение:

SELECT имя

FROM S, (SELECT номер_поставщика

FROM SPJ,P

WHERE

SPJ.номер_детали = SPJ.номер_детали

AND цвет= ‘красный’) NP

WHERE S.номер_поставщика = NP. номер_поставщика;

IV Запросы с кванторами существования.

1. Использование ключевого слова EXIST.

Пример:

Выдать имена поставщиков, которые поставляют деталь с номером P2.

Решение:

SELECT имя

FROM S

WHERE EXIST (SELECT *

FROM SPJ

WHERE S.ном_пост=SPJ.ном_пост

AND ном_дет = ‘P2’);

Выражение EXIST возвращает истинное значение, если таблица, указанная в скобках не является пустой.

2. Использование конструкции NOT EXIST.

Пример:

Выдать номера поставщиков, которые поставляют по крайней мере все те детали, которые поставляет поставщик с номером S2.

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

Некоторые законы математической логики:

2) (импликация)

3) Закон де Моргана

Запишем исходный запрос в виде предиката:

{SX |

В чистом виде этот предикат имеет

Решение:

SELECT имя

FROM S

WHERE EXIST (SELECT *

FROM SPJ

WHERE S.ном_пост=SPJ.ном_пост

AND ном_дет = ‘P2’);

Выражение EXIST возвращает истинное значение, если таблица, указанная в скобках не является пустой.

Лекция 20

Примеры

1. Выдать количество поставок для деталей с N=’Р2’.Поставка-запись в SPJ

SELECT COUNT (*)

FROM SPJ

WHERE ном_дет=’Р2’;

2. Выдать общее количество поставляемых деталей с номером Р2

SELECT SUM (количество)

FROM SPJ

WHERE ном_дет=’Р2’;

3. Выдать номер состояния город для всех поставщиков, состояние которых не меньше среднего для их родного города

SELECT номер_пост, состояние, город

FROM S,SX

WHERE состояние>=

(SELECT AVG (состояние)

FROM S

WHERE город=SX.город)

Примечание

Эта конструкция правильна для условия, если возвращается из подзапроса только 1 значение

Использование конструкции GROUP BY в операторе SELECT

Если в операторе SELECT закодирована эта конструкция, то запрос выполняется в следующем порядке:

Строится декартово произведение таблиц указанных за ключевым словом SELECT
Из полученной на предыдущем шаге таблицы извлекаются записи, удовлетворяющие условию, указанному за ключевым словом SELECT
После этого полученные записи группируют по атрибутам, указанным за ключевым словом GROUP BY

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

Группы, которые не удовлетворяют условию, указанные за ключевым словом HAVING исключаются из рассмотрения
В результирующую таблицу включается только одна запись из каждой оставшейся группы

Примечание:
Если в операторе SELECT встречается агрегативная функция, то она действуют для строк каждой группы.

Примеры

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

Пример таблицы SPJ

Ном_поставщика	Ном_детали	Ном_изделия	Количество
S1	Р2	J1	100
S1	Р1	J1	200
S2	Р2	J2	300

SELECT ном_детали, SUM(количество)

FROM SPJ

GROUP BY ном_детали HAVING COUNT (DISTINCT ном_поставщика)>1;

Порядок выполнения:

1. Декартово произведение: SPJ

2. WHERE нет: SPJ

3. группа 1: S1, Р1, J1,200

группа 2: S1, Р2, J1,100

S2, Р2, J2,300

4. Дальше проходит только группа 2, группа 1 исключается из рассмотрения

5. Результат: Р2,400

Оператор обновления языка SQL

Оператор UPDATE

Обновляет существующие записи таблицы БД

UPDATE таблица

SET атр=1значение1[,атр2=знач2,…]

[WHERE условие];

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

Пример

Установить количество деталей в поставках равным 0 для всех поставщиков из Вашингтона

UPDATE SPJ

SET количество=0

WHERE ‘Вашингтон’ IN

(SELECT город

FROM S

WHERE номер_поставщика=SPJ.номер_пост);

Оператор DELETE

DELETE FROM таблица

[WHERE условие];

Из таблицы удаляются все записи, удовлетворяющие условию.

Оператор INSERT

В стандарте SQL99 существуют 2 варианта исполнения этого оператора

- Включение одной записи в таблицу (Действует во всех СУБД)

INSERT

INTO таблица [(атр1[,атр2,…])]

VALUES (конст1[,конст2,…]);

В таблицу включается одна запись, имеющая заданные значения для указанных атрибутов, причем i-ая константа соответствует i-му атрибуту. Отсутствие списка атрибутов эквивалентно перечислению всех атрибутов из схемы таблицы

Пример
Добавить в таблицу деталь с номером Р7, цвет и название неизвестны.

INSERT

INTO Р (ном_детали, город,вес)

VALUES (‘P7’,’Лондон’, 0,001);

- Включение нескольких записей в таблицу

INSERT

INTO таблица [(атр1[,атр2,…])]

Подзапрос;

В этом операторе сначала определяется таблица, связанная с подзапросом. Затем строки этой таблицы включаются в исходную таблицу, имя которой указано за ключевым словом INTO. При этом i-ый атрибут подзапроса соответствует i-ому атрибуту в списке атрибутов таблицы.

Пример

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

CREATE TABLE рабочая

(ном_детали VARCHAR(7);

Общ_кол_в_пост_ NUMBER);

INSERT INTO рабочая

SELECT ном_детали,SUM(количество);

FROM SPJ

GROUP BY ном_детали;

3 задача к КР

1. Выдать номера изделий и названия, где они изготовляются, такие, что 2-я буква в названии города является ‘а’.

2.Выдать номера тех деталей, поставляемых для какого-либо изделия поставщиком, проживающим в том же городе, в котором изготовляются эти изделия

3. Выдать номера поставщиков, поставляющих деталь Р1 для какого-либо изделия в количестве большем, чем средний объем поставок деталей с номером Р1 для этого изделия

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

Основы оптимизации SQL-запросов

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

Основные шаги оптимизации

I. Оптимизатор строит логический план выполнения запроса (дерево логических операций). Для этого он делает следующее:

- преобразовывает запрос в формулу реляционной алгебры

- производит оптимизацию формулы реляционной алгебры

II. Оптимизатор строит оптимальный физический план выполнения запроса (дерево физических операций). Для этого он делает следующее:

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

Физические планы в основном отличаются следующим:

а) методом выбора записей из исходных таблиц (методом реализации подзапросов );

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

в) методом соединения таблиц (т.е. методом реализации операции естественного соединения ).

метод вложенных циклов, метод сортировки-слияния, хешированное соединение.

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

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

Отличие физического плана от логического состоит в том, что логический план не указывает на то, как должны быть реализованы операции реляционной алгебры (проекция, селекция, декартово произведение, естественное соединение). Физический план определяет, как эти операции будут реализовываться.

III. Оптимизатор реализует полученный оптимальный физический план выполнения запроса.

Оптимизация SQL-запросов

Последовательность оптимизации запросов и

используемые законы реляционной алгебры

Основные шаги оптимизации

Поступающий на сервер SQL-запрос подвергается оптимизации с целью уменьшения времени его выполнения. При этом оптимизатор запросов выполняет следующие шаги:

I. Строит логический план выполнения запроса (дерево логических операций).

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

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

Примечание. Оптимизатор называется восходящим, если при построении оптимального физического плана он просматривает логический план от листьев к корню. Если логический план просматривается от корня к листьям, то такой оптимизатор называется нисходящим.

Законы реляционной алгебры

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

1.Закон коммутативности декартова произведения.

Имеет место равенство:

R₁ × R₂ = R₂ × R₁,

где R₁ и R₂ – отношения (таблицы).

2. Закон ассоциативности декартова произведения.

Справедливо равенство:

(R₁ × R₂) × R₃ = R₁ × (R₂ × R₃),

где R₁, R₂ и R₃– отношения (таблицы).

3. Закон каскада проекций.

Если , где {a₁, …, a_n} и {b₁, …, b_m} – некоторые множества атрибутов, то имеет место следующее равенство:

4. Закон каскада селекций.

Если условие F является конъюнкцией нескольких условий, т.е. , то справедливо следующее равенство: .

5. Закон перестановки проекции и селекции:

1. В условие F входят атрибуты только из множества {a₁, …, a_n}.

Имеет место следующее равенство:

2. В условие F входят атрибуты не только из множества {a₁, …, a_n}.

Справежливо следующее равенство:

где b₁, …, b_m – атрибуты таблицы R, которые входят в условие F, но не принадлежат множеству {a₁, …, a_n}.

6. Закон перестановки селекции и декартова произведения.

Если условие f₁ включает в себя только атрибуты отношения R₁, то имеет место следующее равенство:

Следствие. Пусть , причем в f₁ входят атрибуты только из отношения R₁, а в f₂ входят атрибуты только из R₂. В этом случае справедливо следующее равенство:

7. Закон перестановки селекции и объединения.

Имеет место следующее равенство:

Примечание. В языке SQL операция объединения отношений моделируется с помощью операции UNION.

8. Закон перестановки селекции и разности отношений.

Справедливо следующее равенство:

, где R₁ – R₂ – множество кортежей, которые принадлежат отношению R₁ и не принадлежат R₂.

9 Закон перестановки проекции и декартова произведения.

Пусть {b₁, …, b_n} – некоторые атрибуты из R₁, {с₁, …, с_m} – некоторые атрибуты из R₂. Имеет место следующее равенство:

10. Закон перестановки проекции и объединения.

Справедливо следующее равенство:

Построение логического плана

При построении логического плана выполнения SQL-запроса выполняются следующие действия:

1. Запрос преобразуется в формулу реляционной алгебры (явно или неявно).

2. Выполняется преобразование (оптимизация) этой формулы.

Преобразование запроса в формулу реляционной алгебры

Оператор SELECT языка SQL может быть представлен в виде следующей формулы реляционной алгебры (здесь не рассматриваются функции агрегирования, группирования и удаления дубликатов):

π_A(σ_F(R₁× R₂ × … × R_n)), (5.1)

где R₁× R₂ × … × R_n – декартово произведение отношений (таблиц), указанных за ключевым словом FROM;

σ_F – операция селекции кортежей декартова произведения в соответствии с условием F, указанным за ключевым словом WHERE;

π_A – проекция селекции на множество атрибутов А, перечисленных за ключевым словом SELECT.

Ниже приведён пример преобразования запроса.

Запрос: "Найти фамилию пользователя с кодом 3".

Оператор SELECT:

SELECT фамилия

FROM пользователь

WHERE код_пользователя = 3;

Формула реляционной алгебры:

A

F

R₁

Оптимизация формулы реляционной алгебры

При оптимизации формулы используются следующие правила:

1. Если условие F является конъюнкцией нескольких условий (), то переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8.

2. Переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10.

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

В результате использования правил 1–3 формула реляционной алгебры (5.1), соответствующая исходному запросу, преобразуется в следующую формулу:

, (5.2)

где

– условие, сформулированное в исходном запросе SELECT;

f – условие соединения подзапросов {Q_i}.

Подчеркнутые в приведённой выше формуле отношения Q₁, …, Q_n имеют меньшую размерность, чем исходные отношения R₁, …, R_n, и потому запрос по формуле (5.2) выполняется быстрее, чем по формуле (5.1).

По формуле (5.2) можно построить логический план, представленный на рис. 1.1.

Рис. 1.1. Логический план выполнения запроса, соответствующий формуле (5.2)

Иллюстрация логической оптимизации

1. Выполнение запроса по формуле π_A(σ_F(R₁× R₂ × … × R_n)), до оптимизации, иллюстрируется рисунком (рис. 1.2).

Рис. 1.2. Выполнение запроса по формуле (5.1).

2. Выполнение запроса по формуле

, после оптимизации, иллюстрируется рисунком (рис. 1.3).

Рис. 1.3. Выполнение запроса после оптимизации по формуле (5.2).

В случае отсутствия оптимизации запроса вначале нужно определить декартово произведение исходных таблиц R₁, …, R_n , затем выполнить селекцию σ_F и взять проекцию π_A. Если таблицы R₁, …, R_nимеют большую размерность, то время выполнения запроса будет достаточно большим. Поэтому запрос по формуле (5.2) выполняется быстрее, так как отношения Q₁, …, Q_n имеют меньшую размерность, чем исходные отношения R₁, …, R_n
.

Примечание. Если исходные таблицы R₁, …, R_n размещаются на разных серверах или на одном суперкомпьютере, то подзапросы Q₁, …, Q_n могут выполняться параллельно.

Пример построения логического плана

Оптимизация запроса

Предположим, что на сервер СУБД поступает запрос SELECT. На сервере хранятся две таблицы, участвующие в запросе (рис. 1.4).

Рис. 1.4. Исходные таблицы на сервере СУБД.

Предположим, что клиент, связанный с сервером СУБД, выдал следующий запрос: "Найти значения остатков, большие 1500, на счетах пользователя с кодом 3". Соответствующий запрос SELECT имеет следующий вид:

SELECT остаток

FROM R2

WHERE остаток > 1500 AND номер_счета IN

(SELECT номер_счета

FROM R1

WHERE код_пользователя = 3);

Этот оператор SELECT преобразуется в формулу реляционной алгебры (см. п. 1.2.1):

Эта формула подвергается оптимизации. Оптимизатор вначале строит логический план выполнения запроса, используя законы реляционной алгебры (см. пункты 1.1.2 и 1.2.2, номера законов показаны над равенствами):

Последняя формула – результат оптимизации, здесь подчёркнуты подзапросы. По этой формуле оптимизатор строит логический план выполнения запроса (рис. 1.5).

Рис. 1.5. Логический план выполнения запроса в графическом виде.

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

1. Определение промежуточных таблиц Q₁ и Q₂.

На основе полученной формулы

(5.3)

определяются промежуточные таблицы Q₁ и Q₂:

Из таблицы R1 (см. рис. 1.4) получим

Q1: номер_счета

102

Из таблицы R2 (см. рис. 1.4) получим

Q2: номер_счета остаток

101	2000
102	3000

2. Соединение промежуточных таблиц Q₁ и Q₂.

Выполняется соединение промежуточных таблиц Q₁ и Q₂ и передача результата клиенту. При этом реализуется формула

а) Q = Q₁´Q₂:

R1.номер_счета R2.номер_счета R2.остаток

102	101	2000
102	102	3000

б) Z = s_R_{1.номер_счета=}_R_{2.номер_счета}(Q):

R1.номер_счета R2.номер_счета R2.остаток

102

3000

в) p_R_{2.остаток}(Z):

остаток

3000

Эта величина остатка посылается клиенту.

Примечание. Если таблицы R1 и R2 хранятся на других различных серверах S1 и S2, то подзапросы Q₁ и Q₂ преобразуются в запросы SELECT и направляются на серверы S1 и S2, где параллельно выполняются.

Подзапрос Q₁ преобразуется к виду:

SELECT номер_счета

FROM R1

WHERE код_пользователя=3;

Подзапрос Q₂ преобразуется к виду:

SELECT номер_счета, остаток

FROM R2

WHERE остаток > 1500;

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

Построение физического плана

Шаги построения физического плана

При построении оптимального физического плана выполнения SQL-запроса (дерева физических операций) выполняются следующие действия:

1. Последовательно строится множество физических планов на основе логического плана (см. разделы 1.2, 1.3). Физические планы в основном отличаются следующим:

а) методом выбора записей из исходных таблиц (методом реализации подзапросов );

б) порядком соединения таблиц;

в) методом соединения таблиц (т.е. методом реализации операции естественного соединения ).

2. Для каждого физического плана рассчитывается стоимость его выполнения. Выбирается физический план с наименьшей стоимостью.

Отличие физического плана от логического

Логический план не указывает на то, как должны быть реализованы операции реляционной алгебры (проекция, селекция, декартово произведение, естественное соединение). Физический план определяет, как эти операции будут реализовываться.

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

Рис. 1.6. Логический и физический планы выполнения запроса.

Физический план выполняется в следующей последовательности.

1. Здесь операции реализуются следующим образом: читается вся таблица R1 (TableScan(R1)) и затем каждая запись проверяется, удовлетворяет ли она логическому условию F₁, и если да, то из нее выделяются атрибуты, входящие в множество A₁ (). Получившаяся промежуточная таблица является правым аргументом соединения.

2. Операции реализуются следующим образом: с помощью индекса читаются записи таблицы R2, удовлетворяющие подусловию φ (IndexScan(R2, φ)). Здесь φ – некоторое подусловие условия F₂ по атрибуту, который имеет индекс.

Примеры подусловий φ: a = 5, a > 5, a ≥ 5, a < 5, a ≤ 5 (a – индексированный атрибут таблицы R2).

Считанные записи фильтруются (). Получившаяся промежуточная таблица является левым аргументом соединения.

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

Оптимизатор для каждого физического плана рассчитывает стоимость. Эта стоимость равна сумме составляющих. Для данного примера имеем:

Каждая из этих составляющих, в свою очередь, включает процессорную составляющую и составляющую дискового ввода-вывода:

C = C_CPU + C_I_/_O .

После перебора нескольких физических планов оптимизатор выбирает план с минимальной стоимостью.

Методы выбора записей из исходной таблицы

1. Чтение всех записей таблицы и их фильтрация.

Схематично эту операцию (TableScan + Filter) можно представить в следующем виде (рис. 1.7, нижние индексы в обозначениях таблиц и условий поиска будем пока опускать).

Рис. 1.7. Чтение всех записей.

Стоимость работы процессора и дискового ввода-вывода рассчитывается по формулам:

C_CPU = T(R) · C_filter , (5.4)

C_I/O = B(R) · C_B ,

где

T(R) – число кортежей (записей) в исходной таблице R;

B(R) – число физических блоков таблицы R;

С_filter – время фильтрации одной записи в ОП;

C_B – время чтения/записи одного блока на диск.

2. Чтение записей с помощью индекса и их фильтрация.

Схема операции (IndexScan + Filter) представлена на рис. 1.8.

Рис. 1.8. Чтение записей с помощью индекса.

Стоимость работы процессора и подсистемы ввода-вывода определяются следующими выражениями:

(5.5)

где

T(R) – число записей в таблице R;

B(R) – число блоков таблицы R;

I(R,a) – мощность атрибута "а" в таблице R (число различных значений);

B(Index(R,a)) – число блоков на листовом уровне индекса по атрибуту "а";

С_filter – время фильтрации одной записи в ОП;

C_B – время чтения/записи одного блока на диск;

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

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

Мощность атрибута в запросе (параметр k) можно оценить с помощью следующих выражений:

(5.6)

Величину в формулах (5.5) можно интерпретировать как вероятность, что запись таблицы R удовлетворяет условию φ по атрибуту "а".

Оценка числа кортежей в промежуточной таблице Q

Число кортежей оценивается с помощью следующей формулы:

T(Q) = T(R)·p , (5.7)

где

Q=s_F(R) – промежуточной таблица, соответствующая подзапросу Q,

T(Q) – оценка числа кортежей в промежуточной таблице Q,

T(R) – общее число кортежей в исходной таблице R,

p – вероятность того, что кортеж из R удовлетворяет условию поиска F.

Для расчета вероятности p можно воспользоваться следующими рекурсивными выражениями:

1. Пусть F = f₁ AND f₂ . Тогда

p = p₁p₂ ,

где p_i – вероятность того, что запись из R удовлетворяет подусловию f_i (i=1,2).

2. Пусть F = f₁ OR f₂ . Тогда

p = p₁ + p₂ – p₁p₂ .

3. Пусть F = NOT f₁ . В этом случае

p = 1 – p₁ .

Если в приведенных выше случаях 1–3 f_i – подусловие по какому-либо атрибуту "а", то вероятность p_i рассчитывается по следующей формуле:

где k – мощность атрибута в подзапросе (см. формулу (5.6)),

I(R,a) – мощность атрибута "а" в таблице R.

Ниже приведён пример расчёта числа кортежей в промежуточной таблице.

Пусть таблица R включает атрибуты (a, b, c). Число кортежей T(R) = 1000. Мощности атрибутов: I(R,a) = 5, I(R,b) = 10, I(R,c) = 2. Для простоты полагаем, что a, b, c – натуральные положительные числа.

Пусть задано условие выбора записей таблицы R:

F = (a < 3 OR b ³ 5) AND c = 2

Требуется оценить число записей, удовлетворяющих условию F.

Решение.

1. f₃ = f₁ OR f₂

2. F = f₃ AND f₄

– вероятность того, что запись из R удовлетворяет условию F.

3. T(Q) = T(R)·p = 1000·0,38 = 380 – оценка числа записей, удовлетворяющих условию F.

Оценка числа блоков в промежуточной таблице Q

Число блоков в промежуточной таблице можно оценить при помощи следующей формулы:

где

Q=s_F(R) – промежуточной таблица, соответствующая подзапросу Q,

T(Q) - оценка числа кортежей в промежуточной таблице (см. п. 1.4.4),

L_B – длина блока (т.е. число записей в блоке),

- операция округления с избытком.

Порядок соединения таблиц

Существуют три вида деревьев соединений:

1. Левостороннее дерево соединений.

2. Кустовое (ветвящееся) дерево соединений.

3. Правостороннее дерево соединений.

Левостороннее дерево соединений

Рис. 1.9. Левостороннее дерево соединений.

В данном варианте в каждом соединении правым аргументом является исходная таблица. Этот порядок соединения имеет следующие преимущества:

· число переборов вариантов соединений меньше, чем для кустового дерева (для левостороннего дерева оно равно n!, где n – число соединяемых таблиц);

· для этого типа дерева достаточно просто организовать каналы обработки.

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

Рассмотрим операции соединений 1 и 2 на рис. 1.9: (R S)T. Схема выполнения этих операций показана на рис. 1.10.

Рис. 1.10. Организация каналов обработки.

В канале только левый аргумент может быть опорным (т.е. храниться в оперативной памяти). Правый аргумент соединения называется тестируемым и может располагаться на диске. Если таблица подзапроса R и результат соединения (см. рис. 1.10) умещаются в оперативной памяти, то использование каналов позволяет организовать однопроходной алгоритм соединения таблиц (исходные таблицы R₁, S₁, T₁ читаются с диска один раз).

Можно отметить следующий недостаток рассмотренного порядка соединения таблиц: выбирается квазиоптимальный план, так как перебирается ограниченное число вариантов (n!), поскольку правый аргумент – это всегда исходная таблица.

Кустовое дерево соединений

Рис. 1.11. Кустовое дерево соединений.

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

Этот метод обеспечивает поиск оптимального плана, так как перебираются все возможные варианты соединения таблиц. Но часто полный перебор всех деревьев соединений занимает много времени. Также при выполнении соединений таблиц имеются сложности в организации каналов, так как возрастают требования к объёму оперативной памяти.

Например, для реализации однопроходного алгоритма соединения таблиц, представленных на рис. 1.11, необходимо, чтобы в оперативной памяти размещались таблицы R и , T и .

Правостороннее дерево соединений

Рис. 1.12. Правостороннее дерево соединений.

В данном варианте в каждом соединении левым аргументом является исходная таблица.

Этот способ практически не используется, так как для реализации однопроходного алгоритма соединений необходимо, чтобы в ОП размещались (не одновременно) таблицы T, S, R и результаты промежуточных соединений.

Методы соединения таблиц

Ниже рассматриваются три метода соединения таблиц:

· метод вложенных циклов (NLJ – Nested Loop Join),

· метод сортировки-слияния (SMJ – Sort Merge Join),

· хешированное соединение (HJ – Hash Join).

Метод вложенных циклов (NLJ – Nested Loop Join)

При этом методе каждая запись первой таблицы сравнивается с каждой записью второй таблицы (рис. 1.13, сравнение выполняется по номеру счёта). В общем случае условие сравнения может быть произвольным.

Рис. 1.13. Метод соединения NLJ.

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

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

2) назначения буферов ввода-вывода (рис. 1.14).

Рис. 1.14. Схема назначения буферов ввода-вывода.

В этом случае формулы для вычисления стоимости соединения NLJ следующий вид:

(5.8)

где

T(Q₁), T(Q₂) – число кортежей в таблицах подзапросов Q₁и Q₂;

B(Q₁) – число блоков в таблице Q₁;

С_I_/_O(Q₂) – время ввода-вывода для получения таблицы Q₂;

b – число блоков в буфере для Q₁;

C_comp – время соединения (сравнения) двух кортежей из таблиц Q₁и Q₂ в оперативной памяти (ОП);

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

Во второй формуле учитывается возможность многопроходного варианта соединения таблицы Q₂, если таблица Q₁не умещается в "b" блоках буфера оперативной памяти. Округление берётся с недостатком, так как одно чтение таблиц с диска учитывается в стоимости выбора записей из исходных таблиц.

Метод сортировки-слияния (SMJ – Sort Merge Join)

Соединение таблиц включает следующие шаги:

1. Соединяемые таблицы сортируются по атрибуту соединения (обозначим его через "а").

2. Организуется вложенный цикл, где выполняется сравнение значений атрибутов соединения.

Условием соединения может быть только равенство атрибутов соединения.

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

Рис. 1.15. Метод соединения SMJ.

Выполняется сравнение записей, на которые указывают указатели таблиц Q₁и Q₂. Перемещение указателей выполняется следующим образом: если выполняется условие "<", то осуществляется перемещение указателя Q₁к следующей записи; если выполняется условие ">", то к следующей записи перемещается указатель Q₂; при "=" указатели не перемещается и выполняется сравнение со следующей записью таблицы Q₂.

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

Рис. 1.16. Схема назначения буферов.

Формулы для оценки стоимости соединения SMJ имеют следующий вид.

Здесь

T(Q₁), T(Q₂) – число кортежей в таблицах Q₁и Q₂;

B(Q₁), B(Q₂) – число блоков в таблицах Q₁и Q₂;

I(Q₁,a), I(Q₂,a) – мощности атрибутов соединения "а" в таблицах Q₁и Q₂;

b – число блоков в ОП, отводимых под сортировку таблицы Q₁ или Q₂;

C_comp – время соединения двух кортежей из таблиц Q₁и Q₂в ОП;

C_move – время перемещения одного кортежа в ОП при сортировке;

C_B – время чтения/записи одного блока на диск;

- округление с избытком;

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

- не учитывается, если таблицы были уже отсортированы перед началом соединения.

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

Блоки 1¸b таблицы R читаются в буфер (рис. 1.17) и записи этих блоков сортируются. Результат сортировки сохраняется в виде файла. Затем читаются следующие "b" блоков (b¸2b, см. рис. 1.17) и их записи также сортируются, результат сортировки сохраняется во втором файле и т.д.

Рис. 1.17. Чтение большой таблицы в буфер из b блоков.

Сохранённые файлы представлены в виде уровня 1 на рис. 1.18.

Известно, что число операций сравнений и перемещений при сортировке пропорционально величине , где - число сортируемых записей. - это количество файлов уровня 1. Поэтому для одного файла . С учётом числа файлов получаем первое слагаемое в формуле 3 (см. выражения (5.9)).

Рис. 1.18. Последовательное укрупнение отсортированных промежуточных файлов.

Далее из 1-го файла уровня 1 записи читаются в 1-й блок буфера, из 2-го файла уровня 1 записи читаются во 2-й блок и т.д., и из b-го файла уровня 1 записи читаются в b-й блок (рис. 1.19). В каждом блоке записи уже отсортированы на предыдущем этапе. Поэтому сравниваются первые записи этих блоков по атрибуту сортировки (b сравнений). Запись с минимальным значением атрибута перемещается в файл (одно перемещение). Остальные записи соответствующего блока сдвигаются вверх (блок работает как стек). Затем снова сравниваются первые записи b блоков по атрибуту сортировки и т.д. Если записи в каком-либо блоке исчерпаны, то в этот блок подгружаются записи из связанного с ним файла. После обработки таким способом b файлов уровня 1 будет сформирован файл уровня 2 (см. рис. 1.18), записи в котором отсортированы. Далее в блоки буфера подгружаются записи следующих b файлов уровня 1 и т.д.

По аналогичной схеме (см. рис. 1.19) объединяются файлы уровня 2 и т.д. В конце концов, будет сформирован один отсортированный результирующий файл (см. рис. 1.18). Количество уровней L может быть получено из уравнения (число файлов на самом нижнем уровне равно 1), т.е. .

Рис. 1.19. Сортировка записей из b промежуточных файлов.

На каждом уровне (кроме последнего) по описанной выше схеме (см. рис. 1.19) обрабатываются все записи таблицы R (их число равно T(R)). Это объясняет второе слагаемое в формуле 3. В файлах каждого уровня хранятся B(R) блоков. Это объясняет формулу 4. Здесь коэффициент 2 учитывает, что каждый файл каждого уровня записывается на диск, а потом читается.

Чтение блоков таблицы R с диска (см. рис. 1.17) учитывается в стоимости выбора записей из исходной таблицы.

В формуле 5 первое слагаемое определяет процессорное время сравнения соединяемых записей. Если , то каждая запись из (их число равно ) сравнивается и соединяется с записями из (т.е. с числом записей из , приходящихся на одно значение атрибута соединения). Константа 2 учитывает сравнения записей при перемещении указателей. Второе слагаемое в формуле 5 связано с холостыми проверками. Количество таких сравнений равно числу записей в , у которых значение атрибута соединения отличается от всех значений атрибута "а" в (мощность таких значений атрибута "а" в равно ).

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

Метод хешированного соединения (HJ – Hash Join)

При хешированном соединении выполняются следующие шаги:

1. Выбирается хеш-функция h(a).

2. Записи соединяемых таблиц хешируются, т.е. создаются хеш-разделы.

3. Выполняется соединение записей соответствующих разделов по алгоритму NLJ или SMJ.

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

Пример двух таблиц, соединяемых методом хешированного соединения, приведён на рис. 1.20.

Рис. 1.20. Соединяемые таблицы.

1) В качестве хеш-функции выбрано деление номера счета по модулю 10.

2) Обозначим хеш-разделы следующим образом:

R_i – множество номеров счетов из R, у которых остаток от деления на 10 равен i;

S_i – множество номеров счетов из S, у которых остаток от деления на 10 равен i.

3) Соединение разделов.

Представим процесс соединения в виде следующей таблицы (табл. 1.1).

Табл. 1.1.

Результаты соединения разделов

S_i R_i	S₀=Ø	S₁=(31, 1, 1)	S₂=(2)	S₃=Ø	S₄=Ø	S₅=Ø	S₆=(26)	S₇=(27)	S₈=Ø	S₉=Ø
R₀=(10, 30)	–
R₁=(1)		1
R₂=(2)			2
R₃=(3)				–
R₄= Ø					–
R₅=(25)						–
R₆= Ø							–
R₇= Ø								–
R₈= Ø									–
R₉= Ø										–

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

Возможны два варианта реализации хешированного соединения.

1. Однопроходной вариант (рис. 1.21).

Все разделы R_i хранятся в оперативной памяти. Последовательно читаются блоки S с диска. Для каждой записи из S выполняется хеш-функция i=h(a) и значение атрибута соединения данной записи сравнивается со значениями атрибута соединения записей раздела R_i (для краткости будем говорить данная запись соединяется с записями раздела R_i).

Рис. 1.21. Распределение памяти в однопроходном варианте.

2. Двухпроходной вариант (рис. 1.22).

Таблицы R и S хешируются и их разделы {R_i} и {S_i} сохраняются на диске. Далее в ОП читается весь раздел R₀ и в буфер последовательно читаются блоки раздела S₀. Их записи соединяются с записями раздела R₀. Далее в оперативную память читается весь раздел R₁и далее S₁поблочно соединяется с R₁и т.д.

Рис. 1.22. Распределение памяти в двухпроходном варианте.

Теперь рассмотрим одну интересную особенность хешированного соединения.

В методах NLJ и SMJ соединяемые таблицы уже должны храниться на сервере перед выполнением соединения. В методе HJ соединение таблиц R и S может выполняться асинхронно, по мере поступления записей этих таблиц с других серверов (рис. 1.23).

Рис. 1.23. Асинхронное соединение таблиц.

На рис. 1.23 цифрами обозначены следующие действия:

1 - сравнение поступившей записи с записями соответствующего противоположного раздела;

2 – вывод соединения двух записей при успешном сравнении атрибутов соединения;

3 – сохранение поступившей записи в соответствующем разделе.

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

Число кортежей, блоков и мощности атрибутов в соединении

Приведенные ниже формулы являются общими для всех рассмотренных выше методов (NLJ, SMJ и HJ).

1. Число кортежей в соединении.

(5.10)

2. Число блоков.

3. Мощности атрибутов:

а) мощность атрибута соединения ("а") в результирующей таблице

;

б) мощности остальных атрибутов (b)

Здесь T(Q₁), T(Q₂) – число кортежей в таблицах Q₁и Q₂;

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

I(Q_i,a) – мощность атрибута "а" в таблице Q_i (i=1,2);

L_JOIN – число кортежей соединения в одном блоке.

Поясним 1-ую формулу из 3-х, приведённых выше. Пусть . В этом случае каждая запись из соединяется в среднем с записями из (считается, что если , то значение атрибута связи в записи из таблицы совпадёт со значением соответствующего атрибута какой-либо записи из ).

Поиск физического плана с минимальной стоимостью

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

Алгоритм поиска для левостороннего дерева соединений

Вход: логический план выполнения SQL-запроса с таблицами R₁, …, R_n (см. раздел 1.2).

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

//Алгоритм динамического программирования

ДЛЯ i=1,n

AccessPlan(R_i) //определение

КОНЕЦ ДЛЯ

ДЛЯ i=2,n

ДЛЯ всех подмножеств таких, что |P|=i

// |P| - количество таблиц в P

ДЛЯ всех таблиц

// определение метода соединения , дерево

// соединения таблиц (P – Q_j) уже создано при выполнении

// предыдущих циклов

JoinPlan(P – Q_j,Q_j)

КОНЕЦ ДЛЯ

OptPlanReturn({Q₁, …, Q_n}) //вывод оптимального плана

//Конец алгоритма

Формат экземпляра структуры данных

Алгоритм работает с массивом структур. Экземпляр структуры имеет следующий формат:

1. W – множество имен таблиц {Q_i} таких, что W=XÈY, если |W| > 1, и W – имя таблицы Q_i, если |W| = 1.

2. X – подмножество исходных таблиц {Q_i}, которые использованы для получения левого аргумента соединения XY.

3. Y – имя таблицы Q_i, которая используется в качестве правого аргумента соединения XY.

Примечание. Если W содержит имя только одной таблицы, т.е. |W| = 1, то X и Y – пустые поля.

4. Z – текущая стоимость выполнения плана, включающая стоимости выполнения подзапросов и промежуточных соединений, а также стоимость соединения XY, если |W| > 1, или стоимость выполнения подзапроса, если |W| = 1.

5. ZIO – составляющая ввода-вывода в Z (C_I/O).

6. V – опции:

1) T(W) – прогнозируемое число кортежей (записей) в таблице W (т.е. T(XY), если |W| > 1, или T(Q_i), если |W| = 1);

2) B(W) – прогнозируемое число блоков в W;

3) {I(W, A_i)}_i – мощности атрибутов в W, по которым было выполнено или будет выполняться соединение;

4) к – идентификатор метода выбора записей из исходной таблицы (если |W| = 1) или метода соединения таблиц (если |W| > 1).

Спецификации процедуры AccessPlan

Вход: R_i – имя исходной таблицы.

Выход: заполненный экземпляр структуры str[i].

Алгоритм.

// оценка стоимости выбора записей из R_i для различных методов:

// j=1 – чтение всей таблицы, j=2 – использование индекса.

ДЛЯ j=1,2

C_j= C_CPUj + C_I_/_Oj

// C_CPUj и C_I_/_Oj вычисляются с помощью формул (5.4) (для j=1)

// или с помощью формул (5.5) и (5.6) (для j=2).

КОНЕЦ ДЛЯ

// определение оптимального метода выбора записей из таблицы R_i,

// т.е. kÎ{1,2}, заполнение экземпляра структуры str[i] (см. п. 1.7.2)

C=min (C₁, C₂) // здесь С=С_k

str[i] = {

{Q_i}, Ø, Ø, // W, X, Y

C, C_I_/_O_k, // Z, ZIO

{T(Q_i), B(Q_i), {min{T(Q_i), I(R_i, A_j)}_j, k} // V

// для заполнения полей T(Q_i), B(Q_i) используются формулы

// пунктов 1.4.4 и 1.4.5

}

Конец алгоритма.

Спецификации процедуры JoinPlan

Вход: список имен таблиц R=(P – Q_j) и имя таблицы S=Q_j (см. основной алгоритм в п. 1.7.1)

Выход: заполненный экземпляр структуры str[n].

Алгоритм.

Поиск в массиве структур str экземпляров с номерами m₁ и m₂,

для которых str[m₁].W=R и str[m₂].W=S .

// Оценка стоимости соединения для различных методов:

// i=1 – NLJ, i=2 – SMJ, i=3 – HJ ;

// выбрать оптимальный метод соединения kÎ(1,2,3).

ДЛЯ i=1,3

C_i= C_CPUi + C_I/Oi

// C_CPUi и C_I_/_Oi вычисляются с помощью формул (5.8) (для i=1)

// или формул (5.9) (для i=2); метод i=3 не рассматривается.

// Необходимая информация для расчета по формулам

// хранится в полях str[m₁].V и str[m₂].V.

КОНЕЦ ДЛЯ

C = min(C₁, C₂) //здесь С=С_k; пока это стоимость соединения R и S

// текущая стоимость плана, включающая стоимости чтения

// из исходных таблиц и стоимости промежуточных соединений

С = str[m₁].Z + str[m₂].Z + C

С_I_/_O = str[m₁].ZIO + str[m₂].ZIO + C_I_/_O_k // дисковая составляющая

Поиск в массиве структур str экземпляра "n", для которого str[n].W=P. Если экземпляр "n" не найден, то заполнить пустой экземпляр "n". Если экземпляр "n" найден и выполняется неравенство str[n].Z > C, то переписать экземпляр "n". Выражения для заполнения экземпляра "n":

str[n] = {P, R, S, C, C_I_/_O, // W, X, Y, Z, ZIO

{T(P), B(P), {I(P, A_i)}_i, k} } // V - см. формулы (5.10)

Конец алгоритма.

Спецификации процедуры OptPlanReturn

Вход: список таблиц Q={Q_i}.

Выход: вывод оптимального плана.

Алгоритм.

Поиск в массиве структур str экземпляра i, где str[i].W=Q

// Вывод шага оптимизации

Печать (Q, "=", str[i].X, "", str[i].Y, "метод", str[i].V.k)

Если str[i].X пусто, то выйти из алгоритма

// Вывод оптимального плана для левого аргумента соединения

OptPlanReturn(str[i].X)

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

// соединения, которым является исходная таблица.

OptPlanReturn(str[i].Y)

Конец алгоритма.

Пример построения оптимального физического плана

Логический план

Построим оптимальный физический план для примера, который был рассмотрен ранее в разделе 1.3. В этом примере был построен логический план, представленный на рис. 1.24.

Рис. 1.24. Логический план выполнения запроса.

Ниже приведены исходные данные для построения физического плана:

1. Количество записей в исходных таблицах:

T(R₁)=10000, T(R₂)=100000

2. Количество записей в одном блоке таблицы:

L_R₁= L_R₂= 100, L_JOIN=1000

3. Индексы по атрибутам и число записей в блоке индекса (L):

таблица R₁: индекс по атрибуту "код_пользователя" (L=200),

таблица R₂: индекс по атрибуту "номер_счета" (L = 200).

Примечание. Записи исходных таблиц могут читаться в отсортированном виде по своим индексированным атрибутам. Записи в таблице R₁ сгруппированы по атрибуту "код_пользователя" (кластеризованный индекс), записи в таблице R₂ не сгруппированы по атрибуту "остаток".

4. Мощности атрибутов в исходных таблицах:

I(R₁, код_пользователя) = 5000, I(R₁, номер_счета) = 10000,

I(R₂, номер_счета) = 100000, I(R₂, остаток) – неизвестно.

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

6. Некоторые параметры:

b = 10 – число блоков в буфере;

C_comp = C_move = C_filter = 0,01 мс;

C_B = 10 мс – время чтения/записи блока на диск.

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

Алгоритм поиска оптимального физического плана

Ниже приведена последовательность расчётов.

Определение :

1.Определение метода выбора записей из исходной таблицы R₁

(Пользователь):

AccessPlan(R₁) (см. п. 1.7.3).

2. Определение метода выбора записей из исходной таблицы R₂

(Счёт):

AccessPlan(R₂) (см. п. 1.7.3).

Определение метода и порядка соединения :

3. Оценка соединения Q₁ и Q₂ методом NLJ:

в JoinPlan(Q₁, Q₂) (см. п. 1.7.4).

4. Оценка соединения Q₁ и Q₂ методом SMJ:

в JoinPlan(Q₁, Q₂) (см. п. 1.7.4).

5. Выбор метода соединения Q₁ и Q₂ и заполнение структуры:

в JoinPlan(Q₁, Q₂) (см. п. 1.7.4).

6. Оценка и выбор метода соединения Q₂ и Q₁(по аналогии с

пунктами 3 - 4), сравнение вариантов:

JoinPlan(Q₂, Q₁) (см. п. 1.7.4).

Вывод оптимального физического плана:

7. Вывод физического плана:

OptPlanReturn({Q₁, Q₂}) (см. п. 1.7.5).

8. Представление физического плана в графическом виде.

Определение метода выбора записей из исходной таблицы R1

Алгоритм AccessPlan (см. п. 1.7.3) для таблицы R₁ ("Пользователь"):

1. j = 1 – чтение всей таблицы (формулы (5.4)):

2. j = 2 – использование индекса по атрибуту "код_пользователя" (формулы (5.5) и (5.6), здесь "а" – "код_пользователя"):

C = C₂ = 0,32 мс – минимальная стоимость.

C_I_/_O = C_I_/_O₂ = 0,3 мс – составляющая ввода-вывода.

(п. 1.4.4).

(п. 1.4.5).

При вычислении B(Q₁) полагаем, что число записей в блоке проекции π_R_{1.номер_счета} в 10 раз больше, чем в блоке таблицы R₁.

Заполнение структуры str[1] (п. 1.7.2):

str[1] = {{Q₁}, Ø, Ø, 0.32, 0.3, // W, X, Y, Z, ZIO

{2, 1, {2}, 2} } // V: {T(Q₁), B(Q₁), {min(T(Q₁),

// I(R₁,номер_счёта))}, k }

Определение метода выбора записей из исходной таблицы R2

Алгоритм AccessPlan (см. п. 1.7.3) для таблицы R₂ ("Счёт"):

1. j = 1 – чтение всей таблицы (формулы (5.4)):

2. j = 2 – чтения по индексу нет, так как нет индекса по атрибуту "Остаток" (см. запрос Q₂ - п. 1.8.1).

C = C₁ = 11000 мс .

C_I_/_O = C_I_/_O₁ = 10000 мс .

//При вычислении T(Q₂) вероятность принята равной 1/3, поскольку

//мощность атрибута "Остаток" в таблице R₂ неизвестна.

(см. п. 1.4.4).

(см. п. 1.4.5).

Заполнение структуры str[2] (п. 1.7.2):

str[2] ={{Q₂}, Ø, Ø, 11000, 10000, // W, X, Y, Z, ZIO

{33000, 33, {33000}, 1}} //V:{T(Q₂),B(Q₂),

//{min(T(Q₂),I(R₂,номер счёта))},k}

Оценка соединения Q1 и Q2 методом NLJ

В алгоритме динамического программирования (см. п. 1.7.1):

n = 2, i = 2, P = (Q₁, Q₂), Q_j= Q₂ (параметры трёх вложенных циклов).

В JoinPlan (Q₁, Q₂) (см. п. 1.7.4):

R = P – Q₂ = Q₁, S = Q₂, "а" – атрибут "номер_счета".

Алгоритм:

m₁= 1, m₂= 2 // номера экземпляров в структуре str, т.к.

// str[m₁=1].W= Q₁ и str[m₂=2].W= Q₂

// Оценка стоимости соединения R и S методом NLJ, i=1

// (формулы (5.8), для оценки используются данные из str[1],

// str[2] - см. пункты 1.8.3 и 1.8.4):

Оценка соединения Q1 и Q2 методом SMJ

Продолжение алгоритма JoinPlan (Q₁, Q₂) (см. п. 1.7.4):

// Оценка стоимости соединения R и S методом SMJ, i=2

// (формулы (5.9), используются данные из str[1], str[2] - см.

// пункты 1.8.3 и 1.8.4).

// Таблица Q₂ уже отсортирована по номеру счета, так как

// имеется индекс по этому атрибуту.

Выбор метода соединения Q1 и Q2 и заполнение структуры

Продолжение алгоритма JoinPlan (Q₁, Q₂) (см. п. 1.7.4):

// Стоимость соединения Q₁ и Q₂

С = min(С₁,С₂)= min(660, 340) = С₂=340 (мс) // SMJ

// Текущая стоимость плана

С = str[1].Z + str[2].Z + C = 0,32 + 11000 + 340 @11340 (мс),

// где str[1].Z и str[2].Z – стоимости выбора записей из

// исходных таблиц R₁и R₂(см. пункты 1.8.3 и 1.8.4),

// С (справа) – стоимость соединения по методу SMJ.

// Стоимость ввода/вывода

С_I_/_O = str[1].ZIO + str[2].ZIO + C_I_/_O₂ = 0,3 + 10000 + 10 ≈ 10010 (мс).

// Значения полей V структуры str[3] (формулы (5.10) в п. 1.6.4):

Заполнение структуры str[3] (п. 1.7.2):

str[3] = {{Q₁, Q₂}, {Q₁}, {Q₂}, // W, X, Y

11340, 10010, // Z, ZIO

{2, 1, {2}, 2} } // V - , B, I, k

Оценка и выбор метода соединения Q₂ и Q₁

В алгоритме динамического программирования (см. п. 1.7.1):

n = 2, i = 2, P = (Q₁, Q₂), Q_j= Q₁.

В JoinPlan (Q₂, Q₁) (см. п. 1.7.4):

R = P – Q₁ = Q₂, S = Q₁, "а" – атрибут "номер_счета".

Алгоритм:

m₁= 2, m₂= 1 // номера экземпляров в структуре str, т.к.

// str[m₁=2].W= Q₂ и str[m₂=1].W= Q₁

// Оценка стоимости соединения R и S (см. формулы пунктов 1.8.5 и

// 1.8.6)

1. NLJ, i=1

2. SMJ, i=2

// Стоимость соединения Q₂ и Q₁

С = min(С₁,С₂) = С₂= 340 (мс) // SMJ

// Текущая стоимость плана

С = str[2].Z + str[1].Z + C = 11340 (мс)

Запись str[3] не изменяется, так как старое значение str[3].Z совпадает с новым значением (C).

Вывод физического плана

Алгоритм OptPlanReturn (см. п. 1.7.5):

1. метод 2 (т.е. SMJ)

2. Q₁ = метод 2

(т.е. IndexScan(R₁, код_пользователя = 3) +

Filter (реализация проекции по номеру счета)

)

3. Q₂ = метод 1

(т.е. TableScan(R₂) +

Filter (селекция по условию остаток > 1500 и реализация

проекции по остатку и номеру счета)

)

Метод чтения записей из R₂ (чтение всех записей) является причиной высокой стоимости выполнения запроса.

На рис. 1.25 представлен разработанный оптимальный физический план в графическом виде.

Рис. 1.25. Представление физического плана в графическом виде.

Лекция 26

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

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

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

Организация блокировок.

Пример, демонстрирующий необходимость блокировки

обновляемых записей.

Существует таблица счёт:

Номер_счёта	остаток
……………	……………
100	500
……………	…………….
1001	900
……………	…………..

1-ая операция (WS1): дебет(100) и кредит (1001) – 300.

2-ая операция (WS2): кредит (100) и дебет(1001) – 150.

Если блокировки обновляемых записей нет:

Типовая процедура обновления записей в БД.

PL/SQL (Oracle).

1. CREATE PROCEDURE проводка

(номер1 IN NUMBER,

номер2 IN NUMBER,

сумма IN NUMBER) IS

1.a остаток NUMBER;

2. CURSOR курсор (номер_счёта_1 NUMBER,

номер_счёта_2 NUMBER) IS

SELECT номер_счёта, остаток

FROM _счёт

WHERE номер_счёта=номер_счёта_1 OR

номер_счёта=номер_счёта_2

FOR UPDATE OF остаток;

3. запись курсор%ROWTYPE;

4. BEGIN

5. OPEN курсор (номер1,

номер2);

6. LOOP

7. FETCH курсор INTO запись;

8. EXIT WHEN курсор%NOTFOUND

9. IF запись.номер_счёта=номер_1

THEN остаток_1=записьюостаток-сумма

ELSE остаток1=запись.остаток+сумма

END IF;

10. UPDATE счёт SET остаток=остаток1

WHERE CURRENT OF курсор;

11. END LOOP;

12. CLOSE курсор;

13. COMMIT;

14 END;

Примечание:

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

1. Эту процедуру модно добавить в качестве хранимой процедуры в DDL сценарии, сгенерированным пакетом ERWIN.

1.a. описание переменной остаток1.

2. декларативный оператор, который описывает курсор, имеющий входные параметры номер_счёта_1 и номер_счёта_2. В курсоре определяется оператор SELECT для обновления читаемых записей (FOR UPDATE).

3. Декларативный оператор, который строит переменную запись, состоящий из полей номер_счёта и остаток.

4. Начало исполнительной части процедуры.

5. Открываем курсор. После подстановки параметров оператор SELECT автоматически передается на сервер БД и там выполняется. Результаты поиска возвращается обратно в процедуру в виду множества записей курсора.

6-11 обработка записей курсора.

6. Начать цикл.

7. Переслать очередную запись курсора в переменную «запись».

8. Выйти из цикла, если все записи курсора обработаны.

9. Условный оператор, который определяет новое значение остатка в переменной «остаток1».

10. Обновляет текущую запись курсора в БД. После постановки параметров этот оператор UPDATE передается на сервер БД и там выполняется

11. Завершает цикл, начатый в п. 6

12. Закрыть курсор. После этого записи курсора становятся недоступны.

13. Разблокируются все заблокированные записи и завершается транзакция.

14. Завершить описание процедуры.

Схема блокировки и обновление записей при одновременном обращении и процедуре «проводка»

WS1, проводка (100,1001,300)

WS2, проводка (WS1,100,150)

Оператор процедуры

Действия ядра СУБД

Оператор процедуры

Действия ядра СУБД

OPEN

Выполняется SELECT и найденные записи 100 и 1001 блокируются

OPEN

Оператор SELECT переводится в состояние ожидания, т.к. записи 1001 и 100 уже заблокированы

UPDATE

Обновляется сегмент отката, сама БД не обновляется

№ счета	100	1001
Остаток	200	1200

Состояние ожидания

COMMIT

Записи и сегмента отката переписываются в БД.

Счет

№ счета	100	1001
Остаток	200	1200

Записи 100 и 1001 разблокируются.

Выполняется оператор SELECT (т.к. записи 100 и 1001 разблокированы). При этом записи 100 и 1001 вновь блокируются. При поиске используется обновленная таблица «Счет».

UPDATE

Обновляются записи сегмента отказа. Записи в БД не обновляются

№ счета	100	1001
Остаток	350	1050

COMMIT

Записи из сегмента отката переписываются в БД

Счет

№ счета	100	1001
Остаток	350	1050

Записи 100 и 1001 разблокируются.

По оператору UPDATE обновленные записи видны только клиенту, который делает этот оператор UPDATE. Другие клиенты не видят их. Эти изменения становятся доступными другим клиентами после выполнения оператора COMMIT.

Ведение транзакций

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

Лекция 2

Ведение транзакций

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

Ведение транзакции обеспечивает атомарное действие.

Иллюстрация необходимости ведения транзакций

Обозначения:

t1 – чтение блоков с остатками в общесистемный буфер;

t2 – обновление остатков в общесистемном буфере;

t3 – начало перезаписи «грязных» блоков на диск (эта процедура автоматически запускается

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

«грязными» блоками, т.е. нет пустых блоков);

t6 – предполагаемый момент перезаписи «грязных» блоков на диск;

t4 – момент перезаписи блока с остатком «200» на диск;

t5 – момент зависания системы (блок с остатком «1200» не успел записаться на диск);

t7 – момент перезагрузки сервера БД. Здесь наблюдается нарушение целостности БД.

Схема ведения транзакции

Пусть выполняется 2 процесса:

Пусть процесс1 осуществляет обновление записей в БД (UPDATE).

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

По оператору COMMIT выполняются следующие действия:

1. Записи после обновления переписываются из сегмента отката в общесистемный буфер (ОСБ). Они становятся доступными для других клиентов. В заголовок обновлённой записи помещаются время её обновления, это необходимо для ведения версий записей (см. ниже)

Записи после обновления записываются также в журнал транзакций. Если журнал транзакции на диске1 переполняется, то система переключается на журнал транзакций на диске2. (Журналы транзакции всегда имеют фиксированный объём). При этом журнал на диске1 закрывается. Если в СУБД установлена специальная опция, то СУБД автоматически запускает процедуру архивации журнала на диске1 на внешний носитель большой ёмкости. Важно, чтобы время перезаписи журнала на диске1 должно быть меньше времени заполнения журнала на диске2.

По оператору COMMIT записи из сегмента отката удаляются не сразу. Это связано с ведением версий записи.

Версии записей (блокировка по чтение)

Эта схема обеспечивает целостность отчёта.

Рассмотрим процесс чтения - обеспечивает целостность чтения данных на интервале r1-r2. При чтении записей по оператору SELECT сравниваются время начала выполнения оператора r1 со временем обновления записей (tобн).

Если r1 > tобн., то запись читается из ОСБ, т.е. используется последняя версия записи.

Если r1 < tобн., то читается старая (до обновления) запись из сегмента отката. Это и есть блокировка по чтению.

Примечания:

1. Блокировка по обновлению действует до завершения транзакции (до COMMIT).

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

Схема восстановления данных после сбоя.

Полная транзакция записывается в журнал транзакций по оператору COMMIT.

После перезаписи всех «грязных» блоков ОСБ на диск, в журнале транзакций появляется соответствующая отметка (см* ). Для каждой транзакции в журнале отката сохраняются записи до и после обновления. Они сохраняются до завершения транзакции.

После сбоя и перезапуска сервера БД, система пытается автоматически восстановить потерянные данные и обеспечить их целостность. При этом выполняется:

Докат БД : СУБД ищет последнюю временную отметку о перезагрузке «грязных блоков» на диск (см*).И начиная с этой отметки до конца журнала транзакций, читаются записи полных транзакций и перезаписываются в таблицы БД.
Откат незавершенных транзакций : В таблицах БД могли появится записи незавершенных транзакций. Это обычно связано с перезаписью «грязных» блоков на диск (система перезаписала «грязные» данные на диск, а транзакция ещё не завершилась) Чтобы отчистить БД от записей незавершенных транзакций, в сегменте отката выполняется поиск незавершенных транзакций и восстанавливаются в БД записи до обновления с конца транзакции до её начала.

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

Здесь только докат, отката нет, т.к. нет незавершенных транзакций.

Перезапись «грязных» блоков ОСБ на диск производится в следующей последовательности:

Сначала перезаписывается буфер сегмента отката.
Далее перезаписывается буфер журнала транзакций.
В конце перезаписывается буфер БД.

Лекция 28

Обработка тупиковых ситуаций

Предположим, что процедура «проводка» (см. предыдущую лекцию) реализована несколько по-другому:

Проводка (счёт1, счёт2, сумма)

2 оператора.

UPDATE … счёт1

Пример: UPDATE счёт SET остаток = остаток - сумма

WHERE номер_счёта=счёт1;

UPDATE … счёт2

COMMIT

Пусть к этой процедуре одновременно обращаются две рабочие станции

WS1 WS2

Проводка (100, 1001, 300) проводка (1001, 100, 150)

процесс 1 процесс 2

UPDATE … 100 UPDATE … 1001

(соответствующая запись (запись с этим номером счёта

блокируется до конца транзакции, также блокируется до COMMIT)

т.е. до оператора COMMIT)

UPDATE … 1001 UPDATE … 100

(ждёт разблокировки записи (процесс 2 приостанавливается и

процессом 2) ожидает разблокировки со стороны

процесса 1)

Возникает тупиковая ситуация.

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

Либо выполнить ROLLBACK (выполняется откат транзакции, и записи разблокируются);
Задача очень важная, и её нельзя завершить. Здесь должен быть предусмотрен вывод сообщений оператору с указанием снять задачу, которая мешает выполнению данной задачи, далее по реакции оператора продолжить выполнение задачи.

Выбор архитектуры тестируемой системы обработки данных

При выборе архитектуры решаются следующие задачи:

1) Выбирается модель доступа к данным;

2) Выбираются общесистемные пакеты (то, что покупается, а не разрабатывается в рамках данного проекта);

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

4) Определяется метод репликации (тиражирования данных).

Модель доступа к данным

В настоящее время в основном используются следующие модели:

1) модель файлового сервера

2) модель сервера БД

3) модель сервера приложений

4) модель доступа к данным по технологии Intranet/Internet

5) CORBA/DCOM

1. Модель файлового сервера

Бизнес-правила – логика предметной области.

Предположим, пользователь щёлкает по кнопке. Запускается скрипт (прикладная программа), обрабатывающая соответствующее событие. Если при выполнении прикладных программ выполняется соответствующий оператор, он передаётся в ядро СУБД. СУБД выполняет разбор SQL-оператора и обращается к файлам БД, откуда читаются блоки индексов, блоки сортировки, блоки записей таблиц. После выполнения SQL-оператора результаты передаются в прикладную программу, которая обрабатывает их, и результаты обработки в виде формы отображаются на экране.

Файловый сервер служит как разделяемый удалённый диск.

СУБД, поддерживающие данную модель:

1. dBase(Borland)

2. CA-Clipper (CAI)

3. FoxPro (Microsoft)

4. Paradox (Borland)

5. Access (Microsoft)

Преимущества модели файлового сервера:

+: эти продукты дёшевы, просты в освоении;

+: реализация прикладной ОС не зависит от сетевой ОС, так как эта ОС используется только для организации доступа к файлам БД.

Недостатки модели файлового сервера

-: эти системы сильно перегружают шину ЛВС, так как по шине передаются не только блоки таблиц, но и промежуточные данные (индексы, данные сортировки и т.д.)

В данной модели файловый сервер как удалённый разделяемый диск.

-: данная модель не поддерживает распределённую обработку.

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

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

-: в этой модели блокировки записей БД и ведение транзакций реализуются средствами сетевой ОС.

2. Модель сервера БД

Сервер БД - процесс ОС, имеющий свой порт.

Предположим, пользователь щёлкает по кнопке, на рабочей станции (WS) вызывается программа обработки событий. Если при её выполнении встречается SQL-оператор, то он не выполняется на рабочей станции и передаётся на сервер БД и выполняется ядром СУБД. Ядро разбивает SQL-оператор и обращается к требуемым файлам по шине PCI. После выполнения SQL-оператора результаты возвращаются в прикладную программу, выдавшую запрос, та их обрабатывает и отображает их в виде формы на экране.

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

Триггеры – это программы, к которым обращается ядро СУБД до, и/или после обрабатывания записи в таблице.

Условия срабатывания триггера определяет программист. В теле триггера может быть вызвана хранимая процедура.

Хранимые процедуры – это прикладные программы, являющиеся расширением ядра. В теле хранимой процедуры можно кодировать обращение к СУБД и к хранимым процедурам. К хранимым процедурам можно обращаться и с рабочих станций, и с помощью RPC (Remote Procedure Control).

Основные СУБД данного типа:

1. Oracle

2. MS SQL Server

3. SyBase

4. Informix

5. InterBase

6. Centura

Преимущества модели сервера базы данных:

Система, разработанная на основе этой модели, имеет большую производительность, чем в случае модели файлового сервера (по шине передаются только SQL-операторы и результаты выполнения SQL-операторов, все промежуточные данные передаются по PCI);
Эти СУБД поддерживают распределённую обработку (используется оптимизация SQL-запросов, т.е. выделяются подзапросы, которые могут автоматически выполняться на разных серверах);
В рамках этих СУБД поставляются большое число сервисных продуктов, облегчающих работу с СУБД;
Ядро СУБД общее для всех рабочих станций.

Недостатки модели сервера базы данных::

Эти СУБД намного дороже СУБД предыдущего класса;
В силу большого объёма документации СУБД сложнее в освоении, поэтому необходимо наличие квалифицированных администраторов;
Так как ядро общее, необходим мощный сервер;
Для того чтобы проявились преимущества оптимизации SQL-запросов, необходимо наличие в сети нескольких серверов баз данных.

Лекция 29

3. Модель сервера приложений

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

Примеры:

1) Tuxedo (BEA System)

2) CICS (IBM)

3) SQL Server (Microsoft)

Преимущества модели сервера приложнгий

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

ü При увеличении нагрузки на сервис сервер приложений может автоматически запустить копию этого сервиса на другом сервере приложений и тем самым снизить нагрузку на текущий сервис.

ü Сервис приложений может выступать в качестве маршрутизатора запросов к сервисам (все зависит от исходных данных)

ü Данная модель позволяет снизить число лицензий на сервер БД.

Недостатки модели сервера приложений:

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

4 Модель доступа к данным по технологии internet/intranet

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

Доступ к данным из CGI, API программ
Доступ к данным из Java-апплетов или управляющих элементов ActiveX

Доступ к данным из CGI, API программ

По url читается HTML форма, она интерпретируется и на экране появляется web-страница с полями/формами. На сервер передается имя CGI программы и значения заполненных полей. На web-сервере запускаются соответствующие CGI программы (как задача ОС). Если при выполнении этой программы встречается SQL-оператор, то он через ODBC интерфейс передается на локальный сервер БД либо на удаленный сервер. Результат выполнения SQL-оператора выполняется в CGI программе, она его обрабатывает и с помощью команды print генерирует html-программу (в нее включаются результаты поиска в БД). Эта html-программа возвращается на рабочую станцию, там интерпретируется и отображается на экране.

Преимущества CGI:

ü Web-сервер выступает в качестве сервера приложения (администрирование выполняется централизованно).

ü CGI интерфейс унифицирован и реализован во всех серверах.

ü Для доступа к БД можно использовать любой web-браузер.

Недостатки:

ü Каждая CGI программа выполняется как процесс ОС. Инициализация задачи ОС и переключение между ними занимает очень много времени, т.к. требуется переключение между блоками управления страницами.

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

ü Генерируемая форма имеет небольшие выразительные возможности.

Для устранения 1-го недостатка в настоящее время используют API-интерфейсы, например ASP, PHP, JSP. API программы выполняются как отдельные потоки, но в рамках задачи web-сервера, т.е. в рамках одной задачи ОС.

Преимущества API:

ü Они выполняются быстрее, чем CGI программы (нет переключения между задачами ОС).

ü ASP вместе с некоторыми дополнениями (Remote scripting, scriptlet) позволяют поддерживать контекст с БД

Недостатки:

ü API программы разных производителей не совместимы между собой

ü API интерфейсы и соответствующие API программы зависят от платформы

Доступ к данным из Java-апплетов и ActiveX.

Если при интерпретации html документа встречается тег <applet>, то браузер обращается к web-серверу с запросом на чтение java-программы (1). Затем java-программа передается на рабочую станцию и там интерпретируется java-машиной (2). Если в процессе выполнения java-программы встречается SQL-оператор, то он через интерфейс JDBC-ODBC передается на удаленный сервер БД и там выполняется (3). Результаты возвращаются обратно в java-программу, там обрабатываются и java-программа выводит их в web-страницу.

Преимущества:

ü Эта технология позволяет существенно разгрузить web-сервер, т.к. java-аплеты выполняются на рабочих станциях.

ü Java-апплеты мобильны. Язык java достаточно гибкий для создания сложных программ.

ü JDBC является универсальным интерфейсом. Язык SQL не зависит от СУБД.

ü Существует множество java-программ, которые можно использовать. Их можно запускать с различных серверов и связывать на рабочей станции.

Недостатки:

ü Размеры java-апплетов должны быть небольшими. Это связано с ограничением времени передачи по сети.

ü Низкая производительность java-программ.

ü Относительная сложность разработки java-апплетов, выполняющих доступ к БД.

Лекция 30

Обращение к БД из элементов Active X.

Обращение к управляющему элементу Active X осуществляется из тега <object>. В свою очередь, в этот управляющий элемент могут быть включены SQL-операторы, которые обращаются к удаленной базе данных. Элементы Active X могут динамически подкачиваться на рабочие станции ( по аналогии с java апплетами ).

Преимущества:

В отличие от java апплетов в Active X выполняется бинарный код, а значит, они выполняются быстрее

Недостатки:

Эта технология продвигается Microsoft и работает только на платформе Wintel/

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

В настоящее время используются 2 метода:

1. шлюзы

2. ODBC – интерфейс или его аналоги ( ADO.NET )

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

с помощью шлюзов.

Предположим, на станции 1- Informix установлен сервер, а на 2-й – Oracle.

Организация доступа приложения Oracle к Informix серверу:

Если при выполнении Oracle-приложения встречается SQL оператор, то он передается на сервер Oracle(1). Если требуемые таблицы хранятся на этом сервере, то SQL оператор выполняется. Если требуемые таблицы хранятся на Informix сервере, то Oracle сервер передает SQL оператор на сервер Informix(2). Этот оператор выполняется на сервере Informix и по обратной цепочке(2 – 1),результаты возвращаются в приложение Oracle.

По аналогии осуществляется доступ приложений Informix к таблицам Oracle (3 – 4).

Соответствующие шлюзы (см * и **) разработаны фирмой Oracle и Informix.

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

с помощью ODBC интерфейса.

Схема реализации ODBC интерфейса:

Если при выполнении Windows – приложения встречается SQL – оператор, то происходит автоматическое обращение к менеджеру драйверов, который выбирает соответствующий ODBC драйвер и через него SQL оператор передается на требуемый сервер и там выполняется.

Организация доступа Windows приложений к менеджеру драйверов.

С помощью функции SQL_CONNECT приложение подключается к конкретному серверу БД (с помощью нескольких операторов приложение может подключатся к нескольким серверам) – в этом реализуется интероперабельность.
В строковой переменной подготавливается SQL оператор (может быть динамическим и статическим)
С помощью функции SQL_EXECUTE осуществляется выполнение SQL оператора. В качестве параметра этой функции используется указатель на строковую переменную. Эта функция первоначально обращается к менеджеру драйверов.
Предыдущая функция ( в общем случае, возвращает множество записей, удовлетворяющих условию поиска. Поэтому в Windows приложении организуется цикл и в нем с помощью функции SQL_FETCH выбирается очередная запись и она обрабатывается ( и так по всему циклу ).

Тиражирование данных в распределенной системе обработки данных.

Пример, демонстрирующий необходимость тиражирования данных.

Предположим, что в Москве функционирует фондовая биржа, и в Санкт-Петербурге.

Под тиражированием понимается автоматическое копирование измененных данных с одного сервера на другой. Тиражирование имеет 2 существенных преимущества:

увеличивается производительность системы ( пользователям ПФБ для получения котировок ценных бумаг в МФБ достаточно обратится к своему серверу в Санкт-Петербурге. )
увеличивается надежность ( если по каким то причинам сервер 2 недоступен, то пользователи ПФБ могут читать котировки ценных бумаг с сервера 1 ).

Классификация способов тиражирования.

Тиражирование на основе снимков.

Рассмотрим тиражирование на основе снимков на примере Oracle ( хотя эти идеи справедливы и для других СУБД ).

Спецификация описания канала связи с узлами БД и снимков.

Все это описывается в DDL – сценарии и создается в виде объектов.

Канал связи

CREATE DATABASE LINK имя_канала

CONNECT TO имя_пользователя

IDENTIFIED BY пароль

USING спецификация удаленной БД ( подробно см SQL . NET )

Примечание: здесь имя_пользователя – это имя, по которому Сервер 2 будет подключаться к Серверу 1 при выполнении тиражирования.

Снимок

CREATE SNAPSHOT имя_снимка

REFRESH 2 варианта:

FAST – читать только обновленные данные

COMPLETE – выполнить полностью, т.е. читать всю таблицу А с сервера 1 на сервер 2.

NEXT Sydate+7 ( указывается когда и как будет обновляться ) – снимок на сервере будет обновляться каждые 7 дней с даты создания соответствующего объекта SNAPSHOT.

AS SELECT * FROM имя_пользователя.А.@имя_канала

Указывается оператор select, по которому будет выполнятся чтение данных. Это оператор select? Который автоматически посылается с Сервера 2 на сервер 1 по запросу тиражирования, т.е. каждые 7 дней.

Синхронная и асинхронная репликация.

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

Пример организации реплицирующей транзакции в прикладной программе ( или хранимой процедуре ).

COMMIT – завершает предыдущую транзакцию и автоматически начинает новую.

……….

Изменения в БД 1

……….

Те же изменения в БД 2

……….

COMMIT

При синхронизации репликации фиксация изменений по оператору COMMIT выполняется в 2 фазы:

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

Таким образом, описанный выше метод называется методом 2-х фазной фиксации. По этому методу репликация работает по принципу – “изменения на всех серверах, либо никаких изменений” .

Недостатки:

- сбой на вторичном сервере приостанавливает изменения на всех остальных серверах.

- сервер ответил, что готов принять изменения, а потом до COMMIT завис => серверу надо или COMMIT или ROLLBACK. Для этого существует отметка для ЦЫ узнать, что сделал сервер. При асинхронной репликации изменения передаются на серверы по мере готовности этих серверов. Если какой-либо сервер не готов принять изменения, то они сохраняются на исходном сервере и будут переданы по назначению, когда требуемый сервер будет готов принять эти изменения.

Асинхронная репликация на уровне записей без конфликтов.

Предположим на клиенте выполняется операция HT ( может быть оператор COMMIT). Все изменения в БД фиксируются в журнале изменений.

По команде HT выполняются следующие действия :

запускается менеджер журнала транзакций, который читает записи журнала транзакций после обновления из журнала изменений.
Эти записи передаются репликационному серверу ( задача ОС ).
Репликационный сервер для каждой записи транзакции по имени таблицы и значению ключа записи определяет соответствующую строку в таблице публикации ( для данного примера будет найдена 1 строка таблицы публикации )
Из таблицы подписка определяется имена серверов, которые ссылаются на данную публикацию ( в данном примере это Сервер 2 ). Данная запись тиражируется на этот ( найденный ) сервер.

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

1. Тиражирование из первичного сервера – серверы, где разрешаются модифицирование.

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

Все изменения тиражируются с первичного сервера на вторичные в соответствии с публикациями.

Этот метод имеет следующие преимущества:

1. Позволяется избежать дублирований и зацикливания ( при нескольких первичных серверах существует опасность зацикливания ).

Данной проблемы можно избежать, если обновление снабдить временной меткой. Тогда обновления разрешаются если

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

Примечание: данный метод репликации реализован практически во всех СУБД.

Тиражирование из первичного сервера или его резерва.

Резервный первичный сервер работает в режиме “горячего” резервирования первичного сервера. Он отслеживает состояние и ОП, и внешней памяти первичного сервера. Резервный сервер периодически опрашивает первичный сервер по спец кабелю. Если при очередном опросе первичный сервер не отвечает, то РПС считает что опрашиваемый сервер вышел из строя и начинает обрабатывать поступающие на его сетевой адаптер кадры.

Примечание: MAC адреса сетевых адаптеров первичного сервера и его резерва совпадают, при этом обе платы работают на прием, но передавать выходные данные может только одна из сетевых плат. Т.е. когда резервный сервер обнаруживает неисправность первичного, то он берет обработку на себя ( т.е. его сетевая плата начинает работать не только на прием, но и на выход ). При этом резервный сервер продолжает определять первичный сервер. И если при очередном опросе первичный сервер отвечает ( после его ремонта ) , то инициализируется процедура выравнивания состояния ОП и внешней памяти первичного и резервного серверов. После этого обработку на себя берет первичный сервер, т.е. плата этого сервера начинает работать на выход. Далее процесс работы ( функционирования ) системы продолжается в штатном режиме.

Преимущества: увеличивается надежность системы при аппаратном сбое.

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

Пример “+” :

В США в рухнувших башнях финансового краха не произошло, т.к. там был такой режим.

Пример “-” :

Космический корабль рухнул. Там было даже тройное резервирование. Но если сначала

Поточная модель тиражирования данных.

Здесь статусы первичного и вторичного серверов могут меняться.

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

Предполагаем что основной поток изменений в таблице связан с WS, подключенными к вторичному серверу Санкт-Петербурга. В этом случае изменения во вторичной таблице происходят в след. последовательности:

В этом случае нагрузка на LAN сеть Санкт-Пертербурга состоит из 3λ, а на WAN сеть из 2λ. Если статус вторичного сервера изменить на первичный, то нагрузка на сеть резко уменьшается.

Из рисунка видно, что нагрузка на LAN сеть уменьшается до 2λ, а на WAN сеть до λ

Иерархическая модель тиражирования с использованием репликационного сервера.

Схема тиражирования без репликационного сервера.

Если бы не было репликационного сервера, то в этом случае трафик по низкоскоростной теле коммуникационной сети возрос в n раз. Это связано с тем, что первичный сервер связывается с вторичным по технологии point-to-point.

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

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

На WS происходит обращение к хранимой процедуре обновления. Эта процедура на сервере БД2 имеет пустое тело ( т.е. вход и return ) . Но на сервере БД2 выполнена подписка сервера 1 на процедуру обновления. Поэтому эта процедура будет автоматически запущена на сервере БД1. Но процедура обновления на сервере БД1 не является пустой и содержит в себе операторы обновления таблиц. С помощью этих операторов осуществляется обновление таблиц котировок. Но на сервере БД1 выполнена подписка сервера БД2 на соответствующие изменения. В соответствии с этой подпиской изменения ( данные ) реплицируются с сервера БД1 на сервер БД2.

Асинхронная пакетная репликация.

Включает несколько шагов:

На удаленном первичном сервере администратором создаются скрипты с описанием снимков.
Эти скрипты рассылаются на серверы – подписчики ( обычно в ночное время ).
Данные скрипты автоматически запускаются на серверах – подписчиках и выполняют обновление снимков на этих серверах.

Алгоритм построения ключа (основывается на определении ключа)

Пример построения ключа

Пример доказательства, что схема отношения не находится в 3НФ

Пример доказательства, что схема отношения находится в 3НФ

Алгоритм построения «хорошей» схемы БД

Элементы теории формальных языков

Определения

Пример построения итерации алфавита А

Определение грамматики

Пример грамматики

Язык, описываемый грамматикой

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

Синтаксические деревья

Нисходящие распознаватели

Левосторонняя и правосторонняя рекурсия

Способы устранения левосторонней рекурсии

Общие правила (рекомендации) для разработки нисходящих распознавателей.

Восходящие распознаватели

Восходящие распознаватели - это транслятор, которое строит синтаксическое дерево сверху- вниз.

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

Основы оптимизации SQL-запросов

Оптимизация SQL-запросов

используемые законы реляционной алгебры

Основные шаги оптимизации

Преобразование запроса в формулу реляционной алгебры

Оптимизация формулы реляционной алгебры

Отличие физического плана от логического

Оценка числа кортежей в промежуточной таблице Q

Оценка числа блоков в промежуточной таблице Q

Левостороннее дерево соединений

Метод вложенных циклов (NLJ – Nested Loop Join)

Метод сортировки-слияния (SMJ – Sort Merge Join)

Метод хешированного соединения (HJ – Hash Join)

Спецификации процедуры AccessPlan

Спецификации процедуры JoinPlan

Спецификации процедуры OptPlanReturn

Определение метода выбора записей из исходной таблицы R1

Определение метода выбора записей из исходной таблицы R2

Оценка соединения Q1 и Q2 методом NLJ

Оценка соединения Q1 и Q2 методом SMJ

Выбор метода соединения Q1 и Q2 и заполнение структуры

Оценка и выбор метода соединения Q2 и Q1

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

Организация блокировок.

Пример, демонстрирующий необходимость блокировки

обновляемых записей.

Типовая процедура обновления записей в БД.

Оценка и выбор метода соединения Q₂ и Q₁