ИОСУ лекции (мои)

«ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ СИСТЕМ УПРАВЛЕНИЯ»
1. Общие понятия ИО

Предметом настоящего курса являются информационные системы, базы данных и системы управления базами данных. Это очень важная область, определяющая характер революции в информационных системах.
С начала развития вычислительной техники образовались два основных направления ее использования. Первое направление – применение вычислительной техники для выполнения численных расчетов, которые слишком долго или вообще невозможно производить вручную. Становление этого направления способствовало интенсификации методов численного решения сложных математических задач, развитию класса языков программирования, ориентированных на удобную запись численных алгоритмов, становлению обратной связи с разработчиками новых архитектур ЭВМ.
Второе направление – это использование средств вычислительной техники в автоматических или автоматизированных информационных системах. В самом широком смысле информационная система представляет собой программный комплекс, предназначенный для надежного хранения информации, выполнения специфических для данного приложения преобразований информации и вычислений, предоставлении пользователям удобного и легко осваиваемого (дружелюбного) интерфейса. Обычно объемы информации, с которыми приходится иметь дело таким системам, достаточно велики, а сама информация имеет достаточно сложную структуру. Классическими примерами информационных систем в гражданской сфере являются банковские системы, системы резервирования авиационных или железнодорожных билетов, мест в гостиницах и т.д.
Для обеспечения гибкости использования данных необходимо учитывать два аспекта разработки баз данных:
- во-первых, данные должны быть независимы от использующих их программ, чтобы данные можно было добавлять или перестраивать без изменения программ;
- во-вторых, должна быть обеспечена возможность запрашивать и отыскивать информацию в базе данных без трудоемкого написания программ на обычном языке программирования.
Таким образом, проектирование баз данных основывается на вполне определенной системе положений – четко сформулированной концепции.
Информационные системы – системы обработки данных о какой-либо предметной области со средствами накопления, хранения, обновления, поиска и выдачи данных.
Данные - информация (факты и идеи), представленная в формализованном виде, позволяющем передавать или обрабатывать ее при помощи некоторого процесса (и соответствующих технических средств).
Информационное обеспечение – совокупность данных и средств работы с ними, предназначенных для поддержки какого-либо вида деятельности или функционирования какого-либо объекта.
Для работы с хранимыми данными существуют две основные формы:
1) Файловые системы (ФС)
Виды взаимосвязей данных и программ:
1. Программа и данные в одной куче.
13 SHAPE \* MERGEFORMAT 1415
2. Данные как попало (отдельно от программы)
13 SHAPE \* MERGEFORMAT 1415
3.
13 SHAPE \* MERGEFORMAT 1415


Файловая система – набор прикладных программ (приложений), выполняющих обработку данных, каждая из которых самостоятельно хранит свои собственные данные и управляет ими.
Недостатки:
– несовместимость форматов
– изолированность и разделенность данных
– дублирование данных
– фиксированный набор запросов
– проблемы с размерами полей
2) Системы, использующие БД
База данных (БД) - именованная совокупность данных, отображающих состояние объектов и их отношений в рассматриваемой предметной области. Организуется так, что данные собираются однажды и централизованно хранятся (и модифицируются) в виде, доступном всем специалистам или системам программирования, которые могут их использовать.
Системы, использующие БД, можно разделить на информационные системы и информационные подсистемы.
Информационная система для пользователя автономна, существует интерактивный интерфейс.
Информационная подсистема – одна из частей более глобальных системы. Обеспечивает информацией другие подсистемы.
13 EMBED Visio.Drawing.11 1415
В информационной системе реализуется интерфейс с человеком-пользователем. В подсистеме же реализуется программный интерфейс (API). Подсистема может быть дополнена интерфейсом с пользователем с целью модификации данных для дальнейшего автоматического использования.
Одна из важных черт БД – независимость данных от особенностей прикладных программ, которые их используют, а также возможность создания этих программ в такой форме, что изменение особенностей хранения, логической структуры или значений данных не требует изменения программ их обработки. Другой важной чертой БД является возможность изменения физических особенностей хранения данных без изменения их логической структуры.
Таким образом, приложение “не знает” форматы данных, все делает СУБД.
Если не будут меняться форматы данных и т.д., если не будем использовать несколько программ, в этом случае лучше использовать ФС.
СУБД же используется там, где необходима универсальность.
Соответственно двум понятиям – «информация» и «данные» – в базах данных различают два аспекта рассмотрения вопросов: инфологический и даталогический.
Инфологических аспект употребляется при рассмотрении вопросов, связанных со смысловым содержанием данных независимо от способов их представления в памяти системы.
Даталогический аспект употребляется при рассмотрении вопросов представления данных в памяти информационной системы.
Данные соответствуют зарегистрированным фактам об объектах реального мира. Чтобы в дальнейшем использовать эти данные, требуется их смысловое содержание – семантика данных. Поэтому в информационной системе должны быть сформулированы правила смысловой интерпретации данных.
БД делятся:
1) по размещению:
– локальные – на машине пользователя. Одна база, одна программа
Плюсы:
Простой доступ к базе
Минусы:
Однопользовательский режим
Простота несанкционированного доступа
– интегрированные – для обслуживания группы пользователей в рамках подразделения, предприятия. Используется файл-серверная (клиент-серверная) организация.
Плюсы:
Простота обмена информацией между пользователями
Возможность параллельной работы пользователей
Минусы:
Необходимость повышения надежности, разрешения конфликтов между пользователями, разделение доступа к данным
Замедление в скорости получения данных
– распределенные – база распределена по системе, но едина логически. Физически хранятся на удаленных компьютере для приближения данных к пользователю.
Плюсы:
Увеличение скорости работы для локальных задач
Улучшение защиты от несанкционированного доступа
Минусы:
Усложнение организации
Замедление решения глобальных задач
2) по виду модели данных:
– иерархические – масса недостатков, устарела
– сетевые – масса недостатков, устарела
– реляционные – подавляющее большинство на сегодняшний день
– постреляционные – начинают внедряться, расширяют возможности реляционных, добавляя расширение или используя объектно-ориентированный подход.
Система управления базами данных – совокупность языковых и программных средств, предназначенных для создания, ведения и конкурентного использования базы данных многими пользователями.
Создание и применение СУБД призвано к максимальному удовлетворению требований, предъявляемых к эффективным базам данных. Это приводит к необходимости решения вопроса централизованного управления данными.
Специальные средства СУБД обеспечивают секретность данных, т.е. защиту данных от неправомочного воздействия, и целостность данных – защиту от непредсказуемого взаимодействия конкурирующих процессов, приводящих к случайному или преднамеренному разрушению данных, а также от отказов оборудования.
Операции, выполняемые СУБД:
– работа с данными (выборка, добавление, изменение и т.д.)
– служебные операции с данными (защита от несанкционированного доступа, защита от конфликтов многопользовательского доступа, восстановление и резервирование данных, архивирование и т.д.)
СУБД разделяются:
1) по размещению:
– персональные – размещаются на компьютере пользователя, и обслуживают только его.
– серверные – размещаются на серверах и обслуживают несколько пользователей.
2) по виду моделей: так же, как и для БД, то есть:
– иерархические – масса недостатков, устарела
– сетевые – масса недостатков, устарела
– реляционные – подавляющее большинство на сегодняшний день
– объектные – считаются прогрессивными.
Приложение – разрабатывается под конкретную задачу.
Программа и СУБД – это программное обеспечение, но СУБД – это универсальная программа.
ИС отличаются по архитектуре ПО.
Все ПО можно разделить на три основные компоненты:
- компонент представления (П).
- компонент обработки (О).
- компонент доступа (Д) – поддержка операций работы с БД.
В зависимости от размещения программного обеспечения различаются несколько моделей информационных систем:

13 EMBED Visio.Drawing.6 1415

1. Локальная модель системы. Все находится на одном компьютере пользователя.
Плюс: все данные на одном компьютере, следовательно, быстрота работы.
Минус: однопользовательский режим доступа.
2. FS – файл-серверная модель.
Особенности:
- обеспечение одновременного доступа, следовательно, блокировка данных на время работы с ними.
- ПО на машине клиента, следовательно, все компьютеры должны быть мощными.
- сервер – просто хранилище информации, следовательно, трудность с типовыми операциями (поиск, изменение данных), загруженность сети.
3. RDA - Модель удаленного доступа к данным. На сервере находятся данные и ПО.
4. DBS - Сервер БД. Кроме стандартных команд обращений к базе на сервере выполняется обработка по произвольному коду в виде триггеров или процедур.
5. Main frame – все на сервере, у пользователя только дисплей.
6. AS – модель серверного приложения. Имеется два сервера: сервер СУБД и доступов к ней, сервер с приложением.
13 EMBED Visio.Drawing.11 1415

Структуры 3, 4, 6 попадают под архитектуру Клиент-сервер.
При выполнении основных функций СУБД должна использовать различные описания данных. Очевидно, что в таких описаниях обязательно должны быть учтены:
сущности интересующей предметной области;
атрибуты, характеризующие неотъемлемые свойства каждой сущности;
связи, ассоциирующие выделенные сущности.
С самых общих позиций, в архитектуре современных СУБД выделяют три уровня абстракции, т.е. три уровня описания элементов хранимых данных. Эти уровни составляют трехуровневую архитектуру, представленную на рис. 1.2, которая охватывает внешний, концептуальный и внутренний уровни. Данный подход к описанию данных предложен комитетом ANSI/SPARC (Комитет Планирования Стандартов и Норм Национального Института Стандартизации США). Такое отделение обеспечивает независимость хранимых данных.

Рис. 1.2. Трехуровневая архитектура ANSI/SPARC

Внешний уровень – представление базы данных с точки зрения конкретных пользователей.
Указанный уровень может включать несколько различных представлений БД со стороны различных групп пользователей. При этом каждый пользователь имеет дело с представлением предметной области, выраженным в наиболее понятной и удобной для него форме. Такое представление содержит только те сущности, атрибуты и связи, которые интересны ему при решении профессиональных задач.
На внешнем уровне создается инфологическая модель БД (внешняя схема), полностью независимая от платформы (т.е. вычислительной системы, на которой будет использоваться). Инфологическая модель является человеко-ориентированной: средой ее хранения может быть память человека, а не ЭВМ.
Концептуальный уровень – обобщающее представление базы данных, описывающее то, какие данные хранятся в БД, а также связи, существующие между ними.
Концептуальный уровень является промежуточным в трехуровневой архитектуре. Содержит логическую структуру всей базы данных. Фактически, это полное представление требований к данным со стороны организации, которое не зависит от соображений относительно способа их хранения. На концептуальном уровне необходимо выделить:
сущности, их атрибуты и связи;
ограничения, накладываемые на данные;
семантическую информацию о данных;
информацию о мерах обеспечения безопасности.
На концептуальном уровне создается даталогическая модель (концептуальная схема БД), представляющая собой описание инфологической модели (внешней схемы) на языке определения данных конкретной СУБД. Эта модель является компьютеро-ориентированной (зависит от применяемой на компьютере СУБД).
Внутренний уровень – физическое представление базы данных, описывающее методы их хранения в вычислительной системе.
Данный уровень описывает физическую реализацию базы данных и предназначен для достижения оптимальной производительности и обеспечения экономного использования дискового пространства. Содержит описания структур данных и отдельных файлов, используемых для хранения данных в запоминающих устройствах.
На внутреннем уровне осуществляется взаимодействие СУБД с методами доступа операционной системы с целью эффективного размещения данных на носителях, создания индексов и т.д.
Реализация перечисленного производится на физическом уровне вычислительной системы, который контролируется операционной системой. В настоящее время функции СУБД и операционной системы на физическом уровне строго не разграничиваются. В одних СУБД используются все предусмотренные в данной операционной системе методы доступа, в других применяются только основные и реализована собственная файловая система.
На внутреннем уровне создается физическая модель БД (внутренняя схема), которая также является компьютеро-ориентированной (зависит от СУБД и операционной системы). С ее помощью СУБД дает возможность программам и пользователям осуществлять доступ к хранимым данным по именам, не заботясь об их физическом расположении. По этой модели СУБД отыскивает необходимые данные на внешних запоминающих устройствах.

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

2. Жизненный цикл ИО, проектирование ИО
Жизненный цикл – интервал от принятия решения о создании системы до момента снятия её с эксплуатации.
Рассмотрение вопросов проектирования эффективных баз данных целесообразно начать с обзора жизненного цикла автоматизированных информационных систем.
Типичная автоматизированная информационная система включает следующие компоненты [7].
База данных.
Программное обеспечение базы данных.
Прикладное программное обеспечение.
Аппаратное обеспечение, в том числе устройства хранения.
Персонал, использующий и разрабатывающий систему.
База данных является фундаментальным компонентом информационной системы, а ее разработку и использование следует рассматривать с точки зрения самых широких требований организации. Таким образом, жизненный цикл ИС неотъемлемо связан с жизненным циклом лежащей в основе базы данных.
Жизненный цикл любой сложной системы и, безусловно, ИС, основанной на базе данных, обычно состоит из нескольких этапов:
Состоит из стадий:
1) Анализ: обследование объекта автоматизации.
Определение состава информации, необходимого для деятельности
Определяется состав, функции системы
Выбирается концепция построения системы
2) Проектирование:
а) Данные: может выполняться последовательность шагов.
инфологическое проектирование – определение состава и структуры информации.
даталогическое проектирование – определение состава и структуры данных.
физическое проектирование: реализация в конкретном формате.
внешнее проектирование: указывается определенному пользователю работа с конкретными таблицами; разграничение доступа к БД, в зависимости от пользователя.
б) Программное обеспечение:
функциональное моделирование системы
определение структуры ПО
определение диалогов с пользователем и с внешней средой
спецификации программных модулей
в) Комплекс технических средств (КТС):
определение технической структуры
выбор технических средств
г) Организационные вопросы: работа с людьми.
определение организационной структуры
планирование обучения и поддержки персонала
3) Реализация:
реализация структуры базы
заполнение отладочной информации
реализация и отладка ПО или конфигурирование и настройка
реализуется КТС
проводится интегрированная отладка
создание организационной структуры
обучение персонала
4) Эксплуатация:
ввод, актуализация и использование данных
контроль доступа
контроль за использованием данных: пользователю с данными работать можно, но идет запись действий пользователя
контроль целостности данных: сбойные, аварийные ситуации
модернизация и развитие системы
В соответствии с ГОСТ 34.601-90 Автоматизированные системы в стадии создания определены следующие стадии создания автоматизированных систем:
формирование требований (пункт 1, см.выше)
разработка концепций (пункт 1)
техническое задание (между 1 и 2)
эскизный проект (пункт 2)
технический проект (пункт 2)
рабочая документация (пункт 3)
сопровождение (пункт 4)
Общепризнанным является тот факт, что указанные этапы не являются строго последовательными, а подразумевают повторы предыдущих этапов с помощью циклов обратной связи. Процесс разработки БД является итеративным, предполагает многократные возвраты и анализ полученных результатов с целью максимально адекватного описания предметной области. Для реализации жизненного цикла используются следующие модели (показаны наиболее очевидные циклы обратной связи, хотя это множество не является окончательным):
1) каскадная модель: стадии выполняются последовательно, по завершению определяется полная документация, возврат на предыдущие этапы не рассматривается.
13 EMBED Visio.Drawing.11 1415
Достоинства:
простота
однократное оформление информации
полная информация для следующей стадии
Недостатки:
не полностью определены требования (требования могут измениться по ходу)
длительное время ввода
не равномерная загрузка исполнителей
2) каскад с возвратом (возможно переопределение требований):
13 EMBED Visio.Drawing.11 1415
можно вернуться и подправить систему
увеличивается время запуска (потеря дополнительного времени при возврате)
растет не равномерность загрузки
3) итерационная модель:
13 EMBED Visio.Drawing.11 1415
определяем требования к системе
выполняется разбиение на отдельные части
проектирование и реализация производится по частям
возможно параллельное выполнение нескольких итераций
Достоинства:
улучшение загрузки
уменьшение времени запуска системы
4) эволюционная модель:
13 EMBED Visio.Drawing.11 1415

Если бы в ИС существовал только поток регламентированных запросов и не ожидалось развитие системы, то можно было бы определить границы ПО и осуществить проектирование исходя из анализа содержания всей совокупности запросов пользователей – это так называемый подход к проектированию «от запросов пользователей».
Базы данных, спроектированные по такому подходу, могут объединять все данные, необходимые для решения одной или нескольких прикладных задач, и обычно называются прикладными БД.
Наличие потока произвольных по содержанию запросов и развитие автоматизированных информационных систем во времени не позволяют в полной мере использовать подход от запросов. В этом случае необходим подход, позволяющий выполнить прогноз смыслового содержания ожидаемой совокупности произвольных запросов. Таким является подход, называемый «от реального мира». С помощью экспертов определяются границы предметной области – состав объектов, их свойства и отношения с учетом развития системы, и затем проектируется модель. Этот подход базируется на предположении, что произвольные запросы пользователей соответствуют тематической направленности ИС.
Такие БД объединяют данные, относящиеся к какой-либо предметной области (например, финансам, обучению, торговле и т.п.) и называются предметными БД (соотносящимся с предметами организации, а не с ее информационными приложениями).
Подход «от реального мира» предпочтительно использовать в качестве основного, подход «от запросов пользователей» – для уточнения границ предметной области.
Предметные БД создают основу для обработки неформализованных, изменяющихся и неизвестных запросов и приложений (приложений, для которых невозможно заранее определить требования к данным). Такая гибкость и приспосабливаемость позволяет создавать на основе предметных БД достаточно стабильные информационные системы.
Основная цель проектирования БД - это сокращение избыточности хранимых данных, а следовательно, экономия объема используемой памяти, уменьшение затрат на многократные операции обновления избыточных копий и устранение возможности возникновения противоречий из-за хранения в разных местах сведений об одном и том же объекте.

Проектирование ИС. Основное проектирование данных и ПО
Информацию для проектирования получают путем сбора данных из следующих источников:
1) Анкетирование, интервью пользователей и экспертов
2) Наблюдение за процессом
3) Документация по процессу
4) Изучение аналогов: техническая литература, журналы
Проектирование ПО будет рассмотрено позднее.
Проектирование данных: учитывают несколько уровней их представления.
По рекомендациям ANSI/SPARC (комиссия) определено три уровня:
13 EMBED Visio.Drawing.11 1415
Концептуальный уровень: показывается логическое строение данных.
Физический уровень: показывается физическая организация данных.
Внешний уровень: определяется одно или несколько представлений базы для пользователей (разграничение видимости)
13 EMBED Visio.Drawing.11 1415
Может добавляться инфологический уровень: описывает структуру информации без привязки к типу СУБД.
На рис. 2.2 приведены основные этапы проектирования баз данных. Так, весь сложный процесс создания БД может быть разбит на инфологическое и даталогическое проектирование. Последнее подразделяется на логическое и физическое проектирование. В зависимости от этапов проектирования различают: концептуальную инфологическую модель и концептуальную даталогическую модель, внешнюю инфологическую модель и внешнюю даталогическую модель.
Задача инфологического моделирования базы данных – получение семантических (смысловых) моделей, отражающих информационное содержание конкретной ПО. На этом этапе выполняется восприятие реальной действительности, абстрагирование, изучение и описание предметной области. Вначале выделяется из воспринимаемой реальности ПО, определяются ее границы, происходит абстрагирование от несущественных частей для данного конкретного применения базы данных. В результате этих действий определяются объекты, их свойства и связи, которые будут существенны для будущих пользователей системы.


Рис 2.2. Этапы проектирования базы данных

После изучения предметной области и накопления знаний о ней компонуется концептуальная инфологическая модель, основное значение при этом имеют потребности пользователей. Описывается информация, требуемая каждому конкретному пользователю, т.е. описываются запросы к БД. Каждый запрос соотносится с определенным фрагментом предметной области. Формируются описания внешних инфологических моделей, их взаимная увязка с концептуальной инфологической моделью. Полученные описания инфологических моделей отражают составляющие (сущности) предметной области, связи между ними, но эти описания не должны зависеть от методов представления данных в конкретной СУБД. Концептуальная инфологическая модель призвана обеспечить прочную и долговременную работу всей системы, выдерживать замену одной используемой СУБД на другую.
Задача логического этапа проектирования – организация данных, выделенных на предыдущем этапе проектирования в форму, принятую в выбранной конкретной СУБД. Иными словами, требуется разработать схему концептуальной модели и схемы внешних моделей данных о предметной области, пользуясь только теми типами моделей данных и их особенностями, которые поддерживаются этой СУБД. На этом этапе проектирования обычно не прорабатываются вопросы, связанные с организацией хранения и доступа к данным на внутреннем уровне. Но целесообразно уже здесь получить вполне определенные рекомендации по выбору методов доступа.
Задача физического этапа проектирования – выбор рациональной структуры хранения данных и методов доступа к ним, исходя из арсенала методов и средств, который предоставляется разработчику системой управления базами данных.

Общая схема проектирования данных
13 EMBED Visio.Drawing.11 1415
П – пользователи
Э – эксперты
1) сбор и обработка информации:
ЛП – локальное представление
2) инфологическое проектирование:
ИМ – инфологическая модель
3) даталогическое проектирование:
ЛМ – логическая модель
4) физическое и внешнее проектирование:
ФМ – физическая модель
ВМ – внешняя модель
Внешняя модель – это то, как вы намерены представлять данные, причем это должно совпадать с тем, что хотят получить пользователи и эксперты.
БД – база данных.
3. Инфологическое проектирование
Имеется несколько локальных (ЛП) представлений предметной области (ПО). Необходимо формализовать сведения об используемой информации.
Два подхода:
1) Объединение исходной информации и формализация:
13 EMBED Visio.Drawing.11 1415
ЛП => Предс + ПО => ИМ
Проблемы: данные отдельно собирались, а информация одна и та же. Пользователи используют разную терминологию, в связи с этим трудность в объединении локальных представлений. Используется для небольших проектов.
2) Объединение локальных инфологических моделей
13 EMBED Visio.Drawing.11 1415
 ЛП => ЛокИМ => ИМ
Инфологическое (концептуальное) моделирование – процесс создания внешней (инфологической) модели данных о предметной области, не зависящее от любых физических аспектов ее представления.
Инфологическая модель (ИМ) – формализованное представление информации предметной области.
Цель инфологического моделирования – обеспечение наиболее естественных для человека способов сбора и представления той информации, которую предполагается хранить в создаваемой базе данных. Поэтому инфологическую модель данных пытаются строить на доступном широкому кругу пользователей и разработчиков языке. Известны следующие средства создания внешних моделей:
семантические сети;
язык инфологического моделирования;
ER-диаграммы.
Наибольшую популярность из-за доступности, наглядности и компактности приобрел подход моделирования «сущность-связь».
Модель «сущность-связь» (Entity-Relationship model) разработана Ченом в 1976 году с целью упрощения концептуального проектирования баз данных. (другие обозначения: ER, ERD, сущность-связь).
Для изображения ERD могут использоваться разные нотации:
нотация Чена:
Первая нотация, то есть она не самая лучшая.
Нотация в литературе фигурирует в качестве ссылок.
нотация Баркера:
Она используется в СУБД Oracle.
нотация IDEF1X:
Стандартизованная нотация.
Нацелена на автоматизированную работу во многих программных продуктах.
Так же существует множество других нотаций, которые мы не будем рассматривать:
Основными элементами ER-модели являются:
сущности;
атрибуты (свойства);
связи.
Сущность
Сущность представляет собой различимое множество объектов {экземпляров сущности) реального мира с одинаковым набором атрибутов. Иными словами, сущность описывает некоторый тип объекта, характеризующийся определенным набором свойств.

Сущность идентифицируется именем и списком свойств (атрибутов). База данных о сколько-нибудь значительной предметной области содержит много (несколько) сущностей. Каждый экземпляр сущности обладает уникальным набором значений атрибутов.
На ER-диаграммах сущность представляется прямоугольником с именем сущности внутри.
13 EMBED Visio.Drawing.11 1415
Наименование - существительное в единственном числе, возможно расширенное прилагательным или дополнением.
Атрибут
Атрибут – неотъемлемое свойство сущности или связи. Именно по значениям атрибутов можно идентифицировать экземпляр сущности. Значения атрибутов представляют основную часть сведений, хранящихся в БД.
На ER-диаграммах атрибут представляется овалом (эллипсом), соединенным с соответствующей сущностью линией и с именем атрибута внутри.
13 EMBED Visio.Drawing.11 1415
Наименование - существительное в единственном числе, возможно расширенное прилагательным или дополнением.
Атрибуты связываются с сущностью. Обозначение связи зависит от вида свойства.
Атрибуты делятся на:
простые;
составные;
однозначные;
многозначные;
условные;
безусловные
производные.
Простой атрибут состоит из одного компонента с независимым существованием.
Составной атрибут состоит из нескольких компонентов, каждый из которых характеризуется независимым существованием.
13 EMBED Visio.Drawing.11 1415
На рисунке: "Дата" – простой атрибут, "Ремонт" – составной.
Однозначный (единичный) атрибут содержит одно значение для одного экземпляра сущности.
Многозначный (множественный) атрибут может содержать несколько значений для одного экземпляра сущности. Множественное свойство позволяет сохранять набор значений.
13 EMBED Visio.Drawing.11 1415
На рисунке: "Дата" – однозначный атрибут, "Ремонт" – многозначный.
Условные - могут отсутствовать у некоторых экземпляров сущностей.
Безусловные – всегда имеющиеся у всех экземпляров сущностей.
13 EMBED Visio.Drawing.11 1415 13 EMBED Visio.Drawing.11 1415
На рисунке: "Дата ремонта" – условный атрибут, может присутствовать при условии положительного значения атрибута "Ремонтопригодность" (если последний есть).
Производный атрибут представляет значение, производное (вычисляемое) от значения связанного с ним атрибута или некоторого множества атрибутов, принадлежащих некоторой сущности.

В предметной области сущности соответствует множество экземпляров. Все экземпляры имеют одинаковый набор атрибутов, но разное их значение.
Вопрос однозначной идентификации экземпляров сущности связан с понятием ключа (идентификатора).
Ключ – минимальный набор атрибутов, по значениям которых можно идентифицировать экземпляр сущности. Иными словами, ключ – одно или несколько свойств, по значениям которых все экземпляры различаются.
В наборе атрибутов сущности можно выделить несколько потенциальных ключей. Потенциальный ключ, используемый реально для идентификации экземпляров сущности называется первичным ключом.
На ER-диаграммах имена атрибутов, выбранных в качестве первичного ключа, подчеркиваются.

Связь
Связь – указывает связанность экземпляров двух типов объектов.
Связи, также как и сущности и атрибуты, идентифицируют именем.
На ER-диаграммах связь изображается в виде ромба или шестиугольника, помеченного соответствующим именем. Соединение с ассоциированными сущностями производится линиями.
Пример ER-диаграммы с обозначениями сущностей, их атрибутов и связей представлен на рис. 2.3.

Рис. 2.3. Пример ER-диаграммы

Степень связи – количество сущностей, которые охвачены данной связью.
Если связь определена между двумя сущностями, то ее степень – 2, а называется такая связь бинарной. Связь между тремя сущностями называется тернарной, четырьмя сущностями – кватернарной и т.д. В общем случае связь между n сущностями называется n-арной (рис. 2.4).
Рекурсивная связь – связь, в которой одни и те же сущности участвуют несколько раз в разных ролях.
Рекурсивная связь часто называют унарной. Пример такой связи представлен на рис. 2.4, г. В приведенном примере каждый студент из сущности СТУДЕНТ может исполнять обязанности дежурного по отношению к другим студентам той же сущности.


Для указания вида связи отмечаются:
Множественность
13 EMBED Visio.Drawing.11 1415 13 EMBED Visio.Drawing.11 1415 13 EMBED Visio.Drawing.11 1415
Возможны варианты:
- один экземпляр сущности A связан с одним экземпляром сущности B (1:1). Пример: Декан-Факультет;
- один экземпляр сущности A связан со многими экземплярами сущности B (1:М). Пример: Квартира-Жилец;
- многие экземпляры сущности A связаны со многими экземплярами сущности B (М:М). Пример: Преподаватель-Студент;
Обязательность
13 EMBED Visio.Drawing.11 1415
Пример1: А – деканат, B – замдекана. Малый деканат может не иметь замдекана.
13 EMBED Visio.Drawing.11 1415
Пример 2: В большом деканате обязательно есть замдеканы.
13 EMBED Visio.Drawing.11 1415

Расширение нотаций
Расширение нотаций ER-модели используется для отображения более сложного характера связей между сущностями. Простые сущности содержат только атрибуты, сложные - другие сущности.
1) Составная сущность: описывается не одной, а несколькими сущностями. Главная обозначает целое, прочие - части объекта. Отражает отношение целого и части.
Пример: винчестер – часть компьютера.
13 EMBED Visio.Drawing.6 1415
2) Обобщенная сущность – отражает отношение, род, вид. Пример: сущность "студент" может подразделяться на виды: "бюджетники" и "ПВЗ".
13 EMBED Visio.Drawing.11 1415
3) Ассоциация определяет отношение: объект - действия. Расширяет возможности связи:
а) Позволяет задать для связи дополнительную информацию. Пример: связь "тест" определена между сущностями "вопросы" и "тестируемые". Связь может иметь свойства: дата, оценка
13 EMBED Visio.Drawing.6 1415
б) Соединение трех или более типов
13 EMBED Visio.Drawing.11 1415
в) Используется для реализации отношения "многих ко многим".

К графическому изображению ER-модели добавляется текстовое описание:
1) описание сущности, свойств, связи.
2) описание ограничения целостности.
3) описание алгоритмических связей (например, вычисляемые поля).
4) описание информационных запросов.

Проблемы ER-моделирования
В процессе создания инфологической модели на языке ER-диаграмм, могут возникать нежелательные ситуации, которые в литературе называются ловушками соединения. Причины этих проблем кроются в неправильной интерпретации семантики предметной области, в том числе смысла некоторых связей между выделенными сущностями. Наиболее распространенными являются два вида ловушек соединения:
ловушки разветвления;
ловушки разрыва.
Ловушка разветвления имеет место в том случае, если модель отображает связь между сущностями, но путь между отдельными экземплярами этих сущностей однозначно не определяется. Возникает в случае, когда две или больше связей ОДИН-КО-МНОГИМ разветвляются из одной сущности. Потенциальная ловушка разветвления показана на рис. 2.11, где две связи типа 1:М выходят из одной и той же сущности ФАКУЛЬТЕТ. Проблема может возникнуть при попытке выяснить, по какой специальности обучается каждый из студентов факультета.


Рис. 2.11. Пример ловушки разветвления

Устранить такой дефект можно только путем перестройки исходной модели. Результат адекватного преобразования модели представлен на рис. 2.13.

Рис. 2.13. Преобразованная ER-модель

Ловушка разрыва появляется в том случае, если в модели предполагается наличие связи между сущностями, но не существует пути между отдельными экземплярами этих сущностей. Возникает при неправильной интерпретации связей между сущностями
На рис. 2.15 потенциальная ловушка разрыва показана на примере связей между сущностями ОБЩЕЖИТИЕ, СТУДЕНТ и КОМНАТА.

Рис. 2.15. Пример ловушки разрыва

ER-модель на рис. 2.15 не даёт возможность получить ответ на вопрос: «В каком общежитии находится комната под заданным номером». Устранить эту проблему можно только путем перестройки ER-модели для представления правильного взаимоотношения между сущностями. Преобразованная ER-модель показана на рис. 2.16. В модель добавлена связь Размещение между сущностями ОБЩЕЖИТИЕ и КОМНАТА.

Рис. 2.16. Преобразованная ER-модель

4. Логические модели данных.
Сетевая и иерархическая модели

Важным этапом жизненного цикла информационной системы и, в частности, проектирования базы данных, является выбор целевой СУБД.
Предлагаемые в разделе методы пригодны и к оценке новых продуктов, поступающих на рынок.
Основная цель при подборе СУБД – выбор системы, удовлетворяющей текущим и прогнозируемым требованиям организации при оптимальном уровне затрат.
В общем виде процесс выбора СУБД включает следующие этапы:
1) определение списка показателей, по которым будут оцениваться СУБД;
2) определение списка сравниваемых СУБД;
3) оценка продуктов по выбранным показателям;
4) принятие обоснованного решения, подготовка отчета.
Для оценки СУБД могут использоваться самые разнообразные параметры, которые могут быть сгруппированы следующим образом:
параметры определения данных;
физические параметры;
параметры доступности;
параметры обработки транзакций;
утилиты;
средства разработки... и т.д.

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

13 EMBED Visio.Drawing.11 1415
Модель данных состоит из трех компонент.
1. Структурная - структура данных для представления точки зрения пользователя на базу данных.
Описывает допустимые структуры организации данных и способы их связывания.
Пример: практически все СУБД не поддерживают связку многие ко многим.
2. Манипуляционная - допустимые и необходимые операции, выполняемые на структуре данных. Они составляют основу языка данных рассматриваемой модели данных. Одной лишь хорошей структуры данных недостаточно. Необходимо иметь возможность работать с этой структурой при помощи различных операций языка определения данных и языка манипулирования данными. Богатая структура данных ничего не стоит, если нет возможности оперировать ее содержимым.
3. Целостностная - ограничения для контроля целостности. Определяет ограничения, накладываемые структурой, связями и набором операций. Модель данных должна быть обеспечена средствами, позволя ющими сохранять ее целостность и защищать ее.

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

Сетевая модель данных
Строится по рекомендациям CODASYL (конференция по символьным языкам).
С точки зрения теории графов сетевой модели соответствует произвольный граф (возможно имеющий циклы и петли). В узлах графа помещаются типы записей, а ребра интерпретируются как связи между типами записей.
Модель не накладывает ограничения на связи.
Узлы сети описывают типы объектов.
Дуги – связи между экземплярами разных типов.
В описании базы включается множество описаний типов, множество описаний связей.
Сетевая БД состоит из набора записей и набора связей между этими записями, а если говорить более точно, из набора экземпляров каждого типа из заданного в схеме БД набора типов записи и набора экземпляров каждого типа из заданного набора типов связи.
Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка.
13 EMBED Visio.Drawing.11 1415
Для описания типа описывается структура записи этого типа.
Структура может быть линейной:
13 EMBED Visio.Drawing.11 1415
По минимуму надо хранить: имя, тип и размерность.
Описание связок:
Связь описывается набором. Описание набора содержит указание типа владельца набора, указание типа члена набора, описание характеристик связи.

Важный элемент описания связи – класс членства. Указывается для подчиненного типа. Для главного типа – указание связи не обязательно.
Три класса членства:
Не обязательное членство: подчиненная запись не обязана иметь владельца.
Обязательное членство: подчиненная запись обязана иметь владельца, но может его сменить.
Фиксированное членство: подчиненная запись обязана иметь владельца и не может его сменить.
По соединениям типов разрешается:
множественное владение:
13 EMBED Visio.Drawing.11 1415
множественное членство:
13 EMBED Visio.Drawing.11 1415
множественное связывание двух:
13 EMBED Visio.Drawing.11 1415
рекурсивная (петлевая) связь:
13 EMBED Visio.Drawing.11 1415
По соединениям типов НЕ разрешается:
Отношение "многие ко многим".
Включение экземпляра в несколько связей из одного набора.
Связывание реализуется с помощью физических указателей:
Основной вариант – кольцо:
13 EMBED Visio.Drawing.11 1415 13 EMBED Visio.Drawing.11 1415
Сетевая модель базы при выборке работает медленнее, чем реляционная.
13 EMBED Visio.Drawing.11 1415
Пример: Найти сотрудника Иванова и найти его отпуска.
Достоинства сетевой модели:
высокое быстродействие
компактность
Недостатки:
низкая надежность за счет возможности потери указателей.
"позаписная" работа, т.е. привыборке последовательно просматриваются все записи.
невозможность оперативной работы, т.е. сетевая модель способна отвечать только на заранее запрограммированные запросы

Операции сетевой модели
1) операции с данными:
удалить
добавить
изменить
2) операции со связями:
подключить
отключить
переключить
3) навигация по данным:
переход на подчиненную
возможность перехода на следующую подчиненную
переход на владельца
Отличие сетевой структуры от иерархической заключается в том, что каждый элемент в сетевой структуре может быть связан с любым другим элементом (см. рис. 2.3). Пример простой сетевой структуры показан на рис. 2.4.
[ Cкачайте файл, чтобы посмотреть картинку ][ Cкачайте файл, чтобы посмотреть картинку ]
Достоинством сетевой модели данных является возможность эффективной реализации по показателям затрат памяти и оперативности.
Недостатком сетевой модели данных являются высокая сложность и жесткость схемы БД, построенной на ее основе.
Наиболее известными сетевыми СУБД являются IDMS , db_VistaIII , СЕТЬ, СЕТОР и КОМПАС.
Простой пример сетевой схемы БД приведен на рис. 2.22.



Рис. 2.22. Пример схемы сетевой БД

Примерный набор операций при использовании сетевой модели может быть следующим [8].
Найти конкретную запись в наборе однотипных записей (инженера Петрова).
Перейти от предка к первому потомку по некою рой связи (к первому сотруднику отдела 42).
Перейти к следующему потомку в некоторой связи (от Петрова к Иванову).
Перейти от потомка к предку по некоторой связи (найти отдел Петрова).
Создать новую запись.
Уничтожить запись.
Модифицировать запись.
Включить в связь.
Исключить из связи.
Переставить в другую связь и т.д.

Иерархическая модель данных
Является частным случаем сетевой модели.
Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева.
Тип дерева состоит из одного «корневого» типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи
Структура – дерево.


.

Пример типа дерева (схемы иерархической БД) представлен на рис. 2.19.


Рис. 2.19. Пример схемы иерархической БД

На рис. 2.19 ОТДЕЛ является предком для НАЧАЛЬНИК и СОТРУДНИКИ, а НАЧАЛЬНИК и СОТРУДНИКИ - потомки ОТДЕЛ. Между типами записи поддерживаются связи.

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

13 EMBED Visio.Drawing.11 1415
Виды членства:
Класс членства всегда фиксирован. При удалении – каскадирование.
Все экземпляры данного типа потомка с общим экземпляром типа предка называются близнецами. Для БД определен полный порядок обхода - сверху-вниз, слева-направо.
Примерами типичных операторов манипулирования иерархически организованными данными могут быть следующие.
Найти указанное дерево БД (например, отдел 42, рис.2.19).
Перейти от одного дерева к другому.
Перейти от одной записи к другой внутри дерева (например, от отдела – к первому сотруднику).
Перейти от одной записи к другой в порядке обхода иерархии.
Вставить новую запись в указанную позицию.
Удалить текущую запись.
Автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя.
Иерархическая структура реализует отношение ОДИН-КО-МНОГИМ между исходным и порожденным типами записей. Это отображение полностью функционально, т.к. дерево не может содержать порожденный узел без исходного узла (за исключением «корня»). Однако для представления отображения МНОГИЕ-КО-МНОГИМ необходимо дублирование деревьев, а значит, реализация сложных связей требует больших затрат памяти.
Другой проблемой иерархий является невозможность хранения в БД порожденного узла без соответствующего исходного, т.е. в этом случае необходимо ввести пустой исходный узел. Соответственно удаление данного исходного узла влечет удаление всех порожденных узлов (поддеревьев), связанных в ним. Эти ограничения создают проблемы применения иерархической модели для некоторых приложений.
Достоинством иерархической структуры является компактность. Она имеет максимальные характеристики по объёму памяти и быстродействию.

Особенности, достоинства и недостатки ранних даталогических моделей
Их особенности:
1. Эти системы активно использовались в течение многих лет, а некоторые используются даже в наше время, накоплены громадные базы данных, и одной из актуальных проблем информационных систем является использование этих систем совместно с современными системами.
2. Все ранние системы не основывались на каких-либо абстрактных моделях. Понятие модели данных фактически вошло в обиход специалистов в области БД только вместе с реляционным подходом.
3. В ранних системах доступ к БД производился на уровне записей. Пользователи этих систем осуществляли явную навигацию в БД, используя языки программирования, расширенные функциями СУБД. Интерактивный доступ к БД поддерживался только путем создания соответствующих прикладных программ с собственным интерфейсом.
4. Навигационная природа ранних систем и доступ к данным на уровне записей заставляли пользователя самого производить всю оптимизацию доступа к БД, без какой-либо поддержки системы.
5. После появления реляционных систем большинство ранних систем было оснащено «реляционными» интерфейсами. Однако в большинстве случаев это не сделало их по-настоящему реляционными системами, поскольку оставалась возможность манипулировать данными в естественном для них режиме (на низком физическом уровне).
Достоинства и недостатки ранних систем.
Достоинства:
развитые средства управления данными во внешней памяти на низком уровне;
возможность построения вручную эффективных прикладных программ;
возможность экономии памяти.
Недостатки:
сложность практического использования;
необходимость знания физической организации данных;
жесткая зависимость прикладных систем от физической организации данных;
логика перегружена деталями организации доступа к БД.

5. Реляционная модель данных
В конце 60-х годов появились работы, в которых обсуждались возможности применения различных табличных даталогических моделей данных, т.е. возможности использования привычных и естественных способов представления данных. Будучи математиком по образованию, сотрудник фирмы IBM доктор Э. Кодд предложил использовать для обработки данных аппарат теории множеств (объединение, пересечение, разность, декартово произведение). Он показал, что любое представление данных сводится к совокупности двумерных таблиц особого вида, известного в математике как отношение – relation (англ.).
Реляционная модель – это набор логически связанных отношений.
Отношение (по Кодду) предназначено для хранения описания и данных для определенного типа объекта. Отношение соответствует типу объектов предметной области или их взаимодействий.
Наименьшая единица данных реляционной модели – это отдельное атомарное (неразложимое) для данной модели значение данных. Так, в одной предметной области фамилия, имя и отчество могут рассматриваться как единое значение, а в другой – как три различных значения.
Доменом называется множество атомарных значений одного и того же типа. Так, на рис. 2.23 домен пунктов отправления (назначения) – множество названий населенных пунктов, а домен номеров рейса – множество целых положительных чисел.
Домен определяет множество допустимых значений.
Описание домена содержит:
наименование
тип
возможная размерность
возможное ограничение
возможное значение по умолчанию
Отношение на доменах D1, D2, ..., Dn (не обязательно, чтобы все они были различны) состоит из заголовка и тела.
Заголовок содержит описание структуры данных. Он состоит из такого фиксированного множества атрибутов A1, A2, ..., An, что существует взаимно однозначное соответствие между этими атрибутами Аi и определяющими их доменами Di (i = l, 2, ..., n).
Описание заголовка представляется неупорядоченным набором пар атрибут-домен.
Атрибут определяет некоторую характеристику описываемого типа объекта (атрибут – столбец).
Тело содержит набор кортежей, т.е. состоит из меняющегося во времени множества кортежей, где каждый кортеж состоит в свою очередь из множества пар атрибут-значение (Ai:Vi), (i = 1, 2, ..., n), по одной такой паре для каждого атрибута А. в заголовке. Для любой заданной пары атрибут-значение (Ai:Vi) Vi является значением из единственного домена Di, который связан с атрибутом Аi.
Кортеж содержит данные по одному экземпляру описываемого объекта. Каждая строчка тела – атрибут-значение.
13 EMBED Visio.Drawing.11 1415

На рис. 2.23 приведен пример отношения для расписания движения самолетов.


Рис. 2.23. Отношение в реляционной модели

Степень отношения – это число его атрибутов. Отношение степени один называют унарным, степени два – бинарным, степени три – тернарным, ..., а степени п – n-арным.
Кардинальное число или мощность отношения – это число его кортежей. Кардинальное число отношения изменяется во времени в отличие от его степени.
Изменение кардинального числа отношения связано с изменением состояния отношения.
Вышеупомянутые и некоторые другие математические понятия явились теоретической базой для создания реляционных СУБД, разработки соответствующих языковых средств и программных систем, обеспечивающих их высокую производительность, и создания основ теории проектирования баз данных. Однако для массового пользователя реляционных СУБД можно использовать неформальные эквиваленты этих понятий:
Отношение – Таблица (иногда Файл),
Кортеж – Строка (иногда Запись),
Атрибут - Столбец, Поле.

Отношение может использоваться двояко:
1) Для представления набора объектов;
2) Для представления связей между наборами объектов.
Реляционная база данных – это набор экземпляров конечных отношений. Схему реляционной БД можно представить в виде совокупности схем отношений


Другими словами – реляционная база данных – это совокупность отношений, содержащих всю информацию, которая должна храниться в БД. Однако пользователи могут воспринимать такую базу данных как совокупность таблиц.
База представляется набором логически связанных отношений.
13 EMBED Visio.Drawing.11 1415
Отличие отношения от таблицы:
Неупорядоченность по атрибутам и кортежам
Отсутствие совпадающих кортежей (уникальность)
На рис. 2.24 показаны таблицы базы данных, построенные по инфологической модели базы данных «Питание».
Каждая таблица состоит из однотипных строк и имеет уникальное имя.
Строки имеют фиксированное число полей (столбцов) и значений (множественные поля и повторяющиеся группы недопустимы). Иначе говоря, в каждой позиции таблицы на пересечении строки и столбца всегда имеется в точности одно атомарное значение или ничего.
Строки таблицы обязательно отличаются друг от друга хотя бы единственным значением, что позволяет однозначно идентифицировать любую строку такой таблицы.
Столбцам таблицы однозначно присваиваются имена, и в каждом из них размещаются однородные значения данных (даты, фамилии, целые числа или денежные суммы).
Полное информационное содержание базы данных представляется в виде явных значений данных, и такой метод представления является единственным. В частности, не существует каких-либо специальных «связей» или указателей, соединяющих одну таблицу с другой. Так, связи между строкой с БЛ = 2 таблицы «Блюда» на рис. 2.24 и строкой с ПР = 7 таблицы продукты (для приготовления Харчо нужен Рис), представляется не с помощью указателей, а благодаря существованию в таблице «Состав» строки, в которой номер блюда равен 2, а номер продукта – 7.
При выполнении операций с таблицей ее строки и столбцы можно обрабатывать в любом порядке безотносительно к их информационному содержанию. Этому способствует наличие имен таблиц и их столбцов, а также возможность выделения любой их строки или любого набора строк с указанными признаками.

Рис. 2.24. База данных «Питание»

Для обеспечения уникальности кортежей определяется первичный ключ.
Первичный ключ – один или несколько атрибутов, по значениям которых все кортежи различаются.
Пусть R – отношение с атрибутами А1, A2, ..., Ап. Говорят, что множество атрибутов К = (Аi, Аj, ..., Аk) отношения R является возможным ключом R тогда и только тогда, когда удовлетворяются следующие независимые от времени условия:
1. Уникальность: в произвольный заданный момент времени никакие два различных кортежа R не имеют одного и того же значения для Аi, Аj, ..., Ak.
2. Минимальность: ни один из атрибутов Аi, Аj, ..., Ak не может быть исключен из К без нарушения уникальности.
3. Обязательность – все атрибуты первичного ключа должны быть заполнены
Каждое отношение обладает хотя бы одним возможным ключом, поскольку, по меньшей мере, комбинация всех его атрибутов удовлетворяет условию уникальности. Один из возможных ключей (выбранный произвольным образом) принимается за его первичный ключ. Остальные возможные ключи, если они есть, называются альтернативными (потенциальными) ключами или кандидатами.
Для связывания отношений вводится внешний ключ. Получается дублированием атрибутов первичного ключа в подчиненную таблицу.
13 EMBED Visio.Drawing.11 1415
Для внешнего ключа:
уникальность не требуется
обязательность не требуется
минимальность учитывается
значение ВК должно совпадать с каким-нибудь значением первичного ключа, либо быть пустым.
Целостность данных включает:
Целостность отношений: все кортежи должны быть уникальны. Поддерживается введением первичного ключа.
Целостность значений: поддерживается введением доменов.
Ссылочная целостность: поддерживается введением внешнего ключа.
По сравнению с ранними даталогическими моделями, реляционный подход обладает следующими особенностями.
Достоинства:
наличие относительно небольшого набора абстракций;
наличие простого, но мощного математического аппарата (в основе реляционного подхода – теория множеств);
возможность ненавигационного манипулирования данными без знания их конкретной физической организации.
возможность выполнять групповые операции.
Недостатки:
ограниченность использования в нетрадиционных предметных областях;
относительно неполная адекватность отражения семантики предметной области.
Более медленная обработка данных.
Самая сильная сторона реляционного подхода – математический аппарат для выполнения операций над отношениями реляционной модели.
Наличие простого, но мощного математического аппарата сыграло решающую роль в повсеместном переходе разработчиков СУБД на реляционную модель.

Операции с реляционными данными
1) Унарные операции (операции с одним отношением):
а) Проекция: отношение, указывающее указанный атрибут.
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415 – результирующее значение, 13 EMBED Equation.3 1415 – исходное значение, 13 EMBED Equation.3 1415 – атрибут или список атрибутов, 13 EMBED Equation.3 1415 – проекция.(Результат - новое отношение, включающее только указанные атрибуты исходного отношения R).
б) Ограничение:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415-операция определения, предикат – логическое выражение, параметрами которого являются атрибуты отношения.(Результат - новое отношение, включающее кортежи исходного отношения, удовлетворяющие заданному предикату).
13 EMBED Visio.Drawing.11 1415
2) Операции с двумя однотипными отношениями:
а) Объединение: отношение, содержащее все кортежи исходных отношений без повторов.
13 EMBED Equation.3 1415
б) Разность: отношение, включающее кортежи 13 EMBED Equation.3 1415 и не включающие 13 EMBED Equation.3 1415.(результат включает в себя все кортежи отношения S не входящие в отношение T)
13 EMBED Equation.3 1415
в) Пересечение: отношение, включающее кортежи одновременно входящие в 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415
3) Операции с разнотипными отношениями:
а) декартово произведение:
13 EMBED Equation.3 1415, результат – отношение, включающее все варианты попарного соединения кортежей соотношений.
13 EMBED Visio.Drawing.11 1415
Пример: select * from 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
б) деление: операция обратная декартову произведению
13 EMBED Equation.3 1415
13 EMBED Visio.Drawing.11 1415
Остаток не входит в результат.
в) соединение – производная операция сочетает декартово произведение и ограничение.
Для соединения выделяются варианты:
1. Внутренние соединения:
Тета-соединение: результат – все пары сцеплений, при выполнении условия (>, <, = и т.д.)
13 EMBED Equation.3 1415
Тета – предикат, включающий столбцы исходных отношений, по которым происходит соединение.
Пример1: студ.группа, общее между ними – это и там и там есть название группы.
Эквивалентное соединение: это частный случай тета – соединение по условию равенства.
Естественное соединение: как эквивалентное соединение, но дублирование столбцов или связей удаляется.
13 EMBED Equation.3 1415
(По такому варианту вы будете собирать таблицы).
Полусоединение: в результат включаются данные только одного исходного отношения.
13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415.
Все указанные выше соединения называются внутреннее соединение: в результат включаются данные, нашедшие партнера.
2. Внешние соединения: в результат включаются все данные, нашедшие партнера плюс однократно данные, не нашедшие партнера.
В зависимости от дополнительно включаемых данных различают:
левое соединение: 13 EMBED Equation.3 1415
правое соединение: 13 EMBED Equation.3 1415
полное внешнее соединение: 13 EMBED Equation.3 1415
Пример:
13 EMBED Visio.Drawing.11 1415
внутреннее соединение:
13 EMBED Equation.3 1415
внешнее соединение:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
Полное внешнее соединение: левое + правое.

Реляционное исчисление
Исчисление задает не последовательность обработки, а требовательность к результату.
Упрощенный вариант формулы реляционного исчисления:
13 EMBED Equation.3 1415
Целевой список – указывает состав выходных результатов.
Область определения – набор отношений, в которых выполняется отбор.
Условие – требование получаемого результата.
Пример:
13 EMBED Equation.3 1415
Первый вариант решения задачи:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Visio.Drawing.11 1415
Второй вариант решения задачи:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Visio.Drawing.11 1415
6. Нормализация отношений
Реляционная модель – набор взаимосвязанных отношений.
Формульная запись отношения: 13 EMBED Equation.3 1415, часть отношения может быть помечена как первичный ключ 13 EMBED Equation.3 1415.
Основные требования к отношениям:
атомарность к атрибутам
уникальность кортежей
Пример: Расписание приема врачей поликлиники.
Включает данные:
врач (ФИО, специалист)
прием (день, время, кабинет)
Врач
Прием

ФИО
Специалист
День
Время
Кабинет

Иванов
Хирург
Пн, вт,
Ср, чт.
8:00-13:00,
14:00-16:00
3
3

Отношение Расп(врач(ФИО, специалист), прием(день, время, кабинет)) – недопустимо.
Правильная запись таблицы:
ФИО
Специалист
День
Время
Кабинет

Иванов
Хирург
Пн
Вт
Ср
Чт
8:00-13:00,
14:00-16:00
3
3



Прием(ФИО, специалист, день, время, кабинет). При этом имеем составной ключ: ФИО, день.
Для повышения уникальности введем уникальный номер:
Прием(табN, день, ФИО, специальность, время, кабинет)
На первых этапах проектирования базы данных, после анализа предметной области и определения состава информации для хранения в БД обычно формируется так называемое универсальное отношение.
Универсальное отношение – одна таблица, в которой может храниться вся информация об интересующей предметной области. Другими словами схему этого отношения образует весь перечень интересующих атрибутов предметной области.
Использование универсального отношения приводит к избыточности – дублированию данных в разных таблицах, повторяющиеся сочетания в одной таблице.
Повторяемость сочетаний, в свою очередь, ведет к аномальностям обновления:
1) Аномальность изменения: приводит к необходимости множественного изменения.
2) Аномалия удаления: возможность потери информации при удалении сопутствующих данных.
3) Аномалия добавления: например, нельзя ввести данные по врачу, не ведущему прием.
Аномалии обновления являются нежелательным побочным эффектом, обусловленным избыточностью хранимых данных при внесении изменений в отношение.
Рассмотрим отношение График.
График
РЕЙС
ДАТА
ПИЛОТ
ГАЛЕРЕЯ


112
6 июня
Иванов
7


112
7 июня
Петров
7


203
9 июня
Иванов
12

Атрибуты РЕЙС ДАТА являются ключом отношения График, и это отношение должно также удовлетворять функциональной зависимости РЕЙСГАЛЕРЕЯ. Пусть требуется обновить отношение, указав значение ключа и задавая значения всем остальным атрибутам. Однако если выполнить операцию
ИЗМЕНИТЬ (График; 112, 6 июня, ПИЛОТ=Иванов, ГАЛЕРЕЯ=8),
то отношение перестанет удовлетворять функциональной зависимости РЕЙСГАЛЕРЕЯ. Чтобы избежать нарушения функциональной зависимости, необходимо после каждого выполнения операции обновления просмотреть полученное отношение и везде (во всех кортежах), где появляется указанный в операторе номер рейса, изменить номер галереи на указанный в операторе. А требовалось всего лишь изменить один кортеж. Кроме того, информация о связи между номером рейса и номером галереи дублируется с рассмотренном отношении, что ведет к избыточности информации.
С точки зрения как обновления, так и устранения избыточности лучше представить ту же информацию в виде базы данных из двух отношений Пилот-График и Галерея-График.

Пилот-График
РЕЙС
ДАТА
ПИЛОТ


112
6 июня
Иванов


112
7 июня
Петров


203
9 июня
Иванов


Галерея-График
РЕЙС
ГАЛЕРЕЯ


112
7


203
12


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

Для устранения избыточности выполняется нормализация.
Нормализация - формальный метод анализа отношений на основе их первичного ключа (или потенциальных ключей) и существующих функциональных зависимостей.
Цель нормализации – получение такого проекта базы данных, в котором каждый факт хранится в одном месте, т.е. исключена избыточность информации. Это делается не столько с целью экономии памяти, сколько для исключения возможной противоречивости хранимых данных из-за их избыточности.
Нормальная форма представляет собой ограничение на схему базы данных (отношения), которое избавляет базу данных от некоторых нежелательных свойств.
Нормализация чаще всего выполняется в несколько последовательных этапов, результатом каждого из которых является некоторая нормальная форма с известными свойствами.
Определены 6 нормальных форм:
1НФ, 2НФ, 3НФ, НФБК (Б – Бойс, К – Кодд), 4НФ, 5НФ.
Каждая следующая форма не содержит некоторого вида избыточности. Нормализация ведется последовательно от первой ко второй и т.д. формам.
Каждая следующая нормальная форма является в некотором смысле более ограниченной, но и более желательной, чем предшествующая. Это связано с тем, что (N + 1)-я нормальная форма не обладает некоторыми недостатками, свойственным N-й нормальной форме.
При реализации реляционной БД только удовлетворение требований первой нормальной формы (1НФ) обязательно для создания отношений приемлемого качества. Все остальные формы могут использоваться по желанию проектировщика. Однако чтобы избежать аномалий обновления, описываемых ниже, нормализацию рекомендуется проводить как минимум до ЗНФ.

1НФ требует:
атомарность значений атрибутов
уникальность кортежей.
Схема отношения R находится в первой нормальной форме (1НФ), если значения в домене D(A) являются атомарными для каждого атрибута А в JR. Другими словами, значения в домене не являются ни списками, ни множествами простых или сложных значений.
Определить понятие атомарности трудно: значение атомарное в одном приложении, может быть неатомарным в другом. Можно руководствоваться общим принципом, что значение неатомарно, если в приложении оно используется по частям.

Пример. Имеется отношение Сотрудники:

Сотрудники
НОМЕР
ФИО




23
Вербов Александр Владимирович


24
Фисенко Александр Сергеевич


25
Фатхи Дмитрий Владимирович


Если понадобится указать только фамилии сотрудников, то указанное отношение не находится в 1НФ, так как требуемые значения являются частью атрибута ФИО. Чтобы отношение в таких условиях находилось в 1НФ, атрибут ФИО должен быть разбит на части, как показано ниже.

Сотрудники
НОМЕР
ФАМИЛИЯ
ИМЯ
ОТЧЕСТВО


23
Вербов
Александр
Владимирович


24
Фисенко
Александр
Сергеевич


25
Фатхи
Дмитрий
Владимирович


Последующие нормальные формы используют понятие функциональной зависимости:
Создание баз данных преследует две основные цели:
понизить избыточность хранимых данных;
повысить их надежность.
Любое априорное знание о различного рода ограничениях, накладываемых на совокупности данных, может принести большую пользу для достижения указанных целей.
Один из способов формализации этих знаний – установление зависимостей между элементами данных.
Функциональная зависимость является обобщением понятия ключа. Она имеет место тогда, когда значения кортежа на одном множестве атрибутов единственным образом определяют эти значения на другом множестве атрибутов.
Пусть есть две группы атрибутов: А и В. Если любому значению А соответствует определенное значение В, то они находятся в функциональной зависимости.
Либо А – функционально определяет В, либо В – функционально зависит от А.
Пример: отношение График (ПИЛОТ, РЕЙС, ДАТА, ВРЕМЯ-ВЫЛЕТА).
График
ПИЛОТ
РЕЙС
ДАТА
ВРЕМЯ-ВЫЛЕТА


Мовчан
Мовчан
Синицын
83
116
281
9 августа
10 августа
8 августа
10:15
13:25
05:50


В отношении имеются следующие функциональные зависимости:
1. ВРЕМЯ функционально зависит от РЕЙСА.
2. РЕЙС функционально зависит от {ПИЛОТ, ДАТА, ВРЕМЯ}.
3. ПИЛОТ функционально зависит от {РЕЙС, ДАТА}.
Символически можно записать это так:


2НФ требует:
удовлетворение требований в 1НФ
все неключевые атрибуты должны находиться в полной функциональной зависимости от первичного ключа.
Полная функциональная зависимость - зависимость от всего ключа в целом. Если лишь от части ключа, то - частичная зависимость. Для примера с расписанием приёма врачей:
табN => ФИО табN, день => время
табN => Специальность табN => кабинет
Для устранения частичной зависимости её выносят в отдельное отношение:
Прием1(табN, день, время)
Прием2(табN, ФИО, специальность, кабинет)
Получили 2НФ.

3НФ: связана с понятием транзитивной зависимости.
13 EMBED Visio.Drawing.11 1415
Если А зависит от В, В зависит от С, то А транзитивно зависит от С.
Поскольку специалист ведет прием в определенном кабинете, кабинет приписан к определенной специальности, то в заполненной таблице будет повтор сочетания специальность->кабинет. Для нормализации, части транзитивной зависимости выносятся в отдельное отношение.
Получим 3НФ:
Прием1(табN, день, время)
Прием21(табN, ФИО, кабинет)
Прием22(кабинет, специальность)
3НФ – это отношение, удовлетворяющее требованиям 2НФ и не имеющее транзитивной зависимости неключевых атрибутов.

НФБК учитывает нескольких потенциальных (возможных) ключей.
Пусть в отношении Прием1 имеется ещё один атрибут: паспорт.
13 EMBED Visio.Drawing.11 1415
Итак, НФБК – это отношение, в котором все функциональные зависимости являются полными зависимостями от какого-нибудь возможного ключа. Для нормализации необходимо выделить в отдельные отношения связи атрибутов с частью ключа.
Прием11(табN, день, время)
Прием12(табN, паспорт)

4НФ и 5НФ на практике почти не встречаются.

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

Механизмом нормализации можно пользоваться как технологией проектирования.
Общая схема при этом следующая: выявляются все необходимые данные, сводятся в единое отношение – универсальное отношение. В нем выявляются неполные функциональные зависимости - выполняется переход к 2НФ. Выявляются транзитивные зависимости – выполняется переход к 3НФ и т.д.
Такой подход можно использовать:
Для проектирования небольших баз данных (до 50 атрибутов)
Для нормализации отдельных частей базы, полученных другими методами

Резюме:
Нормализация отношений используется для преобразования структуры имеющихся отношений с целью получения требуемых свойств. Основное требование – минимизация дублирования. Нормализация сводится к пошаговой декомпозиции отношений на более простые.
Приведение к первой нормальной форме (1НФ)
Отношение находится в 1НФ, если не содержит составных атрибутов, имеют первичный ключ. Наличие первичного ключа сводится к тому, чтобы не было повторной записи и все значения были проставлены (пр: разделение даты на год, месяц и день).
Приведение к 2НФ
Обладает свойствами 1НФ + полной функциональной зависимостью атрибутов от ключа. Она состоит в том, что атрибут зависит от всего ключа, а не от части. Иначе - частичная функциональная зависимость. Для устранения частичной функциональной зависимости, ее описание выносится в отдельное отношение:
13 EMBED Visio.Drawing.6 1415
ВРЕМЯ - зависит от полного ключа
СПЕЦ - зависит от части ключа
КАБ - зависит от части ключа
Приведение к 3НФ
Обладает свойствами 2НФ + не транзитивной зависимостью атрибутов от ключа:

В С Д

Для устранения транзитивной зависимости отдельные переходы выделяются в отдельное отношение:
13 EMBED Visio.Drawing.6 1415
13 EMBED Visio.Drawing.6 1415
Теоретический подход в составлении генерального отношения, затем пошаговая нормализация до нужной формы. Недостаток: трудоемкость процесса.

7. Даталогическое проектирование
Выполняется переход от инфологической модели к даталогической (логическая модель).
Исходные данные:
Инфологическая модель, информация по выбранному типу или марке СУБД.
Критериями оценки СУБД являются:
- адекватность;
- полнота;
- адаптируемость;
- универсальность;
- сложность структуры БД;
- степень дублирования данных в БД;
- сложность последующей обработки;
- объём требуемой памяти;
- скорость обработки информации.
Логические модели подразделяются на:
13 EMBED Visio.Drawing.11 1415
При проектировании учитываются следующие ограничения:
ограничения, накладываемые моделью данных
ограничения, накладываемые конкретной СУБД
В результате получаем логическую модель, учитывающую принятые ограничения.
Логическая модель – формализованное представление логической организации данных предметной области, удовлетворяющей требованиям выбранного вида модели данных и конкретной СУБД.
Основные отличия от инфологической модели:
могут быть введены искусственные идентификаторы, то есть изменится число атрибутов
могут быть изменены (устранены) вычисляемые атрибуты
устранение связи: многие ко многим
соединение и расщепление данных

Рассмотрим преобразование реляционной логической модели
Для реляционной базы данных проектирование логической структуры заключается в том, чтобы разбить всю информацию по файлам (или в терминах реляционной модели – по отношениям, таблицам), а также определить состав полей (в терминах реляционной теории – атрибутов) для каждого из этих файлов. Определение ключа каждого из отношений также является задачей логического проектирования реляционной БД.
Существуют разные методы проектирования логической структуры реляционных баз данных. Среди них есть и строгие математические методы, обычно базирующиеся на теории нормализации. Рассмотренный ниже метод проектирования основан на анализе ER-модели и переходе от нее к реляционным отношениям. В основу этого метода положен эмпирический подход. Предлагаемый метод является достаточно простым и наглядным, и в то же время дает хорошие результаты. Базы данных, полученные в результате применения излагаемой ниже методики проектирования, находятся в 4-й нормальной форме.
Для перехода от ранее полученной инфологической модели «сущность-связь» к логической реляционной модели выполняются следующие шаги:
1) преобразование исходной инфологической модели (ИМ)
2) переход к логической модели
3) нормализация отношений
4) дополнительные действия

I. ПРЕОБРАЗОВАНИЕ ИСХОДНОЙ ИНФОЛОГИЧЕСКОЙ МОДЕЛИ (ИМ):
На этом шаге нужно получить инфологическую модель, сущности которой содержат только элементарные свойства (одновременно простые, единичные и безусловные) и связаны между собой связями 1:М (или, как частный случай, 1:1).
При этом могут применяться следующие преобразования.
Преобразования сущностей
1. Преобразование составного объекта.
Вложенные сущности выносятся на уровень главной сущности объекта и соединяются с ней внешними связями.




2. Преобразование обобщенного объекта
Преобразование может быть выполнено в нескольких формах:
а) сущности категорий выносятся на уровень главной сущности объекта и соединяются с ней внешними связями. При этом общие данные и данные категорий хранятся отдельно.
13 EMBED Visio.Drawing.11 1415
б) сущности категорий объединяются с частями главной сущности с образованием набора независимых сущностей объектов;

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






в) все сущности объединяются в единую сущность

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






Всё это иллюстрируется следующим образом:


3. Преобразование ассоциации.
Ассоциация рассматривается как обычная сущность, что сводится к простой замене изображения ассоциации на изображение сущности



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



2. Преобразование множественного свойства
Множественное свойство выносится в новую сущность, связываемую с исходной сущностью связью 1:М



Другим возможным вариантом является введение вместо одного множественного свойства достаточного числа свойств для поединичного хранения данных (например, если нужно хранение данных по месяцам в течение года – ввести 12 свойств).

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



3. Вычисляемые свойства - данные, которые не вводятся с клавиатуры, а рассчитываются. Их можно хранить (в БД это свойство оставляем). А можно не хранить, а каждый раз вычислять. (Если расчетные данные должны соответствовать исходным данным на момент расчета).

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



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



2. Преобразование связи М:М
Вводится дополнительная связующая сущность, разбивающая связь М:М на две связи 1:М



II. ПЕРЕХОД К ЛОГИЧЕСКОЙ МОДЕЛИ:
На этом шаге элементы инфологической модели отображаются в элементы реляционной модели. Выполняются два основные действия.
1. Отображение сущностей инфологической модели в реляционные отношения.
При этом свойства сущностей отображаются в атрибуты отношений, идентификаторы сущностей – в первичные ключи отношений (локальные идентификаторы – в части первичных ключей отношений).
Графически отношение можно представить в виде

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




Полученное итоговое отношение можно также записать как:
Отношение(Атрибут1,Атрибут2,Атрибут3)

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



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

III. НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ
Выполняются в случае необходимости для исключения избыточности данных.

IV. ДОПОЛНИТЕЛЬНЫЕ ДЕЙСТВИЯ
Выполняются для повышения эффективности использования данных.
1. Введение искусственных идентификаторов. Выполняется в следующих случаях:
- Если составной (длинный) идентификатор
13 EMBED Visio.Drawing.11 1415
- Если не уникальный ключ
- Если динамический идентификатор
- Если первичный ключ часто меняется
2. Слияние таблиц: совместно используемые таблицы сливаются путем соединения (денормализация).
3. Введение дублирования данных: для исключения соединения таблиц (часть процесса денормализации)
4. Вертикальное разделение отношений.
13 EMBED Visio.Drawing.11 1415
если есть ограничение на число полей записи или на длину записи;
если длина строки очень большая – программа выборки данных работает медленно;
как косвенный элемент защиты.
5. Горизонтальное разделение отношений:
13 EMBED Visio.Drawing.11 1415
Используется в случаях:
Если необходимо какой-то элемент таблицы защитить от пользователя;
Используется для повышение быстродействия (например, данные по студентам в университете разбиты по факультетам).
8. Ограничения целостности, виды и реализация
Обеспечение целостности данных является важнейшей задачей при проектировании и эксплуатации систем обработки данных (СОД).
Проблема целостности состоит в обеспечении достоверности и согласованности данных в базе данных в любой момент времени. Целостность актуальность и непротиворечивость информации, ее защищенность от разрушения и несанкционированного изменения.
Целостность данных - неотъемлемое свойство базы данных, и ее обеспечение является важнейшей задачей проектирования БД. Целостность данных описывается набором специальных предложений, называемых ограничениями целостности. Ограничения целостности представляют собой утверждения о допустимых значениях отдельных информационных единиц и связях между ними. Эти ограничения определяются в большинстве случаев особенностями предметной области, хотя могут отражать и чисто информационные (лингвистические) характеристики.
Выполнение заданных ограничений целостности должно контролироваться при вводе и изменении данных.
Источниками происхождения ограничений являются:
а) ограничения, определяемые выбранной моделью данных. Каждая модель данных включает набор ограничений, которые описывают то, что допустимо (или недопустимо) для организации данных, предлагаемой моделью.
Например, реляционная модель данных требует, чтобы значение внешнего ключа дочернего отношения совпадало с одним из значений первичного ключа в родительском отношении или было неопределенным (NULL);
б) естественные ограничения данных. Для многих видов данных или сочетаний данных имеются физические ограничения, которые реально не могут быть нарушены («этого не может быть никогда»)
Например, возраст сотрудника не может быть отрицательным, а дата приема его на работу меньше, чем дата его рождения;
в) функциональные связи. Значения данных могут жестко определяться значениями других данных, что характерно для вычисляемых данных.
Например, расход сырья за месяц должен совпадать с суммой ежедневных расходов в данном месяце;
г) специфические требования заказчика. Определяются специфическими особенностями ведения деловых (производственных) процессов в конкретной организации (предприятии).
Например, может быть задано, что в рабочую группу не может входить более пяти человек.

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

1) По области действия.
Учитывается размер части БД, контролируемый ограничением.
а) Ограничение минимального элемента данных.
13 EMBED Visio.Drawing.11 1415
В зависимости от уровня представления данных минимальным элементом может быть свойство, атрибут, поле. Ограничение может предъявляться в виде:
- задания диапазона допустимых значений (например, зарплата сотрудника не может быть ниже минимального размера оплаты труда);
- задания набора допустимых значений (например, состояние установки может принимать значения «Выключено», «Тестовый режим», «Рабочий режим»);
- требования обязательности задания значения (например, задание марки прибора обязательно);
- требования уникальность значения (например, инвентарный номер должен быть уникальным)
Ограничение на значение элемента может быть динамическим, учитывающим переменные факторы. Примером является ограничение перехода, учитывающее текущее и, возможно, предыдущие значения. Например, может быть задано, что переход из состояния «Тестовый режим» в состояние «Рабочий режим» может быть выполнен только через состояние «Выключено».
б) Ограничение, предъявляемое к экземпляру объекта.
13 EMBED Visio.Drawing.11 1415
В зависимости от уровня представления данных экземпляром может быть экземпляр сущности, кортеж отношения, запись таблицы.
Ограничение такого типа задает допустимое соотношение между значениями разных элементов в одном экземпляре объекта (например, дата списания оборудования должна отсутствовать или быть больше даты пуска этого оборудования).
в) Ограничение, предъявляемое к набору экземпляров объектов одного типа.
13 EMBED Visio.Drawing.11 1415
Скорее всего, это будет требование:
- уникальности экземпляров в наборе (например, все сотрудники должны иметь уникальный табельный номер)
- определенного соотношения между данными разных экземпляров объектов (например, максимальная зарплата по сотрудникам не должна превышать среднюю зарплату более чем в 5 раз)
г) Ограничение, предъявляемое к набору экземпляров разных типов объектов.
13 EMBED Visio.Drawing.11 1415
С помощью ограничений этой группы может контролироваться:
- ссылочная целостность (например, значение внешнего ключа дочернего отношения должно совпадать с одним из значений первичного ключа в родительском отношении или быть неопределенным (NULL))
- соотношение между данными разных типов объектов (например, суммарная зарплата сотрудников отдела не должна превышать запланированного для этого отдела фонда оплаты труда).
2) По месту реализации.
Проверка выполнения ограничения выполняется СУБД или приложением. Места реализации ограничения могут различаться не только логически, но и физически, если СУБД и приложение размещены на разных компьютерах
а) Реализация на уровне СУБД.
Может выполняться через декларативное объявление или путем программной реализации.
В первом случае описание ограничения вставляется в описание той части БД, к которой оно предъявляется. Ограничение в данном случае декларируется, то есть указывается, что следует проверять, а не задается программный код для выполнения проверки. Например, фраза fio NOT NULL в описании поля fio указывает, что поле fio не может быть незаполненным. Код выполняющий данную проверку спрятан в СУБД.
Во втором случае программный код проверки в явном виде вводится разработчиком в описание БД (в виде программных триггеров вставки, обновления, удаления), храниться в БД и исполняется СУБД в нужные моменты времени. Этот вариант дает большие возможности разработчику, но и более трудоемок в реализации, чем декларативное объявление;
Достоинство применения ограничения на сервере:
– однократность
– не нужно менять ограничения в клиентских приложениях
– единство ограничения для всех клиентов
б) Реализация на уровне приложения.
В этом случае также пишется программный код. Но код размещается не в БД на сервере, а в приложении на клиентском рабочем месте. В результате проверка выполняется быстрее (если не требуется дополнительных данных с сервера). Кроме того, в приложении можно запрограммировать самые изощренные виды ограничений, не реализуемые на математически и логически ограниченном языке СУБД. Однако реализация ограничений на клиентских местах является децентрализованной и может привести к конфликтам.
3) По способу реакции на нарушение.
Основными стратегиями поведения при обнаружении нарушения являются стратегии запрета и коррекции. В первом случае при нарушении ограничения выполняющаяся операция отменяется, во втором – производится корректировка данных, приводящая к восстановлению целостности. Примерами корректирующих действий являются каскадное удаление подчиненных записей при удалении главной записи и пересчет вычисляемых данных при изменении исходных данных. При контроле ссылочной целостности часто используются также корректирующие стратегии SET NULL (неверное значение внешнего ключа сбрасывается и запись становится свободной) и SET DEFAULT (неверное значение внешнего ключа заменяется на заранее определенное значение по умолчанию, т.е. дочерняя запись присоединяется к заранее определенной главной записи).
Дополнительные стратегии для связей:
– очистка – подчиненная связь становится свободной
– переключение – запись, утратившая связь подключается к заведомо существующей другой записи (SET DEFAUT)
4) По моменту выполнения проверки.
Различают немедленную и отложенную проверку. Первая выполняется сразу после завершения изменений в контролируемой области данных, вторая – откладывается до наступления определенного события. Например, в стандарте языка SQL за такое событие принято завершение транзакции. Кроме того, разработчиком в приложении может быть реализована программным путем сверхотложенная проверка, которая выполняется по явному указанию пользователя.

Таким образом, ограничений целостности при работе с БД может быть задано много и самого разного вида. Ограничения могут задаваться заказчиком до начала проектирования или добавляться разработчиком по ходе проектирования.
Кроме того, одно и то же ограничение на разных этапах проектирования может представляться по-разному.
Например, в описании предметной области может быть указано:
«Каждый сотрудник должен относиться к какому-нибудь отделу»
В инфологической модели это может быть отражено в описании в виде:
«Связь ОТДЕЛ-СОТРУДНИК является обязательной со стороны сотрудника»
В описании логической модели рассматриваемое ограничение может быть представлено в форме:
«Атрибут ОТДЕЛ отношения СОТРУДНИК является внешним ключом к отношению ОТДЕЛ. Данный атрибут является обязательным»
Наконец, при физическом проектировании реализация ограничения может предстать, например, в таком виде:
otdel CHAR(30) NOT NULL REFERENCES otdel

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

Физическое проектирование
13 EMBED Visio.Drawing.11 1415
Решаются задачи:
физическое распределение памяти (размерности файлов, размер страницы, распределение по дискам)
физическая реализация объектов базы
определение дополнительных объектов: индекс или, например, домен в IB, генераторы
определение типа и формата данных
определение реализации хранимых данных
определение прав доступа пользователей
настройка поддержки многопользовательского доступа
определение методов и средств для восстановления данных (параметры копий, зеркало, их размещение)
создание представлений
9. Средства доступа к данным и разработки приложений
Средства доступа к БД предназначены для поддержки работы с БД определенного формата. Они могут быть разделены на:
универсальные
прикладные (проблемно-ориентированные)
Общая схема обращения к данным имеет вид:
13 EMBED Visio.Drawing.11 1415

Универсальные средства
К универсальным средствам доступа относятся соответствующие средства и утилиты СУБД и средства внешних разработчиков.
Их недостатки:
не связаны с конкретной прикладной областью;
работают в терминах операций с БД;
необходимо или желательно знание языка СУБД;
требует высокой квалификации пользователя.
Достоинства:
+ не требуется трудоёмкая разработка приложения
Универсальные средства делятся на две группы:
1) средства и утилиты СУБД:
Примерами таких средств являются:
- интерфейс FoxPro, объединяющий набор команд системного меню, обеспечивающий большое число операций с БД, и набор диалоговых окон работы с БД, таких как View, Browse, Command;
- утилита WISQL, обеспечивающая интерактивный доступ в командном режиме к данным БД Interbase-формата, а также просмотр метаданных БД;
- утилиты: командный или графический интерфейс;
- ServerManager.
2) утилиты сторонних (внешних) разработчиков:
Примерами универсальных средств второй группы являются:
- автономные независимые генераторы отчетов (например, Crystal Report), позволяющие выполнять выборку и обработку данных из БД определенных форматов и оформление выходных документов по полученным результатам;
- автономные независимые генераторы запросов (например, MS Query), служащие для непосредственного задания и (или) интерактивного формирования сложных запросов к БД определенных форматов с целью получения выборок требуемой информации.
В отличие от средств СУБД средства независимых разработчиков обычно позволяют работать с БД нескольких распространенных форматов.
Все универсальные средства объединяет одно свойство: они ориентированы на формат БД, а не на прикладную задачу, которая решается с помощью этой БД. Это позволяет работать с БД разного назначения, но затрудняет работу с данными для малоквалифицированных пользователей, знакомых лишь с предметной областью, но не с терминологией и методологией БД и СУБД.

Прикладные средства
Разработаны для устранения проблем универсальных средств, а именно – сложности для малоквалифицированных пользователей. Для работы широких масс пользователей разрабатываются проблемно ориентированные средства (приложения), интерфейс которых ориентирован на определенную прикладную область деятельности и маскирует внутреннее устройство БД и функционирование СУБД. Терминология и набор функций приложения соответствует прикладной задаче, использует терминологию предметной области и работает на уровне пользовательских операций.
. В результате, вместо абстрактного обозначения операции «Стереть запись» приложение использует более понятное для пользователя обозначение, например, «Отчислить студента» или «Уничтожить документ». Кроме того, пользовательская операция, единая и неделимая с точки зрения пользователя, на уровне СУБД может реализовываться большим числом базовых операций. Все это делает работу для пользователя более простой, понятной, удобной и надежной, что должно компенсировать расходы на разработку приложения.
Для разработки приложений БД имеется большой набор средств разработчика (частью которых является, в частности, рассмотренные выше универсальные средства доступа с БД). Средства разработки можно разделить на 3 основные группы:
1) средства разработчика, реализованные в СУБД. Это языки программирования СУБД (например, XBase, диалектом которого является язык FoxPro), трансляторы, отладчики, утилиты работы с БД, библиотеки и наборы компонент, реализующие типовые функции и элементы интерфейса.
2) дополнительные средства универсальных языков программирования, расширяющие возможности языка средствами работы с БД (например, набор компонентов работы с БД для С++). Сюда же можно отнести стандартизированные средства доступа с БД, также как ODBC, DAO, ADO, BDE, а также внешние программные интерфейсы (API), предоставляемые большинством разработчиков СУБД.
3) интегрированные средства разработки, предлагаемые независимыми поставщиками. Такие средства, в отличие от средств СУБД, позволяют, как правило, работать с большим числом распространенных форматов БД. Примером независимого средства разработки является пакет Power Builder, позволяющий создавать приложения для работы с большинством форматов распространенных серверных и некоторых персональных СУБД. Также получили распространение C++ Builder, Delphy.

При выборе средств разработки следует учитывать:
1) поддерживаемую рассматриваемыми средствами модель БД и модель обработки;
2) развитость предоставляемого инструментария;
3) совместимость получаемых результатов с имеющимися разработками;
4) наличие рассматриваемых средств и их стоимость при отсутствии;
5) наличие опыта работы с рассматриваемыми средствами.
При работе с БД используются различные технологии доступа:
- низкий уровень (API),
- средний уровень (ODBC),
- высокий уровень (BDE, IBExpress, ADO).

СУБД
Основным средством работы с данными является СУБД.
Основные задачи СУБД:
создание и модификация БД
ввод и актуализация данных
развитие БД
поддержка разработки приложений
поддержка многопользовательского доступа
поддержка ограничений целостности
поддержка контроля доступа
поддержка резервирования и восстановления
Наиболее распространенными СУБД являются:
1) Персональные системы:
MS Access: средство для конечного пользователя
VFP: средство для разработчика
Семейство X-Base (FoxPro, DBase), Paradox, Clarion
Для персональных систем характерны файл-серверная структура, наличие копии СУБД на каждом рабочем месте.
13 EMBED Visio.Drawing.11 1415
2) Серверные системы:
MS SQL Server
Oracle
InterBase
My SQL: быстрая, бесплатная, сильно урезана
DB: очень старая
Для серверных систем характерны: наличие клиентской и серверной частей, потоков обмена в SQL-серверах.

13 EMBED Visio.Drawing.11 1415


Состав СУБД:
- ядро;
- интерфейсы пользователя;
- средства обмена с приложениями;
- средства разработки;
- утилиты обслуживания.

Общая схема обработки обращений в СУБД:
13 EMBED Visio.Drawing.11 1415
1) Контроль доступа: если команда разрешена, то она принимается к обработке, иначе сообщение о нарушении прав доступа
2) Процессор команд: анализ команды, перенаправление на обработку.
3) Контроллер целостности: проверяются ограничения целостности для команд ввода модификаций.
4) Обработчик запросов: основная часть – оптимизатор запросов, определяет возможные планы исполнения запросов, выбирает наилучший (он может из одной команды сделать несколько).
5) Планировщик: из параллельно поступающих потоков информации формирует единый поток.
6) Контроллер данных: обеспечивает выполнение операций с данными, при выполнении происходит обмен с диском через буфера, при выполнении взаимодействует с файловой системой.
7) Контроллер транзакций: хранит историю и состояние транзакций, управляет их поведением.

Наиболее применяемые СУБД (2002г.):
- MS SQL Server (32,3%),
- Oracle (16,1%),
- InterBase (12,6%),
- MySQL (10,2),
- MS Access (6,6%),
- Visual FoxPro (4,5%).
10. Язык SQL
Стандартизированный язык работы с данными через СУБД реализован в разном объеме во всех реляционных СУБД. Назначение – определение структуры данных, актуализация данных, выборка данных, исполнение служебных функций.
История создания:
Прототип SQL обнародован в 1974 году, назывался он SEQUEL. (Структурированный (S) английский (E) язык (L) формулирования запросов (QUE)). Начало коммерческой реализации – основной вариант в системе Oracle.
В 1986 – стандартизация языка в США, под аббревиатурой SQL, в 1987 – международный стандарт, под названием SQL1 или SQL-87. 1989 год – вторая редакция SQL1 или SQL-89. В первом стандарте определены основные операторы языка
В 1992 – разработан SQL2 или SQL-92. Полный реляционный стандарт, стандартизация работы с метаданными по аналогии с работой с пользовательскими данными (если ранее стандартизировалась работа с пользовательскими таблицами, теперь пошли далее, раньше данные служебные, описание БД, генераторы и триггеры, хранились, как попало, теперь и служебную данные хранятся как таблицы, так же стандартизовано, в “служебных таблицах”).
С появлением объектно-ориентированного программирования и объектно-ориентированных БД, стали думать над расширением стандарта SQL2. В это время не было, какой то одной организации, которая диктовала бы стандарт, все создавали свои стандарты. И в 1999 году создан стандарт SQL3 (SQL-99). Он собрал только самую вершину, того, что было общим. Стандарт превратился в рекомендацию. Весь стандарт разделили на уровни – начальный, стандартный и полный. Обычно в СУБД поддерживается чуть больше начального уровня.
Язык SQL близок к классу языков реляционного исчисления кортежей и используется в основном в реляционных СУБД. Но в связи с его очень широким применением имеются попытки реализации SQL и в других классах систем.
SQL является языком высокого уровня. Пользователь не должен при его использовании помнить об открытии и закрытии каких-либо таблиц, определять наиболее эффективный способ реализации запроса, активизировать индексы и т.п. Все это система делает автоматически.
В составе языка SQL2 можно выделить следующие основные группы операторов и средств:

1. Основные составляющие языка SQL.
1.1. Команды определения данных:
– CREATE SCHEME – создать базу данных (определён в стандарте SQL. Для аналогичных целей в некоторых СУБД имеется оператор CREATE DATABASE).
– CREATE TABLE – создание таблицы базы данных. Таблица определяется путем задания содержащихся в ней столбцов. Все значения в столбце имеют один и тот же тип данных. При описании таблиц могут задаваться ограничения целостности данных.
– CREATE DOMAIN – создание домена (объявление пользовательского типа данных, включает определение типа данных, ограничение и значение по умолчанию). Домен имеет смысл создавать, когда определенный с его помощью тип данных используется в создаваемой базе данных многократно. При описании таблицы для соответствующих полей вместо типа данных будет указываться имя домена.
– CREATE VIEW – создание виртуальной таблицы (представления, обзора). Представление - это виртуальная таблица, данные для которой получаются из базовых таблиц или других представлений. Представление может быть получено из одной таблицы или нескольких, может включать в себя вычисляемые поля. Представление можно рассматривать как хранимый запрос (оно и выражается с помощью запроса). Представление может использоваться в запросах наряду с реальными таблицами. Упрощает создание сложных запросов, используется для обеспечения защиты и ускорения работы с БД. В результате, в БД хранится не сама табличная информация, а лишь способ ее оперативного получения. Использование представлений позволяет скрыть от пользователя излишние для него детали организации БД, реализовать дополнительные возможности контроля доступа к данным, минимизировать объем передаваемой и обрабатываемой информации.
– CREATE CURSOR – создание навигационной таблицы (курсора).
К этой группе также относятся операторы изменения и уничтожения описаний, операторы работы с описаниями вспомогательных объектов БД.
1.2. Команды удаления (DROP) и изменения (ALTER) объектов.
Например, таблицы могут быть удалены с помощью оператора DROP TABLE, а структуру существующей таблицы можно изменять с помощью оператора ALTER TABLE.

2. Методы и средства контроля целостности в основном реализованы в CREATE TABLE:
Имеющиеся в языке возможности позволяют задать в описаниях данных следующие свойства:
– NOT NULL – обязательность.
– UNIQUE – уникальность.
– DEFAULT – значение по умолчанию.
– CHECK – условие ограничения.
– PRIMARY KEY, FOREIGN KEY – поддержка связей.
– ON UPDATE, ON DELETE – триггеры по умолчанию.
Связь осуществляется за счет указания соответствия первичных и внешних ключей FK=PK, отсутствие связи – указанием FK=NULL, при нарушении ссылочной целостности FK=прочее. Возможные реакции триггера задают, что делать с внешним ключом, если произошло нарушение ссылки:
1) CASCADE – если при выполнении действия (удаления, изменения) – выполняем то же действие и с подчиненной.
2) SET NULL – если при выполнении указанной операции произошел разрыв связи, то мы значение внешнего ключа очищаем.
3) SET DEFAULT – если при выполнении указанной операции произошел разрыв связи, то мы значение внешнего ключа меняем на значение по умолчанию.
4) NO ACTION – ничего не делать, во многих системах заменено на RESTRICT.

3. Операторы модификации данных:
– INSERT – добавление данных,
– UPDATE – обновление данных,
– DELETE – удаления данных.

4. Выборка:
– SELECT. Оператор состоит из предложений SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY, которые должны быть записаны в команде именно в той последовательности, в которой они перечислены в синтаксической формуле.

5. Управление доступом:
– GRANT – назначение прав доступа.
Предположим, пользователь является владельцем таблицы «Sotrudnik» и хочет позволить пользователю Ivanov выполнять запросы к ней. В этом случае пользователь должен ввести команду
GRANT SELECT ON Sotrudnik TO Ivanov;
– REVOKE – удаление прав доступа.
Команда имеет синтаксис, схожий с синтаксисом оператора GRANT. Например, отмена привилегии на просмотр таблицы «Sotrudnik» для пользователя Ivanov будет выглядеть следующим образом:
REVOKE SELECT ON Sotrudnik TO Ivanov;

6. Управление транзакциями:
Транзакция представляет собой законченную совокупность действий над БД, которая переводит ее из одного целостного в логическом смысле состояния в другое.
– SET TRANSACTION – задает параметры транзакции, объявляет её начало.
– COMMIT – нормальное завершение, завершение транзакции с фиксацией всех результатов.
– ROLLBACK – завершение транзакций с отменой всех выполненных изменений.
Конкретные СУБД используют различные механизмы управления транзакциями. Некоторые СУБД для задания транзакции используют операторы BEGIN TRANSACTION-END TRANSACTION, и все команды, заключенные между ними, составляют транзакцию. В некоторых системах считается, что, инициируя сеанс работы с SQL, пользователь начинает транзакцию, которая будет продолжаться, пока не будет введен оператор COMMIT WORK, который сделает все изменения, проведенные в ходе транзакции, постоянными, или оператор ROLLBACK WORK, который отменяет все сделанные в транзакции изменения. После каждого оператора COMMIT или ROLLBACK начинается новая транзакция.
Во многих СУБД присутствует специальный параметр AUTO-COMMIT, который, находясь во включенном состоянии, приводит к автоматической фиксации изменений каждой нормально завершенной операции.
Транзакция может быть помечена как «только чтение» (READ ONLY). При выполнении такой транзакции попытка провести изменение данных будет вызывать сообщение об ошибке. Задание признака READ ONLY позволяет увеличить производительность как этой, так и параллельно исполняемых транзакций.
Транзакции должны соответствовать требованиям ACID (Atomicity, Consistency, Isolation, Durability – Атомарность, Согласованность, Изолированность, Долговечность):
Атомарность: транзакция представляет собой некоторый набор законченных действий. Система обеспечивает их выполнение по принципу «все или ничего» - либо выполняются все действия, тогда транзакция «фиксируется»; либо, если возможность выполнить все действия отсутствует, например в случае сбоев, транзакция «откатывается» назад, а БД остается в исходном состоянии.
Согласованность: предполагается, что в результате выполнения транзакции система переходит из одного корректного состояния в другое.
Изолированность: при выполнении транзакции данные могут временно находиться в несогласованном состоянии. Такие данные не должны быть видны другим транзакциям, пока изменения не будут завершены (т.е. пока все модификации не будут формально зафиксированы). Система обеспечивает каждой транзакции иллюзию того, что та выполняется изолированно, как если бы прочие транзакции либо завершились до ее начала, либо начнут выполняться после ее завершения.
Долговечность: если транзакция зафиксирована, то ее результаты должны быть долговечными. Новые состояния всех объектов сохранятся даже в случае аппаратных или системных сбоев.
Существуют многочисленные модели транзакций, обеспечивающие соблюдение требований ACID. Некоторые из этих моделей:
- плоские транзакции;
- контрольные точки;
- многозвенные транзакции;
- вложенные транзакции.

Использование языка SQL:
В целом, язык SQL не является самодостаточным для создания приложений БД и их полномасштабного обслуживания. Поэтому разработчикам приложений предоставляется различные формы соединения языка SQL с другими (внешними) языками.
В персональных системах язык используется как часть основного языка.
В серверных системах он используется в следующих вариантах:
1) как вспомогательный язык приложения для обращения к СУБД.
2) как средство интерактивных запросов.
3) как средство написания программного кода для серверной части.
Для объединения SQL с базовым языком приложения используются следующие методы:
1. Локальный SQL.
Операторы SQL включаются во внешний язык наравне с прочими операторами и обрабатываются расширенным транслятором внешнего языка как его «родные» операторы. Таким образом, имеет место расширение исходного языка на группу операторов SQL с соответствующим расширением транслятора. Этот вариант характерен для персональных СУБД.
2. Встроенный SQL.
В текст программы на внешнем языке операторы SQL включаются с явным их выделением. Например, встраивание операторов SQL в текст С-программы выполняется в виде:
EXEC SQL

END SQL
При обработке пакета программы предварительно выполняется программа предтранслятор, которая преобразует SQL-вставки в эквивалентные конструкции внешнего языка, после чего выполняется трансляция с помощью стандартного транслятора внешнего языка. Обмен данными между SQL-вставками и основным кодом программы производится через явно указываемый набор переменных связи.
3. Модульный SQL.
Операторы SQL размещаются в модулях-подпрограммах, обращение к которым осуществляется по стандартным правилам базового языка. В модульном SQL обмен выполняется через входные и выходные параметры процедур.
4. Динамический SQL – поддерживает ввод, трансляцию и исполнение SQL команд в ходе выполнения программы. Операторы SQL определяются не на момент создания пакета программы, а на момент ее исполнения. Таким образом, трансляция SQL-операторов откладывается на время выполнения программы, что позволяет реализовывать заранее непредвиденные запросы. Для подготовки исполнения используется команда PREPARE, для исполнения EXECUTE.

11. Создание БД в SQL
Для первичного создания БД требуемая последовательность операторов SQL обычно оформляется в виде скрипта. Исполнение скрипта приводит к получению пустой БД требуемой структуры.
В стандарте SQL-92 определяются следующие виды объектов, которые могут быть созданы в БД:
Table - таблица;
View - представление;
Schema ~ схема;
Domain - домен;
Assertion - утверждение;
Character set - набор символов;
Collation - последовательность сортировки;
Translation - преобразование одного набора символов в другой.
Ниже будут рассмотрены вопросы создания таблиц и доменов. Последовательность шагов создания БД может быть, например, следующей:

1. Оператор создания схемы БД
Данный оператор специфичен для различных СУБД. В некоторых СУБД имеется оператор CREATE DATABASE. В стандарте SQL для аналогичных целей используется оператор CREATE SCHEMA. Упрощенный синтаксис оператора создания БД для СУБД Interbase имеет вид:

CREATE {DATABASE | SCHEMA} "<файл>"
USER "<имя>" PASSWORD "<пароль>";

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

2. Оператор создания домена
Домен  допустимое потенциальное ограниченное подмножество значений данного [ Cкачайте файл, чтобы посмотреть ссылку ]. Например, домен ИМЕНА определен на базовом типе строк символов, но в число его значений могут входить только те строки, которые могут представлять имена (в частности, для возможности представления русских имен такие строки не могут начинаться с мягкого или твердого знака и не могут быть длиннее, например, 20 символов). В один домен могут входить значения из нескольких колонок, объединённых, помимо одинакового типа данных, ещё и логически. Если два значения берутся из одного и того же домена, то можно выполнить сравнение этих двух значений.
Более простое определение домена  это допустимое потенциальное множество значений одного типа.
Домен представляет собой описание типа столбца, которое может использоваться как шаблон при создании конкретных столбцов таблиц БД. При создании домена можно задать альтернативный тип данных, значение по умолчанию и такие ограничения целостности как NOT NULL и CHECK. Упрощенный синтаксис оператора имеет вид:

CREATE DOMAIN <домен> [AS] <тип>
[DEFAULT <значение> ]
[NOT NULL]
[CHECK ( <условие>)];

Здесь <домен> - уникальное внутри БД имя, присваиваемое домену,
<тип>- тип данных домена. Упрощенный набор типов данных имеет вид:
INTEGER - целочисленное данное,
FLOAT - численное данное с плавающей точкой,
NUMERIC(n,m) - численное данное с фиксированной точкой
(n - всего знаков, m - знаков после точки),
DATE – данное типа календарная дата,
CHAR(n) – символьная строка (n – длина строки),
NOT NULL – требование обязательности заполнения позиций столбца (в явном виде или значением по умолчанию),
<значение> - значение, автоматически заносимое в позицию столбца при создании новой строки, если эта позиция не заполнена пользователем. Значение по умолчанию чаще всего задается константой соответствующего типа.
<условие> - условное выражение, которое должно проверяться после ввода или изменения значения в столбце. Если условие для нового значения данного выполняется, то новое значение принимается, в противном случае – отвергается.

3. Оператор создания таблицы
База данных обычно содержит несколько таблиц, а также и индексы и некоторые другие информационные объекты.
SQL оперирует с данными, представленными в виде таблиц. Каждая таблица содержит множество строк. Различают базовые таблицы – таблицы, определенные с помощью их описания на языке описания данных, и производные таблицы, получаемые из одной (или нескольких других) таблицы путем выполнения некоторого запроса. Базовые таблицы бывают постоянные или временные. Если создается временная таблица, то используется параметр TEMPORARY. В этом случае при определении таблицы должны быть указаны дополнительные параметры GLOBAL или LOCAL.
Таблица описывается с помощью оператора CREATE TABLE. Таблица определяется путем задания содержащихся в ней столбцов. Все значения в столбце имеют один и тот же тип данных. При описании таблиц могут задаваться ограничения целостности данных.
Следующий оператор создает новую таблицу в существующей БД. Упрощенный синтаксис оператора имеет вид:

CREATE TABLE <таблица>
( <определение столбца>
[, {<определение столбца> | <ограничение таблицы>}, ]);

Здесь <таблица> - уникальное внутри БД имя, присваиваемое таблице,
<определение столбца> - описание столбца таблицы, которое может основываться на ранее определенном домене, а также содержать ограничения целостности, предъявляемые к вводимым в столбец значениям. Таблица должна содержать хотя бы один столбец.
<ограничение таблицы> - описание ограничения целостности, предъявляемого к сочетанию значений, введенных в строку таблицы в нескольких столбцах. В описании таблицы может определяться несколько ограничений таблицы.
В определениях столбцов и в ограничениях таблицы могут также задаваться ограничения ссылочной целостности для поддержки связей между данными в разных таблицах.
Упрощенный синтаксис определения столбца имеет вид:

< определение столбца > = <столбец > {< тип > | <домен >}
[DEFAULT <значение> ]
[NOT NULL]
[ <ограничение столбца>, ]

Здесь <столбец> - уникальное внутри таблицы имя, присваиваемое столбцу,
{< тип> | <домен>} – тип данных столбца или домен, свойства которого наследует столбец,
DEFAULT, NOT NULL – аналогичны объявлениям, рассмотренным для домена,
<ограничение столбца> - требование, которое должно выполняться для вводимых в столбец значений. Набор видов ограничений столбца имеет вид:
UNIQUE – требование уникальности значений в столбце;
PRIMARY KEY – объявление столбца первичным ключом. Это автоматически накладывает требование уникальности на значения в столбце. Кроме того, для столбца должно быть явно указано требование NOT NULL;
Ограничение столбца представляется в виде ограничений ссылочной целостности и ограничений по значению:
REFERENCES <таблица> [(<столбец>)]
[ON DELETE
{NO ACTION | CASCADE | SET DEFAULT | SET NULL}]
[ON UPDATE
{NO ACTION | CASCADE | SET DEFAULT | SET NULL}]
- ограничение ссылочной целостности.
CASCADE - каскадное удаление или изменение внешних ключей с соответствии с удалением или изменением в главной таблице;
SET DEFAULT – установка некорректных значений внешних ключей в заданное для столбца значение по умолчанию;
SET NULL – очистка позиций некорректных значений внешних ключей путем записи в них значения NULL.
CHECK (<предикат>) – ограничивающее условие, проверяемое при вводе или изменении значения в столбце. Предикат использует значения столбцов в выражении для вычисления значения
Простыми формами задания условия являются:
<столбец> <оператор сравнения > <значение>,
<столбец > [NOT] BETWEEN <значение> AND <значение>,
<столбец > [NOT] IN (<список значений>),
<столбец > IS [NOT] NULL.
Предикат может принимать значения TRUE, FALSE или UNKNOWN. Ограничение считается нарушенным, когда предикат принимает значение FALSE.
Более сложные условия задаются с использованием кванторов и операторов выборки. Также как для домена простые условия могут соединяться в более сложные с помощью логических функций AND, OR и NOT.
Ограничения таблицы аналогичны ограничениям столбца, но предъявляются не к одному столбцу, а к набору столбцов:
PRIMARY KEY (<список столбцов>) – объявление набора столбцов первичным ключом;
UNIQUE (<список столбцов>) – требование уникальности сочетаний значений в наборе столбцов,
FOREIGN KEY (<список столбцов>) REFERENCES <таблица>
ON DELETE {NO ACTION | CASCADE | SET DEFAULT | SET NULL}]
ON UPDATE {NO ACTION | CASCADE | SET DEFAULT | SET NULL}]
- объявление набора столбцов внешним ключом;
CHECK ( <предикат>) – задание ограничивающего условия, включающего значения из нескольких столбцов.
Ниже приведен пример описания трех связанных таблиц: «Spr_mat» справочник материалов, «Spr_post» справочник поставщиков и «Post» - таблица, содержащая информацию о поставках. При включении в базу данных информации о конкретной поставке должно проверяться наличие вводимых значений кода материала (kod_mat) и кода поставщика (kod_post) в соответствующих справочниках.

CREATE TABLE spr_mat
(kod_mat CHAR(3) NOT NULL PRIMARY KEY,
naim_mat CHAR (30) NOT NULL UNIQUE);

CREATE TABLE spr_post
(kod_post CHAR(5) NOT NULL,
naim_post CHAR (30) NOT NULL,
PRIMARY KEY (kod_post),
UNIQUE (naim_post));

CREATE TABLE post
(kod_post CHAR(5) NOT NULL,
kod_mat CHAR(3) NOT NULL,
data_post DATE NOT NULL,
kolv NUMERIC NOT NULL,
PRIMARY KEY (kod_post, kod_mat, data_post),
FORIGN KEY (kod_mat) REFERENCES spr_mat (kod_mat),
FORIGN KEY (kod_post) REFERENCES spr_post (kod_post));

Структуру существующей таблицы можно изменять с помощью оператора ALTER TABLE.

ALTER TABLE <имя таблицы>
[ADD [COLUMN] <определение столбца>]
| [ALTER [COLUMN] <имя столбца> <изменяющее действие>]
| [DROP [COLUMN] <имя столбца> RESTRICT | CASCADE]
| [ADD <определение ограничения для таблицы>]
| [DROP CONSTAINT <имя ограничения> RESTRICT | CASCADE];

изменяющее действие::=
[SET DEFAULT <значение по умолчанию>] | [DROP DEFAULT]

Как видно, с помощью оператора ALTER TABLE можно добавить новый столбец в таблицу, изменить определение существующего столбца, добавив/удалив значение по умолчанию, добавить/удалить ограничения целостности, а также удалить столбец из таблицы. При удалении столбца, если будет использован параметр RESTRICT, то в случае наличия каких-либо ссылок на этот столбец (в представлениях, ограничениях, условиях) оператор будет отвергнут. Если же будет использован параметр CASCADE, то все объекты, имеющие ссылки на этот столбец, будут уничтожены.
Оператор ALTER TABLE присутствует не во всех СУБД. Часто реализация этого оператора не полностью соответствует стандарту.
Таблицы могут быть удалены с помощью оператора DROP TABLE.

4. Оператор фиксации результатов работы с БД
COMMIT;
Данный оператор фиксирует результаты выполнения предшествующих операторов.

12. Выборка данных в SQL
ОПЕРАТОР ВЫБОРКИ SELECT
Оператор выборки SELECT предназначен для описания и исполнения запросов к БД на выборку данных. Он является наиболее проработанным и идеологически важным оператором языка SQL. Основная форма оператора имеет вид:
SELECT <поля выборки>
FROM <таблицы>
WHERE <условия отбора записей>
GROUP BY <поля группирования>
HAVING <условия отбора группы>
Оператор описывает:
- откуда брать данные,
- каким требованиям должна удовлетворять отобранная информация,
- в каком виде представить результаты выборки.
Таким образом, в операторе SELECT определяется, «что должно быть получено», а не «как это получить», что показывает связь оператора SELECT с реляционным исчислением. Дополнительно оператор SELECT включает нереляционные операции.
Исполнение оператора SELECT можно представить последовательностью действий:
1) Формирование единой таблицы:
Формирование выполняется в соответствии с информацией, заданной фразой FROM. Во фразе FROM перечисляются через запятую входные элементы. Элементом может быть исходная таблица или соединение исходных таблиц.
Соединение таблиц задается в виде:
<таблица1> <вид соединения> JOIN <таблица2> ON <условие>
Вид соединения может принимать значения:
INNER – внутреннее соединение: содержит все соединения записей, для которых выполняется заданное условие
LEFT – левое внешнее соединение: к допустимым соединениям записей добавляются соединения с пустой строкой для записей таблицы 1, не имеющих соответствия в таблице 2. Таким образом, в таблицу соединения хотя бы однократно входят все записи таблицы 1 (левой таблицы соединения)
RIGHT – правое внешнее соединение: к допустимым соединениям записей добавляются соединения с пустой строкой для записей таблицы 2, не имеющих соответствия в таблице 1.
FULL – полное внешнее соединение: в результат соединения включаются все записи как левой, так и правой таблицы соединения.
После формирования соединений общая таблица образуется декартовым произведением полученных табличных элементов. Декартово произведение также образуется соединениями строк, но допустимыми являются все сочетания.
Пример:
Таблица «А_сотрудники» содержит сведения о сотрудниках фирмы X:
Таб_ном
ФИО

01
Диго

02
Афанасьев

03
Сидоров

Таблица «Б_разработки» содержит информацию о том, какие программные продукты разработаны в фирме X и кто является автором каждой разработки.
ФИО
Продукт

Диго
П1

Диго
П2

Афанасьев
П3

Чистов
П4

Если в предложении FROM перечислено несколько таблиц, то все они неявно считаются соединяемыми. Если тип соединения явно не задан, то считается, что каждая строка первой таблицы соединяется с каждой строкой второй таблицы. Такое соединение и называется перекрестным.
Результат перекрестного соединения для приведенных выше таблиц представлен ниже.
Таб_ном
А_сотрудники.фио
Б_разработки.фио
Продукт

01
Диго
Диго
П1

01
Диго
Диго
П2

01
Диго
Афанасьев
ПЗ

01
Диго
Чистов
П4

02
Афанасьев
Диго
П1

02
Афанасьев
Диго
П2

02
Афанасьев
Афанасьев
ПЗ

02
Афанасьев
Чистов
П4

03
Сидоров
Диго
Ш

03
Сидоров
Диго
П2

03
Сидоров
Афанасьев
ПЗ

03
Сидоров
Чистов
П4

Запрос на SQL может иметь следующий вид:
SELECT а_сотрудники.таб_ном, а_сотрудники.фио, б_разработки.фио, б_разработки.продукт
FROM а_сотрудники, б_разработки;
Чаще всего при создании запросов используется тип соединения INNER JOIN, при котором соединенная таблица будет включать только те строки, для которых есть соответствующие друг другу значения полей связи в обеих таблицах.
Результат соединения типа INNER JOIN для приведенных выше таблиц представлен ниже.
Таб_ном
ФИО
Продукт

01
Диго
П2

01
Диго
П1

02
Афанасьев
ПЗ

Этот запрос показывает разработки, выполненные сотрудниками фирмы X.
На SQL такой запрос будет иметь следующий вид:
SELECT а_сотрудники.таб_ном, а_сотрудники.фио, б_разработки.продукт
FROM а_сотрудники INNER JOIN б_разработки
ON а_сотрудники.фио = б_разработки.фио;
При использовании соединения типа LEFT JOIN в результатную таблицу попадают все записи из первой таблицы и только те записи из второй таблицы, для которых есть соответствующие значения полей связи в первой таблице. Соединение типа LEFT JOIN для рассматриваемого примера даст в результате список всех сотрудников фирмы X с указанием их разработок:
Таб_ном
ФИО
Продукт

01
Диго
П2

01
Диго
П1

02
Афанасьев
ПЗ

03
Сидоров
Null

На SQL такой запрос будет выглядеть следующим образом:
SELECT а_сотрудники.таб_ном, а_сотрудники.фио, б_разработки.продукт
FROM а_сотрудники LEFT JOIN б_разработки
ON а_сотрудники.фио = б_разработки.фио;
При использовании соединения типа RIGHT JOIN, напротив, в результатную таблицу попадают все записи из второй таблицы и только те записи из первой таблицы, для которых есть соответствующие значения полей связи во второй таблице. Соединение типа RIGHT JOIN для рассматриваемого примера даст в результате список всех продуктов с указанием разработчика и его табельного номера:
Таб_ном
ФИО
Продукт

01
Диго
П1

01
Диго
П2

02
Афанасьев
ПЗ

Null
Чистов
П4

На SQL такой запрос будет выглядеть следующим образом:
SELECT а_сотрудники.таб_ном, б_разработки.фио, б_разработки.продукт
FROM а_сотрудники RIGHT JOIN б_разработки
ON а_сотрудники.фио = б_разработки.фио;
Во всех приведенных выше примерах предполагалось, что условием соединения является равенство значений полей связи. Обычно именно этот тип сравнения и используется.
FULL JOIN для нашего примера даст следующий результат:
Таб_ном
ФИО
Продукт

01
Диго
П1

01
Диго
П2

02
Афанасьев
ПЗ

03
Сидоров
Null

Null
Чистов
П4


2) Ограничение единой таблицы по строкам:
Данная операция выполняется при наличии фразы WHERE, которая содержит условие ограничения.
Условие проверяется для каждой записи единой таблицы. При невыполнении условия запись исключается из единой таблицы. Условие выборки включает одно или несколько простых условий. При наличии нескольких простых условий они объединяются в условие ограничения с помощью логических функций AND и OR.
Простые условия могут иметь следующие формы:
<поле> <сравнение> <выражение>
Выполняется сравнение значения поля со значением выражения. Для задания вида сравнения используются символы < > = и их сочетания. Сравнение «не равно» может быть задано в виде != или <>.
<поле> IS NULL
<поле> IS NOT NULL
Выполняется проверка отсутствия или наличия значения поля.
Например, если в таблице «Сотрудник» (sotr) есть поле «Ученая_степень» (ych_st), то запрос, выводящий список сотрудников, не имеющих ученых степеней, будет выглядеть следующим образом:
SELECT fio FROM sotr WHERE ych_st IS NULL;
<поле> BETWEEN <выражение> AND <выражение>
<поле> NOT BETWEEN <выражение> AND <выражение>
Выполняется проверка попадания значения поля в заданный интервал или вне интервала.
<поле> IN (<список>)
<поле> NOT IN (<список>)
Выполняется проверка наличия или отсутствия значения поля в заданном наборе значений. Набор значений может быть создан запросом SELECT, т.е. условие может иметь форму: <поле> IN (оператор SELECT).
EXISTS (оператор SELECT)
NOT EXISTS (оператор SELECT)
Выполняется проверка наличия или отсутствия записей в выборке, выполненной с использованием данных проверяемой записи.
<поле> <сравнение> ALL (оператор SELECT)
Выполняется проверка выполнения условия сравнения для каждого элемента набора, созданного запросом SELECT.
<поле> <сравнение> ANY (оператор SELECT)
Выполняется проверка выполнения условия сравнения хотя бы для одного элемента набора, созданного запросом SELECT.

В выражении, использующемся для сравнения, разрешается применять заполнители (трафаретные символы):
символ подчеркивания (_) - используется вместо любого единичного символа в проверяемом значении;
символ процента (%) - заменяет набор любых символов в проверяемом значении.
Предположим, что коды металлов начинаются с буквы «м». Тогда запрос, позволяющий вывести сведения о поставке металлов, будет иметь вид
SELECT * FROM post WHERE kod_mat LIKE "м%";

3) Отбор выходных столбцов выборки:
Во фразе SELECT перечисляются через запятую выходные элементы. Выходным элементом может быть поле таблицы, задаваемое именем, или вычисляемое поле, задаваемое выражением.
Для уточнения ссылки на поле может быть указан псевдоним его таблицы в виде:
<псевдоним>.<поле>.
Псевдоним - имена, которые станут заголовками столбцов вместо исходных названий столбцов в таблице
Для элемента может быть задан псевдоним в виде:
<элемент> AS <псевдоним>.
Задание псевдонима позволяет присвоить имена вычисляемым полям, разрешить конфликты совпадения имен и определить понятный пользователю заголовок.
Кроме задания выходного списка фраза SELECT может содержать необязательные опции, ограничивающие дублирование выходных строк выборки. Ограничение повтора может принимать значения:
- ALL – повторяющиеся записи включаются в выборку (значение по умолчанию);
- DISTINCT – повторяющиеся записи не включаются в выборку.
Примечание: символ * задает включение всех имеющихся столбцов в выходной список без необходимости полного перечисления.

4) Группирование строк таблицы выборки:
Фраза GROUP BY содержит список полей, по которым выполняется группировка. Группирование используется для определения групп выходных строк, к которым могут применяться те или иные агрегатные функции. Предложение GROUP BY обычно используется со встроенными агрегатными функциями. Если агрегатные функции используются без предложения GROUP BY, то они будут применяться ко всему набору строк, удовлетворяющему условию запроса.
Поле группировки может быть задано именем или порядковым номером в выходном списке. Для группы формируется итоговая запись, в полях которой размещается агрегированная по группе информация.
Агрегирование данных выполняется с помощью функций:
COUNT(<выражение>) – количество записей в группе;
SUM(<выражение>) – суммарное значение выражения по записям группы;
MIN(<выражение>) – минимальное значение выражения по записям группы;
MAX(<выражение>) – максимальное значение выражения по записям группы;
AVG(<выражение>) – среднее значение выражения по записям группы.
При использовании группировки выходной список должен содержать только элементы, имеющие постоянное значение внутри группы (например, поля группировки) или являющиеся агрегированными функциями.
Например, в таблице «Zarpl», содержащей сведения о заработной плате рабочих, имеются колонки FIO (фамилия, инициалы), «ТаbNum» (табельный номер), «Uch» (участок), «Zpl» (заработная плата). Требуется определить среднюю заработную плату по каждому участку:
SELECT uch, AVG(zpl)
FROM zarple
GROUP BY uch;
В данном примере рассматривается группировка по одной колонке. В принципе можно группировать строки таблицы по любой комбинации ее колонок. В этом случае имена колонок в предложении GROUP BY перечисляются через запятую.

5) Ограничение по групповым строкам:
Данная операция выполняется при наличии фразы HAVING. Она задает условие ограничения для групповых строк аналогично тому, как фраза WHERE задает условие ограничения для исходных строк. Обычно используется вместе с фразой GROUP BY.
Например, запрос на выдачу списка кодов тех материалов, по которым было выполнено более чем по одной поставке, будет выглядеть следующим образом:
SELECT codmat
FROM post
GROOUP BY codmat
HAVING COUNT(*)>1;
Выражение во фразе HAVING должно принимать единственное значение для группы. Формат COUNT(*) означает подсчет всех строк таблицы.

6) Объединение выборки:
Данная операция выполняется при наличии фразы UNION.
Объединяет результаты двух или более запросов в один результирующий набор, в который входят все строки, принадлежащие всем запросам в объединении. Основные правила объединения результирующих наборов нескольких запросов с помощью операции UNION:
- Количество и порядок столбцов должны быть одинаковыми во всех запросах.
- Типы данных должны быть совместимыми.
Операция UNION указывает на то, что несколько результирующих наборов следует объединить и возвратить в виде единого результирующего набора.
Пример:
SELECT ProductModelID, Name
FROM Production
UNION
SELECT ProductModelID, Name
FROM Gloves;

7) Упорядочивание записей выборки:
Данная операция выполняется при наличии фразы ORDER BY.
Она содержит список полей, по которым выполняется упорядочивание. Каждое поле упорядочивания должно присутствовать в выходном списке.
Порядок сортировки определяется порядком следования полей в списке упорядочивания. Сначала выполняется сортировка по первому полю списка, затем внутри каждой сортировочной группы – по второму полю и т.д.
После каждого поля можно указать направление сортировки по этому полю.
Допустимыми значениями указателя сортировки являются ASC (по возрастанию) и DESC (по убыванию).
При использовании фразы UNION упорядочивание может быть задано только однократно. Фраза ORDER BY в этом случае размещается в самом конце и относится ко всему объединению.
Например, следующая инструкция позволяет получить список лучших студентов выпуска 2002 г., средний балл которых больше 4,5:
SELECT Имя, Фамилия
FROM Студенты
WHERE ГодВыпуска =2002
AND СреднийБалл>4.5
ORDER BY СреднийБалл DESC;

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

13 EMBED Visio.Drawing.11 1415

Буфер данных – для временного хранения обрабатываемых данных. Данные записываются в буфер, который находится в ОЗУ. Он может быть как на стороне сервера, так и клиента.
Буфер журнала (операций или транзакций) – для буферирования текущей информации по операциям изменения.
Оперативная база данных – база данных, с которой выполняется работа.
Журнал – хранит историю операций с данными.
Архив данных – хранятся резервные копии оперативной базы данных.
Архив журнала – хранятся сведения об операциях, не требующих оперативной работы.

НОРМАЛЬНЫЙ РЕЖИМ
В нормальном режиме работы с клиентских мест поступают обращения к СУБД, нужные данные загружаются в буфер данных, при выполнении операций с данными действия фиксируются с помощью буфера журнала. Эти действия могут регистрироваться различными способами. Самый простой – записываются все операции. При этом возможно отменять действия. Другой способ – расставляют метки об удалении, тогда при необходимости можно будет восстановить эти записи. При подтверждении изменений делается новая копия, затем удаляются записи, помеченные для удаления.
По ходу работы информация из буферов переносится на диск. Основные ситуации:
1) Буфер данных переписывается на диск при заполнении буфера.
2) Буфер журнала перезаписывается:
- по переполнению буфера.
- по завершению транзакций.
- перед перезаписью данных из буфера данных. Обеспечивается протоколом WAL (Write-Ahead Logging). Данное упреждающее журнализирование является ключевым методом обеспечения требований физической целостности данных. WAL позволяет обеспечить сброс на диск записей из журнала транзакций, относящихся к изменениям данных, раньше того, как будут сброшены на диск сами эти изменённые страницы данных. Известно, что если в СУБД корректно соблюдается протокол WAL, то с помощью журнала можно решить все проблемы восстановления БД после любого сбоя/
Для последующего восстановления используются архивы данных и журнала. Архивация данных может быть по заданным событиям или по явной команде пользователя. При этом копируется вся база или её часть.
В итоге: есть база данных, с которой работаем. Чтобы её не потерять, делается её копия, функция полного копирования обычно есть во всех СУБД. Но эта операция требует монопольного режима работы. Создаваемая копия может быть в другом формате, отличном от формата исходной базы данных. Резервная копия обычно не копирует записи, помеченные на удаление. Копирование может вестись по какому-то событию. Резервное копирование может также позволить перейти в более высокую версию СУБД.
Архивация в архив журнала обычно выполняется для сокращения оперативной части журнала. Архивация выполняется в рабочем режиме. Для этого журнал делится на два блока – один для записи данных из буфера журнала, второй для архивации. После выполнения архивации выполняется смена частей местами. В некоторых системах есть больше частей, это позволяет сгладить пиковые режимы (когда данные не успевают архивироватся). При отсутствии архива журнала реализуется освобождение журнала через архивацию данных, тогда журнал стирается при архивации данных.

СБОЙНЫЕ СИТУАЦИИ
Возможны следующие ситуации, при которых требуется производить восстановление состояния базы данных:
Индивидуальный откат транзакции. Тривиальной ситуацией отката транзакции является ее явное завершение оператором ROLLBACK. Возможны также ситуации, когда откат транзакции инициируется системой (возникновение исключительных ситуаций в прикладной программе, например, деление на ноль). Для восстановления согласованного состояния базы данных при индивидуальном откате транзакции нужно устранить последствия операторов модификации базы данных, которые выполнялись в этой транзакции.
Восстановление после внезапной потери содержимого оперативной памяти (мягкий сбой). Такая ситуация может возникнуть при аварийном выключении электрического питания, при возникновении неустранимого сбоя процессора (например, срабатывании контроля оперативной памяти) и т.д. Ситуация характеризуется потерей той части базы данных, которая к моменту сбоя содержалась в буферах оперативной памяти.
Восстановление после поломки основного внешнего носителя базы данных (жесткий сбой). Эта ситуация при достаточно высокой надежности современных устройств внешней памяти может возникать сравнительно редко, но тем не менее, СУБД должна быть в состоянии восстановить базу данных даже и в этом случае. Основой восстановления является архивная копия и журнал изменений базы данных.

Соответственно трём вариантам сбойных ситуаций существуют три основных вида восстановления:
Восстановление одиночной транзакции.
Для отката транзакции используется буфер журнала и журнал. Для восстановления выполненные операции просматриваются в обратном порядке и выполняются инверсные действия. Например, вместо операции INSERT выполняется соответствующая операция DELETE, вместо DELETE - INSERT, вместо UPDATE - обратная операция UPDATE, восстанавливающая предыдущее состояние объекта базы данных. Любая из этих обратных операций также журнализируется.

13 EMBED Visio.Drawing.11 1415

2) Восстановление после мягкого сбоя (теряются данные в ОЗУ).
Для восстановления используется журнал. Будем считать, что в журнале отмечаются точки физической согласованности базы данных - моменты времени, в которые во внешней памяти содержатся согласованные результаты операций, завершившихся до соответствующего момента времени, и отсутствуют результаты операций, которые не завершились, а буфер журнала вытолкнут во внешнюю память. Тогда к моменту мягкого сбоя возможны следующие состояния транзакций:
13 INCLUDEPICTURE \d "http://citforum.ru/pictures/it/osbd/img00023.gif" \* MERGEFORMATINET 1415
Предположим, что некоторым способом удалось восстановить внешнюю память базы данных к состоянию на момент времени tlpc. Тогда:
Для транзакции T1 никаких действий производить не требуется. Она закончилась до момента tlpc, и все ее результаты отражены во внешней памяти базы данных.
Для транзакции T2 нужно повторно выполнить оставшуюся часть операций, поскольку во внешней памяти полностью отсутствуют следы операций, которые выполнялись после момента tlpc, но в журнале содержатся записи обо всех изменениях, произведенных этой транзакцией до момента мягкого сбоя.
Для транзакции T3 нужно выполнить в обратном направлении первую часть операций, поскольку во внешней памяти базы данных полностью отсутствуют результаты операций, которые были выполнены после момента tlpc, но гарантированно присутствуют результаты операций T3, которые были выполнены до этого момента. Следовательно, обратная интерпретация операций T3 приведет к согласованному состоянию базы данных (поскольку транзакция T3 не завершилась к моменту мягкого сбоя, при восстановлении необходимо устранить все последствия ее выполнения).
Для транзакции T4, которая успела начаться после момента tlpc и закончиться до момента мягкого сбоя, нужно выполнить полную повторную прямую интерпретацию операций.
Наконец, для начавшейся после момента tlpc и не успевшей завершиться к моменту мягкого сбоя транзакции T5 никаких действий предпринимать не требуется. Результаты операций этой транзакции полностью отсутствуют во внешней памяти базы данных.

Рассмотренные варианты можно графически представить следующим образом:
13 EMBED Visio.Drawing.11 1415

3) Восстановление после жесткого сбоя (теряется база данных на диске).
Основой восстановления в этом случае являются журнал и архивная копия базы данных.
Восстановление начинается с обратного копирования базы данных из архивной копии. Затем для всех закончившихся транзакций операции повторно выполняются в прямом смысле, в соответствии с архивом журнала. Если есть журнал, то выполняются операции по журналу. Для транзакций, которые не закончились к моменту сбоя, выполняется откат.
13 EMBED Visio.Drawing.11 1415
Для успешного восстановления данных необходимо хранение блоков на разных носителях, причем журналы желательно хранить на съемных дисках.

Данная схема восстановления реализуется в разном объеме, в зависимости от функциональности СУБД:
1) восстановление невозможно, если СУБД этого не поддерживает (отсутствуют архивы данных, буфер журнала, журнал и архив журнала):
13 EMBED Visio.Drawing.11 1415

2) система поддерживает создание резервных копий:
13 EMBED Visio.Drawing.11 1415
Простая система, вести журналов не нужно. Но создание архивных копий требует много времени.

3) практически полная система восстановления:
13 EMBED Visio.Drawing.11 1415

4) полная реализация:
13 EMBED Visio.Drawing.11 1415

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


ДОПОЛНИТЕЛЬНЫЕ СРЕДСТВА ВОССТАНОВЛЕНИЯ:
1) Зеркалирование – параллельно пишется зеркальная копия базы. Основная база – на основном диске, но то же самое одновременно пишется на второй, дополнительный диск. Достоинство – быстрое восстановление, недостаток – невозможность выполнения откатов.
2) Аппаратное резервирование, например, с использованием RAID-массивов. Это массив из нескольких дисков (запоминающих устройств), управляемых контроллером, связанных между собой скоростными каналами передачи данных и воспринимаемых внешней системой как единое целое. В зависимости от типа используемого массива может обеспечивать различные степени отказоустойчивости и быстродействия. Служит для повышения надёжности хранения данных и/или для повышения скорости чтения/записи.
14. Организация многопользовательского доступа
В многопользовательской среде с одними и теми же записями могут одновременно работать несколько человек. Поскольку в то время, когда один пользователь пытается редактировать записи, другие пользователи также могут вносить в них изменения или даже удалять данные, при работе иногда возникают противоречия и потеря целостности.
13 EMBED Visio.Drawing.6 1415
Возможными путями устранения противоречий являются:
1. Организация параллельного доступа.
2. Разделение прав доступа. Разные пользователю обладают различными правами (только чтение, чтение/запись, возможность доступа к разным уровням данным).
Ниже будет рассмотрена возможность организация параллельного доступа к БД.
При соединении потоков транзакций от разных пользователей могут возникнуть следующие проблемы, приводящие к искажению данных:

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

Т1
Т2
Состояние

ЧтА

А0


ЧтА
А0

ИзмА

А1


ИзмА
А2


[откат]
[А0]

ЧтА

А2 [А0]


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

2) «грязное чтение»  чтение данных, добавленных или изменённых транзакцией, которая впоследствии не подтвердится (откатится). Либо – чтение второй транзакцией данных, которые могут быть лишь промежуточными (неокончательными).
Пример: обрабатываются A и B – связанные данные (они могут быть получены в результате некоторого вычислительного алгоритма)

Т1
Т2
Состояние

ЧтА

А0 B0

ЧтВ

B0 A0

ИзмА

А1 B0 – грязные данные


ЧтА
A1 B0


ЧтВ
A1 B0

ИзмВ

A1 B1


В результате вторая транзакция прочитала неверные (несвязанные) данные.
Также возможен такой вариант: в транзакции 1 изменяется значение поля f2, а затем в транзакции 2 выбирается значение этого же поля. После этого происходит откат транзакции 1. В результате значение поля f2, полученное второй транзакцией, будет отличаться от значения, хранимого в базе данных.
Решение – запрет чтения данных, изменяемых другой транзакцией, до завершения последней.

3) неповторяющееся чтение  ситуация, когда при повторном чтении в рамках одной транзакции, ранее прочитанные данные оказываются изменёнными

Т1
Т2
Состояние

ЧтА

A0


ЧтА
A0


ИзмА
A1

ЧтА

A1


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

4) фантомное чтение  Одна транзакция в ходе своего выполнения несколько раз выбирает множество строк по одним и тем же критериям. Другая транзакция в интервалах между этими выборками добавляет или удаляет строки и успешно заканчивается. В результате получится, что одни и те же выборки в первой транзакции дают разные множества строк. Такая ситуация называется фантомным чтением. От неповторяющегося чтения оно отличается тем, что результат повторного обращения к данным изменился не из-за изменения самих этих данных, а из-за появления новых (фантомных) данных или из-за удаления строк данных.
Исходные данные – набор данных {A}

Т1
Т2

Чт {А}



Доб. в {A}

Чт {А}



Решение: запрещать добавление записей до завершения другой транзакции.

Управление транзакциями. Основные стратегии.
Для управления взаимодействием транзакций используются уровни изолированности. Изолированность – состояние работы, при котором пользователь не ощущает присутствия других лиц. Уровень изолированности определяет уровень, при котором в транзакции допускаются несогласованные данные, то есть степень изолированности одной транзакции от другой. Более высокий уровень изолированности повышает точность данных, но при этом может снижаться количество параллельно выполняемых транзакций. С другой стороны, более низкий уровень изолированности позволяет выполнять больше параллельных транзакций, но снижает точность данных.
Стандарт SQL-92 определяет следующие четыре уровня изоляции, установка которых предотвращает определенные конфликтные ситуации («+» – предотвращает, «–» – не предотвращает):

Уровень
Запрет читать измененные данные
Запрет изменять прочитанные данные
Запрет добавления
Примечание

read uncommitted (чтение незафиксированных данных)



Низший уровень изоляции. Гарантирует только отсутствие потерянных обновлений.

read committed
(чтение фиксированных данных)
+


Принятый по умолчанию уровень для Microsoft SQL Server. Отсутствует черновое, «грязное» чтение. Тем не менее в процессе работы одной транзакции другая может быть успешно завершена и сделанные ею изменения зафиксированы (не решена проблема неповторяемого чтения)

repeatable read
(повторяемость чтения)
+
+

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

Serializable (упорядочиваемость)
+
+
+
Самый высокий уровень изолированности; транзакции полностью изолируются друг от друга


Под сериализацией параллельно выполняющихся транзакций понимается такой порядок планирования их работы, при котором суммарный эффект смеси транзакций эквивалентен эффекту их некоторого последовательного выполнения.
Сериальный план выполнения смеси транзакций – это такой план, который приводит к сериализации транзакций. Если удается добиться действительно сериального выполнения смеси транзакций, то для каждого пользователя, по инициативе которого образована транзакция, присутствие других транзакций будет незаметно (если не считать некоторого замедления работы по сравнению с однопользовательским режимом).
Существует несколько базовых алгоритмов сериализации транзакций.
1) Последовательное исполнение: выполняется только одна транзакция, остальные ждут ее завершения. Приводит к большим задержкам времени ожидания. Для ускорения следует разрешить любую работу с различными данными и одновременное чтение одних и тех же данных;
2) Использование синхронизационных блокировок: транзакция при обращении к данным накладывает блокировку (захват). Обычно используется два типа блокировок: на чтение и на запись. Если транзакции требуются данные и они свободны, то выполняется работа с данными; если они заблокированы, проверяется возможность совместимости: при совместимости работаем с данными, при несовместимости – ожидаем их освобождения. Блокировки снимаются при завершении транзакции. Для поддержки захватов используется двухфазный протокол синхронизации (двухфазное блокирование).
- 1 фаза – транзакция захватывает данные по мере обращения к ним:
13 EMBED Visio.Drawing.6 1415

- 2 фаза – одновременное освобождение всех данных по завершению транзакции.
Основной недостаток: возможность взаимоблокировок (тупиков):
13 EMBED Visio.Drawing.6 1415

При наличии тупика (deadlock) ожидание будет бесконечным, поэтому необходимо нестандартное разрешение. Конфликты блокировок решаются следующими методами:
полуавтоматический вариант: при обнаружении конфликта посылается запрос пользователю. Пользователь принимает решение – продолжить ожидание или произвести откат транзакции;
автоматический вариант: при обнаружении конфликта после заданного времени ожидания выполняется автооткат транзакции, первой обнаружившей тупик;
анализ наличия тупика: автоматически определяется разрешимость конфликта, при этом используется граф ожидания, в котором указаны транзакции и обрабатываемые объекты. Если обнаруживается тупик, откатывается одна из транзакций.
Граф ожидания – инструмент, используемый при разработке СУБД и многопоточных систем и используемый, в частности, для определения ситуации взаимной блокировки. Представляет собой ориентированный двудольный граф, содержащий вершины двух типов:
вершины типа T, соответствующие транзакциям или выполняющимся потокам. Они образуют первую долю графа;
вершины типа R, соответствующие ресурсам и объектам, которые могут быть захвачены транзакциями. Они образуют вторую долю графа.
Дуги графа ожидания также имеют двоякий смысл:
дуги (T, R), идущие из вершины-транзакции T в вершину-ресурс R, обозначают, что данный ресурс уже захвачен транзакцией
дуги (R, T), идущие из вершины-ресурса R в вершину-транзакцию T обозначают, что транзакция T ожидает, пока ресурс R будет освобождён.
Простейшие свойства:
Ресурс, не имеющий ни одной входящей дуги, является свободным.
Если вершина-транзакция имеет некоторое ненулевое количество входящих дуг, то соответствующая транзакция находится в состоянии ожидания.
Если между двумя транзакциями T1 ( T2 существует путь, то транзакция T1 должна быть выполнена (завершена) раньше, чем начнётся выполнение T2, поскольку последняя требует освобождения некоторых ресурсов, захваченных транзакцией T1.
Из последнего свойства очевидным образом следует, что ситуации взаимной блокировки соответствует цикл на графе ожидания.
Для обнаружения цикла используется редукция графа. При этом поочередно выполняются два шага:
удаление дуг от неожидающих транзакций;
удаление дуг от свободных данных к транзакциям.
Если не удается удалить некоторый набор дуг, то это - цикл. Для разрешения тупика откатывается одна из транзакций.
3) Временные метки – транзакция при инициализации получает метку – это время начала. При обращении к данным, транзакция помечает его своей меткой. При обнаружении конфликта, метки сравниваются. Более молодая транзакция откатывается

При высоком уровне изолированности возникают большие затраты на ожидание. Для повышения быстродействия могут использоваться дополнительные возможности управления многопользовательским доступом:
многоуровневое блокирование: для записи, ячейки, массива записей, или всей таблицы (обычно при мелкой блокировке – много меток, при высокой – сразу блокируется большой кусок);
многоверсионная организация. Применена в InterBase.. Сущность её состоит в том, что все изменения, проводимые над конкретными записями, производятся не над самой записью, а над ее версией. Версия записи - это копия записи, которая создается при попытке ее изменить. Если какой-то транзакции нужно работать с какой-либо записью, транзакция обращается к последней зафиксированной версии записи;
использование оптимистического буферирования. При этом данные храниться в буфере до тех пор, пока принудительно не выполняется запись в базу. Различают пессимистическое (запись в БД при записи в буфер) и оптимистическое буферирование (запись выполняется после завершения транзакции, но потом проверяется - были ли изменения в данных. Если изменения были, то пользователь получает сообщение об этом.
15. Защита от несанкционированного доступа
Безопасность данных (data security) концепция защиты [ Cкачайте файл, чтобы посмотреть ссылку ] и [ Cкачайте файл, чтобы посмотреть ссылку ] от случайного либо умышленного изменения, уничтожения, разглашения, а также несанкционированного использования.
Безопасность базы данных заключается в защите базы данных от несанкционированного доступа со стороны пользователей. Без привлечения соответствующих мер безопасности интегрированные в БД данные становятся более уязвимыми, чем данные в файловой системе. Однако интеграция позволяет определить требуемую систему безопасности базы данных, а СУБД привести ее в действие.
Защита данных от несанкционированного доступа предполагает:
предотвращение несанкционированного доступа к базе данных (обеспечение парольного входа в систему: регистрация пользователей, назначение и изменение паролей);
обеспечение защиты конкретных данных: определение прав доступа групп пользователей и отдельных пользователей, определение допустимых операций над данными для отдельных пользователей, выбор/создание программно-технологических средств защиты данных, шифрование информации в целях защиты данных от несанкционированного использования;
фиксация попыток несанкционированного доступа к информации;
аудит действий пользователей в базе данных;
исследование возникающих случаев нарушения защиты данных и проведение мероприятий по их предотвращению.

Безопасность базы данных можно разделить на две части:
1) Безопасность системы, которая охватывает доступ к базе данных на системном уровне. Безопасность системы включает в себя:
проверка правильности комбинации имени и пароля пользователя;
контроль системных операций, которые пользователю разрешено выполнять.
2) Безопасность данных включает механизмы, которые управляют доступом к объектам базы данных. Безопасность данных определяет:
к каким объектам базы данных имеет доступ пользователь;
какие действия пользователь может выполнять с объектами базы данных (извлечение, вставка, обновление, удаление).

Защита может выполняться на разных уровнях:
13 EMBED Visio.Drawing.6 1415

1. Защита от непосредственного доступа к базе данных. Применяются следующие методы:
1) Использование закрытого (сложного для чтения, уникального) формата данных.
2) Шифрование данных. Могут шифроваться как файлы целиком, так и отдельные поля.
Методика введения полного шифрования – шифрование в конце, расшифровка в начале программы.
Важнейшими характеристиками алгоритмов шифрования являются криптостойкость, длина ключа и скорость шифрования.
В криптографии обычно рассматриваются два типа криптографических алгоритмов. Это классические криптографические алгоритмы, основанные на использовании секретных ключей, и новые криптографические алгоритмы с открытым ключом, основанные на использовании ключей двух типов: секретного (закрытого) и открытого, так называемые двухключевые алгоритмы.
3) Самый популярный метод защиты – перенос базы на защищенный носитель (защищённый сервер).

2. Защита на уровне СУБД
Сервер баз данных управляет секретностью базы данных, используя различные средства:
управление пользователями базы данных;
управление привилегиями и ролями;
аудит базы данных;
шифрование хранимых программных единиц.
Распознавание пользователя предполагает:
идентификацию пользователя – пользователь указывает свой идентификатор (не секретный – логин);
аутентификацию – проверка соответствия реального пользователя указанному идентификатору (подтверждение подлинности пользователя). К настоящему времени разработано множество методов аутентификации, включая различные схемы паролей, использование признаков и ключей, а также физических характеристик (например, отпечатки пальцев и образцы голоса).
После распознавания пользователя система производит следующие действия:
выделяет соответствующие пользователю ресурсы (трафик, расписание доступа, выделение памяти и т.д.);
устанавливает права доступа пользователя.
выполняет мониторинг (оперативное наблюдение) и аудит (подведение итогов, определение статистики) за пользователем;
Основное средство защиты – контроль доступа – использует два основных подхода:
обязательный;
избирательный.
Избирательный подход – дает меньшую степень защиты, но более просто реализуется. Дл этого пользователям назначаются привилегии.
Привилегия – право на выполнение некоторой операции. Разделяются на системные и объектные привилегии.
Системные (командные) привилегии – разрешают пользователю выполнять конкретную операцию с базой данных. Используются для выполнения административных задач (создание или удаление таблиц, представлений, хранимых процедур, ввод учетных записей пользователей и т.д.). Эта группа привилегий никак не стандартизирована и реализуется в разных системах с разным набором привилегий.
Объектные привилегии – разрешают выполнять действия над заданным объектом базы данных (таблицей, представлением и т.д.). Стандартизированы в SQL системах.
Основные объектные привилегии для внешних пользователей:
ALTER – разрешает изменение определения заданных таблиц, представлений
DELETE – разрешает удаление строк из заданных таблиц, представлений
EXECUTE – разрешает выполнение заданных хранимых процедур, функций, пакетов
INSERT – разрешает вставка строк в заданные таблицы, представления
SELECT – разрешает чтение данных из заданных таблиц, представлений
UPDATE – разрешает изменение данных в заданных таблицах, представлениях
При назначении привилегий различают субъект – (то, что выполняет действие – может быть пользователь или программа) и объект (то, над чем выполняется действие – может быть информационный объект или программа).
Для задания привилегий заполняется матрица доступа:

13 EMBED Visio.Drawing.11 1415

Привелегии (права) задаются с помощью команды:
GRANT <привилегия[, привилегия ] | ALL> ON <Объект> TO <Субъект>
("ALL" предоставляет все привилегии на объект)
Например, чтобы позволить пользователю Ivanov выполнять запросы к таблице Sotrudnik, нужно ввести команду
GRANT SELECT ON Sotrudnik TO Ivanov;
Привилегии, объекты и субъекты можно задавать списком.
Привилегии может назначать администратор, владелец объекта или уполномоченное (доверенное) лицо – тот, кому поручили перераспределение привилегий.
Доверенное лицо получает разрешение на выдачу привилегий добавлением GRANT опции:
GRANT <привилегия> ON <Объект> TO <Субъект> WITH GRANT OPTION
При этом конструкция "WITH ADMIN OPTION" разрешает предоставлять полученную привилегию другим пользователям
Напрмер, команда
“GRANT SELECT ON Sotrudnik TO Ivanov WITH GRANT OPTION”
предоставляет возможность пользователю Ivanov передавать право назначать привилегии работы с таблицей Sotrudnik другим пользователям.

Для отмены привилегии используется оператор
“REVOKE <привилегия> ON <объект> FROM <субъект>”.
Привилегию может снять только субъект, ее назначивший; снятие привилегии выполняется каскадно.
Одна из первых привилегий, которая должна быть определена - это привилегия создателей таблиц. Если все пользователи будут иметь возможность создавать в системе базовые таблицы, это может привести к избыточности данных, их несогласованности и, как следствие, к неэффективности системы. Пользователь, создавший таблицу, является ее владельцем. Это означает, что пользователь имеет все привилегии в созданной им таблице и может передавать привилегии другим пользователям в этой таблице.
Каждый пользователь в среде SQL имеет специальное идентификационное имя (или номер).
Для пользователя таблицы могут быть назначены следующие типы привилегий:
SELECT - разрешение выполнять запросы в таблице.
INSERT - разрешение выполнять оператор INSERT (вставка новой строки) в таблице.
UPDATE - разрешение выполнять оператор UPDATE (обновление значений полей) в таблице. Можно ограничить эту привилегию для определенных столбцов таблицы.
DELETE - разрешение выполнять оператор DELETE (удаление записей) в таблице.
REFERENCES - разрешение определить внешний ключ.

Недостатки избирательного подхода:
сложность назначения привилегий;
ошибки нарушения конфиденциальности из-за путаницы.

Для упрощения и большей наглядности назначений может быть реализовано группирование. Существуют две формы: пользователи объединяются в группы, привилегии в роли.
В первых системах создавались группы пользователей. При этом объявляются группы, пользователи причисляются к группам. Привилегии назначаются как отдельным пользователям, так и отдельным группам. Обычно существуют предопределенные группы (например, PUBLIC – в нее автоматически зачисляются все пользователи; этой группе определяют минимальные права).
Второй вариант, который в настоящее время чаще используется – управление привилегиями через роли. Роль – именованная группа привилегий, которая может быть предоставлена пользователю. Использование ролей позволяет группировать привилегии, необходимые для разных категорий пользователей и динамически управлять привилегиями (например, достаточно переопределить привилегии, назначенные роли, что немедленно отобразится на всех пользователях, которым назначена эта роль). Администратор базы данных создает роль, определяет набор привилегий для роли и присваивает роль пользователям:
Разница данных вариантов группирования в том, что назначение в группы является статическим. Создание ролей позволяет сделать динамически управление.

13 EMBED Visio.Drawing.11 1415

Обязательный подход
Реализует жесткое разделение информации по уровням. При этом используются метки секретности. Для объектов задаются классы секретности, для субъектов – уровни секретности. Классы и уровни относятся к одному набору, например: несекретно, для служебного пользования, секретно, совершенно секретно.
При попытке доступа уровень субъекта сравнивается с классом объекта. Учитываются ограничения:
пользователь может читать данные объектов своего уровня и нижних;
пользователь может записывать данные в объекты своего уровня и более высокого.
Такая модель называется моделью Белла-Лападула.
В простой реализации модели метки назначаются записям.
Более полный вариант – задание меток для отдельных полей, так как отдельные ячейки таблицы могут быть засекречены.
В получаемых моделях секретные и несекретные данные хранятся в общих таблицах. При выводе засекреченные данные не предъявляются, если уровень секретности субъекта это не поддерживает. При этом возможна косвенная утечка информации, в зависимости от способа маскирования данных. Используются следующие варианты маскирования:
прямое маскирование полей – информация секретных полей не выводится; ввод в засекреченные поля блокируется. Но в этом случае можно догадаться, что в скрытом поле что-то спрятано;
использование легенды для секретных данных. Для каждой ячейки хранится основной вариант и легенда. С легендой можно делать все что угодно. Например, данные "Иванов" и "бухгалтер" являются легендами соответствующих данных.
ФИО г.р. должность
С Иванов Н 1940 С бухгалтер
Д. Бонд агент 007
Но в этом случае все равно остается косвенный канал утечки информации, т.к. пользователь может модифицировать данные, но удаление запрещенных данных блокируется.
использование многозначных картежей. Допускается умышленное нарушение реляционных принципов: каждый пользователь работает со своей копией. Данный вариант является наиболее надежным.

3. Защита на уровне приложения
На этом уровне могут реализовываться аналогичные механизмы, при отсутствии их в СУБД. Кроме того, на уровне приложения можно реализовать дополнительные возможности:
очистка буферов;
очистка swapping-файлов (один из механизмов виртуальной памяти, при котором отдельные фрагменты памяти, обычно неактивные, перемещаются из ОЗУ на внешний накопитель, освобождая ОЗУ для загрузки других активных фрагментов памяти);
очистка временного хранения;
контроль выдачи выходных документов;
протокол обращения к данным;
вывод на съемные носители;
контроль целостности системы защиты.
Достоинства:
1) возможности реализации нестандартных алгоритмов защиты.
2) большее быстродействие.
3) можно реализовать доступ не к объектам, а к пользовательским операциям.
Недостатки:
1) возможность обхода приложения.
2) легче взлом защиты.

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

13 INCLUDEPICTURE \d "http://files.vunivere.ru/00/00/61/71/images/image002.png" \* MERGEFORMATINET 1415

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



16. Физическая организация данных в БД
Чтобы правильно использовать вычислительную машину, необходимо хорошо представлять себе структурные отношения между данными, знать способы представления таких структур в памяти машины и методы работы с ними. Структура данных и представление этой структуры в памяти ЭВМ – два важных, но различных между собой понятия. Например, некоторая логическая структура данных типа «дерево» может быть представлена в памяти ЭВМ несколькими различными способами.
База данных представляет собой множество информационных объектов. Существует два основных способа их хранения:
1) Раздельное хранение. Характерно для простых персональных систем. При этом каждый объект БД (таблица, индекс, представление и т.д.) хранится в отдельном файле. Размещение файлов на носителе, управление размерностью файлов осуществляется средствами файловой системы. Пример подобной реализации – VisualFoxPro.

13 EMBED Visio.Drawing.11 1415
Достоинства:
– простота форматов – в каждом файле размещается информация одного типа. Упрощается анализ информации;
– упрощение СУБД за счет передачи размещения файловой системе.
Недостатки:
– проблемы хранения общих служебных данных;
– высока вероятность потери целостности базы;
– малая связность объектов БД, что затрудняет контроль данных и управление ими.
2) Совместное хранение. Характерно для серверных СУБД. При создании базы данных сразу же отводится определенный размер на диске. Файл базы один. Распределение таблиц внутри файла производится специальными средствами самой СУБД, при этом память для таблиц выделяется с запасом.
13 EMBED Visio.Drawing.11 1415
При создании нового объекта ему отводится некоторая область памяти, которая по мере появления информации постепенно заполняется. При исчерпании отведенного под объект места СУБД выделяет объекту дополнительный участок памяти в свободном пространстве файла.
При использовании всего свободного пространства файла СУБД создает дополнительный файл, пространство которого является логическим продолжением пространства основного файла. Кроме информационных объектов в пространстве файла БД размещаются вспомогательные и служебные объекты, содержащие дополнительную и метаинформацию, области для оперативной обработки данных и т.д.
Файловая система разбивает общий файл базы по кластерам. Значительную часть распределения памяти берет на себя СУБД. Для работы с памятью СУБД использует, как правило, страничную организацию, при которой вся область распределяемой памяти делится на дискретные единицы (страницы) и все распределение памяти осуществляется в данных единицах. Самостоятельное управление распределением памяти обеспечивает для СУБД полную управляемость данными, но «утяжеляет» СУБД. Какая-то часть страниц выделяется под служебную информацию, под каждый объект выделяется группа страниц. В одной странице может помещаться одна запись, несколько записей или часть записи. Считается что эффективнее всего организуется размещение, если в странице находится 5-10 данных. Если в странице слишком мало данных, выполняется частое обращение к файловой системе. Если задавать слишком большую страницу, то тогда при копировании будет записываться много лишних записей.
В большинстве систем есть возможность задания размера страниц, но какой размер задавать – обычно заранее непонятно, поэтому при создании базы данных данный параметр выбирается случайно. В процессе работы с БД имеется возможность переопределять размер страницы.
Для управления размещением СУБД может поддерживать настройку параметров. Чаще всего поддерживается размер файла базы, размер файла расширения, размер страницы.
Пример: InterBase в команде CREATE DATABASE.

Внутри отведенного объекта (файла, области, страницы) данные размещаются согласно принятой организации: последовательной, списковой, индексной или их комбинации. Рассмотрим четыре основных принципа типовых организаций данных и операций с ними на примере размещения данных для основного информационного объекта – таблицы БД. В этом случае в отведенном участке памяти нужно разместить набор однотипных записей таблицы и выполнять для него операции выборки записи, добавления записи, удаления записи, модификации записи.
1. Последовательная организация.
Если отведенная память для СУБД – это логически связанная последовательность, то для файловой системы – это последовательность кластеров.
Последовательное распределение – простой и естественный способ хранения линейного списка. В этом случае узлы списка размещаются в последовательных элементах памяти.
Нужно иметь доступ к любой записи и обеспечить эффективность следующих операций с ними:
– чтение записи;
– модификация записи;
– удаление записи.
Длина записи может быть фиксированной или переменной.
а) Записи фиксированной длины
Записи размещаются последовательно непосредственно друг за другом. Вектор данных логически отделен от описания структуры хранимых данных. Например, если структура данных представляет собой линейный список (файл записей фиксированной длины), то описание структуры хранится в отдельной записи и содержит:
а) N – размер вектора данных, т.е. количество элементов списка записей;
б) т – размер элемента списка, т.е. размер записи, например, в байтах;
в)
· – адрес базы, указывающий на начало вектора данных в памяти.



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


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

1) Хранение адреса следующей записи

2) Хранение длины следующей записи

3) Выравнивание записей.

Добавление записи при последовательной организации трудоемко из-за необходимости перемещения всех записей, следующих за добавляемой, для освобождения места под новую запись. Поэтому прямая вставка не эффективна, рекомендуется добавление в конец.
При страничной организации для улучшения характеристик применяют неполное заполнение страниц, что позволяет локализовать перемещение записей одной страницей.
Аналогичные трудности возникают при операции удаления, когда записи перемещаются для заполнения освободившегося места. Здесь для повышения быстродействия и для избавления от массовой перезаписи файла часто используется пометка записей на удаление без немедленного сжатия данных. При этом разделяют физическое и логическое удаление (например, в Visual Fox Pro: PACK – физическое удаление, DELETE – логическое удаление. Физическое удаление предполагает монопольный режим и выполняется медленно, поэтому вызывается редко).
Модификация записи при равной длине выполняется просто, но при неравной длине записей снова могут возникать проблемы, связанные с необходимостью перезаписи больших объемов данных. При записях одинаковой длины, просто добавляется в пустое место или в конец, иначе при записях неодинаковой длины – запись в конец.
Для повышения эффективности доступа применяют также выравнивание записей. Для этого существует два метода:
1) Выполняется поиск записи максимальной длины, выполняется расширение до этого размера (плюс некоторый запас) всех строк. Используется: когда разброс длин невелик и длина небольшая. (VARCHAR – строка переменной длины).
2) Невыравненные части записей выносятся в отдельное хранение. Используется при большом разбросе длин записей (Например, в VisualFoxPro используется описание "memo", в InterBase – "blob", указатель занимает 4 байта).

2. Списковое хранение
Связанное представление линейного списка называется связанным списком. При связанном распределении памяти для построения структуры необходимо задать отношения следования и предшествования элементов с помощью указателей. Указателями служат адреса, хранимые в записях данных. В отличие от последовательного распределения памяти, при котором с помощью адресной функции вычисляется адрес следующего элемента, при связанном распределении памяти значение адресной функции можно получить только путем просмотра хранящихся указателей. Такой метод распределения памяти позволяет расширить либо сократить структуру без перемещения самих данных в памяти ЭВМ, однако при этом требуется больше памяти для хранения структуры по сравнению с последовательным распределением.
Связанное распределение – более сложный, но и более гибкий способ хранения линейного списка. Каждый узел содержит указатель на следующий узел списка, т.е. адрес следующего узла списка. При связанном распределении не требуется, чтобы список хранился в последовательных элементах памяти. Наличие адресов связи в данном способе хранения позволяет размещать узлы списка произвольно в любом свободном участке памяти. При этом линейная структура списка обеспечивается указателями.


Примеры связанных линейных списков:
а) однонаправленный список; б) тот же список после удаления узла 4 и включения узлов 2а и 5

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



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

Однонаправленный циклический список

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

13 EMBED Visio.Drawing.11 1415

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

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



Линейный связанный список с индексом


4. Хэшированная организация
Записи размещаются в отведенной области по вычисляемым адресам. Адрес хранения записи расчитывается по значениям ключа хэширования (поля или набора полей) для данной записи. Выборка записи выполняется из адреса, вычисленного для требуемого значения ключа хэширования. Таким образом, вместо поискового перебора записей выполняется прямое обращение к нужному адресу памяти. Проблемой хэшированной организации являются возможные конфликты наложения записей.

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

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

1. Последовательный поиск:
Записи просматриваются последовательно, начиная с первой. Для каждой записи значение поля поиска сравнивается со значением ключа поиска. Окончание поиска – по соответствию значения поля искомому значению.
В целом, последовательный поиск имеет очень низкое быстродействие и применим только для небольших таблиц. К достоинствам поиска относятся простота выполнения и универсальность, основывающаяся на отсутствии необходимости в поддержке служебных данных, упорядочиваний и т.д.
Для ускорения поиска можно использовать упорядочивание по значению записей. Выигрыш - если при просмотре запись не нашлась, то часть таблицы, которая ниже нужной, не просматривается. Но при этом проигрываем в том, что необходимо поддерживать упорядоченность.
Можно упорядочить по важности информации. И если чаще нужна наиболее важная информация, то чаще всего поиск будет заканчиваться на наиболее важной информации.
Последовательный поиск используется в последовательной и списковой организации. Метод не применяется там, где необходим быстрый доступ к данным большого объема. Но его можно использовать в тех случаях, когда по характеру задачи следует выбирать записи последовательно (например, полное копирование данных), а также при очень небольших объемах данных в силу простоты алгоритма доступа.

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

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

4. Индексный поиск
Наиболее распространенный в БД метод поиска. В основе индексных методов доступа лежит создание вспомогательной структуры – индекса, содержащего ключи поиска и ссылки на физические адреса данных. Термин «ключ поиска» не обязательно подразумевает его уникальность, это просто атрибут (комбинация атрибутов), который должен удовлетворять критерию поиска. Индекс хранит описание логической последовательности записей по заданному ключу. Он представляет собой структуру, при обращении к которой входными данными является искомое значение ключа, а выходным – указатель на запись, содержащую это значение (или указание на отсутствие подходящей записи).
Требуемая упорядоченность по ключу поиска поддерживается индексом, в котором и проводится поиск. Доступ к данным производится в два этапа. Вначале в индексе (индексном файле) находятся требуемые значения ключей, затем из основного файла по ссылке извлекается требуемая информация. Производительность системы в целом может стать достаточно высокой. Для ее увеличения обычно требуют, чтобы индекс целиком размещался в оперативной памяти.
Факторами ускорения поиска являются:
- меньшее число проверок при выполнении поиска за счет упорядоченности данных в индексе;
- быстрая выборка проверяемой позиции индекса за счет небольшого объема индекса и выравненности размеров позиций;
- отсутствие необходимости расчета проверяемого значения для записей, т.к. в индексе хранятся уже рассчитанные значения.
Индексы могут быть устроены по-разному. Различаются первичные и вторичные индексы в зависимости от вида ключа поиска. Если поиск и выборка производится по комбинации атрибутов (индексному выражению), соответствующий индекс называется составным. Индекс, построенный на иерархии ссылок, называется многоуровневым. Индекс, который содержит ссылки не на все записи, а на некоторый диапазон, называется неплотным. Плотный индекс содержит ссылки на все записи. Элемент индекса часто называют статьей.
Существует множество индексных методов доступа. Внутренняя организация индекса может основываться на последовательной или списковой организации данных. Простейшей и сравнительно малоэффективной является последовательная организация. В этом случае в индексе хранятся упорядоченные по значению ключа пары «значение ключа – указатель на запись».

13 EMBED Visio.Drawing.11 1415

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

13 EMBED Visio.Drawing.11 1415
Бинарное дерево характеризуется большой глубиной и несбалансированностью ветвей, что снижает эффективность поиска.
Например, заполнение дерева следующими значениями записей: 12, 35, 40, 100, 1, 2, 83, 5, 10, получим дерево, имеющее некоторые очень большие ветви, в то время как другие могут отсутствовать.
13 EMBED Visio.Drawing.11 1415

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

а) Неплотный индекс
Пусть основной файл F упорядочен по полю ключа К. Построим дополнительный файл FD по следующему правилу:
1) записи файла FD имеют формат FD(K, Р), где К – поле, принимающее значение ключа первой записи блока основного файла F; Р – указатель на этот блок;
2) записи файла FD упорядочены по полю К.



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

В-дерево. Так как неплотный индекс упорядочен по ключевому полю, то над ним можно построить еще один неплотный индекс (неплотный индекс неплотного индекса) и т.д., пока на самом последнем, верхнем уровне не останется всего один блок.
Полученная структура называется В-деревом порядка т, где т – количество записей в блоке индекса. Такое дерево должно иметь в каждом узле не менее т/2 зависимых узлов и все листья должны располагаться на одном уровне.


Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа. Поиск в В-дереве выполняется так же, как и в неплотном индексе. Удачный и неудачный поиск записи в В-дереве требует h обменов, где h – число уровней В-дерева.
При поиске по интервалу значений а
· К
· b вначале выполняется поиск по К = а в В-дереве, а затем – последовательный поиск по условию К
· b в блоках 1-го уровня В-дерева.

б) Плотный индекс
Пусть по каким-либо причинам невозможно упорядочить основной файл F по ключу К. Построим дополнительный файл FD по правилу:
1) записи файла FD имеют формат FD(K, Р), где К – поле, принимающее значение ключа записи основного файла F; Р – указатель на эту запись;
2) записи файла FD упорядочены по полю К.

Полученный файл называется плотным индексом. Он строится почти так же, как и неплотный индекс. Различие заключается в том, что для каждого значения ключа К в файле FD имеется отдельная запись, а в неполном индексе - только для значения ключа первой записи блока.
Над плотным индексом можно также построить В-дерево.

5. Хешированный поиск
Этот метод называется еще методом перемешанных таблиц. Он представляет собой расширение метода прямого доступа на случай отсутствия взаимно однозначного соответствия между ключом и адресом записи. Существует адресная функция (хеш-функция), которая по ключу формирует адрес, однако, не исключено, что один и тот же адрес выделится разным ключам.
Быстродействие обеспечивается заменой переборных и поисковых процедур на прямое вычисление местоположения искомой записи по искомому значению ключа. Вычисление содержит три основных шага:
1) преобразование значения ключа в числовое значение (при нечисловом ключе),
2) хэширование, заключающееся в пересчете числового эквивалента ключа в значение рандомизированной переменной с предположительно равномерным законом распределения. Для пересчета используется выбранная хэш-функция, дающая желаемый эффект рандомизации,
3) масштабирование рандомизированной переменной для приведения получаемых значений к выделенному диапазону адресов памяти (определение адресов в памяти).
Проблемой хэшированного поиска является наличие коллизий, выражающееся получением одинаковых значений адреса хранения записи для различающихся значений ключа. Для решения проблемы коллизий приходится принимать дополнительные меры, такие так выделение дополнительных областей памяти для размещения цепочек перекрывающихся записей.
Этот алгоритм прост, но неэффективен по времени при заполнении таблицы более чем наполовину. Кроме того, при неравномерном распределении ключей этот алгоритм приводит к локальным сгущениям записей и увеличению числа коллизий при относительно свободной таблице.










13PAGE 15


13PAGE 146815



П+Д

П

Д

П

Базовое ПО

Д

13 EMBED Visio.Drawing.11 1415

13 EMBED Visio.Drawing.11 1415

13 EMBED Visio.Drawing.11 1415

13 EMBED Visio.Drawing.11 1415









Приложенные файлы

  • doc 8908967
    Размер файла: 5 MB Загрузок: 0

Добавить комментарий