48527

Базы данных. Конспект лекций

Конспект

Информатика, кибернетика и программирование

Базы данных. Лукин Базы данных конспект лекций Хранение данных Системы хранения данных на основе файлов

Русский

2013-12-11

1.95 MB

271 чел.

PAGE  80

В.Н.Лукин. Базы данных. Конспект лекций, ред 3.13, 03.12.05

В.Н.Лукин

Базы данных

(конспект лекций)

[0.1] Хранение данных

[0.1.1] Данные, информация

[0.1.2] Системы хранения данных на основе файлов

[0.1.3] База данных

[0.1.4] Требования к СУБД

[0.1.5] Администратор БД (АБД)

[1]
Лекция 2

[1.1] Модели данных

[1.1.1] Независимость данных

[1.1.2] Модель, схема

[2] Лекция 3

[2.1] Ранние модели

[2.1.1] Иерархическая модель

[2.1.2] Сетевая модель

[3]
Лекция 4

[3.1] Пример базы данных, построенной на сетевой модели

[3.1.1] Постановка задачи

[3.1.2] Диаграмма

[3.1.3] СУБД

[3.1.4] Описание на ЯОД

[4] Лекция 5

[4.1] Реляционная модель

[4.1.1] Принципы

[4.1.2] Модель

[4.1.3] Уточнения

[5]
Лекция 6

[5.1] Методы хранения данных и доступа к ним

[5.1.1] Последовательный метод

[5.1.2] Прямой метод

[5.1.3] Индексные методы

[5.1.4] Индексно-последовательный метод

[5.1.5] Индексно-произвольный метод

[5.1.6] Инвертированные списки

[5.1.7] Хеширование

[6]
Лекция 7

[6.1] Реляционная алгебра: определения, изменение отношений

[6.1.1] Схема, отношение. Ключ

[6.1.2] Изменение отношений во времени.

[7]
Лекция 8

[7.1] Операции реляционной алгебры

[7.1.1] Булевы операции

[7.1.2] Выбор; свойства выбора

[7.1.3] Проекция; свойства проекции

[8]
Лекция 9

[8.1] Операции реляционной алгебры (продолжение)

[8.1.1] Соединение

[8.1.2] Свойства соединения

[9]
Лекция 10

[9.1] Операции реляционной алгебры (продолжение)

[9.1.1] Деление

[9.1.2] Постоянные отношения. Переименование атрибутов

[9.1.3] Эквисоединение, естественное и -соединение

[9.1.4] Реляционная алгебра. Полнота ограниченного множества операторов

[9.1.5] Операторы расщепления и фактора

[10]
Лекция 11

[10.1] Язык структурных запросов SQL

[10.1.1] Начальные понятия

[10.1.2] Стандарт ANSI

[10.1.3] Типы данных

[10.1.4] Интерактивный и встроенный SQL

[10.1.5] Синтаксис

[10.1.6] Подразделы SQL

[10.1.7] Простейшие действия

[10.1.8] Функции агрегирования

[10.1.9] Группировка

[10.1.10] Возможности форматирования

[11]
Лекция 12

[11.1] Язык структурных запросов SQL (продолжение)

[11.1.1] Соединение

[11.1.2] Вложенные запросы

[11.1.3] Связанные запросы

[11.1.4] Предикаты, определенные на подзапросах

[11.1.5] Объединение

[11.1.6] Изменение базы данных

[12]
Лекция 13

[12.1] Понятие о нормальных формах

[12.1.1] 1 нормальная форма (1НФ)

[12.1.2] 2 нормальная форма (2НФ)

[12.1.3] 3 нормальная форма (3НФ)

[12.1.4] Нормальная форма Бойса-Кодда (НФБК)

[12.1.5] 4 нормальная форма (4НФ)

[12.1.6] 5 нормальная форма (5НФ) – проекция/соединение

[13]
Лекция 13

[13.1] Проектирование данных

[13.1.1] Процессы проектирования

[13.1.2] Концептуальное проектирование

[13.1.3] Логическое проектирование

[13.1.4] Средства создания модели

[14]
Лекция 14

[14.1] Функциональные зависимости

[14.1.1] Аксиомы вывода

[14.1.2] B-аксиомы и RAP-последовательности вывода

[14.1.3] Ориентированный ациклический граф вывода

[14.1.4] Определение реляционной базы данных

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

[15]
Лекция 15

[15.1] Покрытия функциональных зависимостей

[15.1.1] Лемма об эквивалентности ФЗ

[15.1.2] Неизбыточные покрытия

[15.1.3] Посторонние атрибуты

[15.1.4] Канонические покрытия

[15.1.5] Структура неизбыточных покрытий

[15.1.6] Оптимальные покрытия

[15.1.7] Кольцевые покрытия и составные ФЗ

[16]
Лекция 16

[16.1] Возвращение к НФ

[16.1.1] 2 нормальная форма

[16.1.2] 3 нормальная форма

[16.1.3] Нормализация через декомпозицию и посредством синтеза

[16.1.4] Нормальная форма Бойса-Кодда

[17]
Литература


Лекция 1

Хранение данных

Данные, информация

Понятие «базы данных» возникло в 60-х годах, наиболее бурное развитие этого направления пришлось на 70-е годы. Тогда же сложился, в основном, и теоретический фундамент этого направления. Состояние вычислительной техники в то время заметно отставало от теоретических разработок, и это не позволило в полной мере оценить их значимость. Последующее увлечение мини- и микро-ЭВМ оттеснило на второй план тематику, связанную с централизованным хранением и коллективным использованием больших массивов данных. Однако история повторяется: микро-ЭВМ, объединенные в сети, быстро достигли, а затем и превысили возможности старых «больших» машин, накопленные данные стали востребованы многочисленными пользователями, и это вновь возродило интерес большим базам данных.

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

Таблица иллюстрирует изменение «основного вопроса информатики», и ключевой фигуры в процессе развития  вычислительной техники от примитивных счетных машин к современным.

Этап 1

Этап 2

Этап3

Этап4

обеспечение

аппаратное

программное

информационное

интеллектуальное

субъект

электроник

программист

пользователь

эксперт

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

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

Определение. Данные – это представление фактов и идей в формализованном виде, пригодном для передачи и переработки в некотором процессе, информация – это смысл, который придается данным при их представлении. Обработка данных – выполнение систематических последовательных действий с данными.

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

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

Для упрощения дальнейшего изложения приведем некоторые термины.

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

Системы хранения данных на основе файлов

В начальной стадии развития информатики прикладные информационные системы работали непосредственно с файлами данных. Программы обработки занимались ведением конкретных файлов, то есть, в основном, добавлением, удалением, корректировкой данных, сортировкой и выдачей. Файлы содержали все данные, необходимые для обработки. Получающаяся избыточность с высокой вероятностью приводила к противоречивости данных. Исключение избыточности существенно увеличивало сложность обработки за счет вовлечения в нее одновременно нескольких файлов. Логическая структура данных, как правило, определялась разработчиком для конкретной задачи, в крайнем случае, для группы задач. Более того, нередко данные различных приложений отличались и физическими структурами. В этой ситуации шагом вперед стало использование обобщенных методов доступа к данным, которые определяли их структуру на нижнем уровне. Системы, поддерживающие эти методы, обычно называются Системами Управления Файлами – СУФ (File Manager – FMGR), они включаются в операционные системы (ОС). Но универсальные программы работают с единственным представлением данных или же с фиксированным числом представлений. Примером может служить СУФ в ОС RTE фирмы Hewlett-Packard, где используется 6 форматов файлов.

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

  •  ограничение разделения данных;
  •  ограничение по доступности;
  •  сложность в управлении.

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

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

База данных

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

Основное отличие баз данных от систем на основе файлов состоит в том, что эти системы имеют несколько назначений и несколько представлений о данных, а базы данных – несколько назначений и одно представление о данных.

Определение. Система управления данными (СУБД) – комплекс программно-аппаратных средств, обеспечивающих доступ к БД и управление данными.

Требования к СУБД

  •  Эффективное выполнение функций ПО.
  •  Минимизация избыточности.
  •  Предоставление непротиворечивой информации.
  •  Безопасность.
  •  Простота в эксплуатации.
  •  Простота физической реорганизации.
  •  Возможность централизованного управления.
  •  Упрощение приложений.

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

Администратор БД (АБД)

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

Администратор БД – это сотрудник, выполняющий следующие функции:

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

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

Подробнее об АБД см. в [2].


Лекция 2

Модели данных

Независимость данных

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

  •  каков формат данных;
  •  где они располагаются;
  •  как к ним обратиться.

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

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

  •  1-й уровень независимости – логическая независимость,
  •  2-й уровень – физическая независимость.

При наличии независимости на 1-м уровне решения, принимаемые в КМ, не зависят от выбираемой СУБД. Независимость на 2-м уровне означает, что реализация ЛМ не зависит от метода доступа, расположения данных, типа ЭВМ, характеризующих ФМ. Отсюда следует, что для обеспечения независимости в КМ не должны учитываться особенности СУБД, а методы доступа к данным должны быть скрыты.

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

Модель, схема

Определение. Модель данных – средство для определения логического представления физических данных, относящихся к ПО.

Модель данных – ни что иное, как формализация данных прикладной области для возможности их обработки. Она характеризуется тремя компонентами:

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

Объекты, которыми оперирует модель, представляют собой сущности. Сущности могут быть в некотором отношении друг к другу: если A, B – множества сущностей, то отношение A R B показывает их связь. Модель, таким образом, представляет собой совокупность сущностей и связей. Сущности и связи имеют содержательную (смысловую) интерпретацию. Подобные модели называются моделями «сущность-связь» или, используя английскую аббревиатуру, ER-моделями [21].

Связи характеризуются кардинальными числами. Говорят об отображении один к одному (1:1), обозначается “”, один ко многим (1:M), обозначается “”, многие ко многим (M:N), обозначается “”. Связи между сущностями называются еще “ассоциациями”.

Пример

ОБЪЕКТ

АТРИБУТ

Пациент

номер, имя, адрес, диагноз, паспорт

Врач

имя, специальность

Койка

палата, номер койки

Отношения между объектами (сущностями):

(1) 1:1 пациент койка (1) 1:1 номер паспорт

(2) 1:М палата  пациент (2) 1:М имя  номер

(3) М:N пациент  врач (3) М:N имя пациента имя врача

Конец примера

Обычно рассматриваются три основных модели представления данных, которые отличаются ограничениями, накладываемыми на представление данных и виды связей. Это, в порядке хронологии появления, иерархическая, сетевая и реляционная модели. В настоящее время развивается и четвертый тип модели – объектно-ориентированный, но его изучение выходит за рамки данного курса.

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

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

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

Проектирование данных – процесс перевода общих представлений о данных, выраженных концептуальной моделью, в конкретную логическую модель. При ее создании полезно руководствоваться наборос простых правил, предложенных в [2]. Соблюдение каждого из них позволит обеспечить нормальную работу соответствующей информационной системы. Вот эти правила:

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

Теперь приведем более точное определение СУБД с учетом того, что она должна поддерживать эти правила.

Определение. СУБД – набор программных средств, позволяющих

  •  обеспечить пользователя языковыми средствами манипулирования данными – языки определения данных (ЯОД) и языки манипулирования данными (ЯМД);
  •  обеспечить поддержку моделей пользователя;
  •  обеспечить реализацию ЯОД и ЯМД: отображение операций над данными в операции над физическими данными;
  •  обеспечить защиту (полномочия) и целостность (согласованность) данных.


Лекция 3

Ранние модели

Иерархическая модель

Иерархическая модель данных – модель с отношением подчиненности между данными.

Определение. Отношение объектов иерархической модели определяется следующими правилам:

А подчинено Б Б не подчинено А;

А подчинено Б (А подчинено В) (Б тождественно В),

где А, Б, В – объекты. Другими словами, иерархическая модель реализуется древовидной структурой.

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

Заметим, что данное определение не позволяет определить пустую модель, модель, состоящую из одного лишь корня. Кроме того, здесь допускается несвязная модель.

Иерархическая модель обладает следующими свойствами.

  1.  Существует корень.
  2.  Узел содержит атрибуты.
  3.  Исходный и зависимый узлы находятся в отношении «непосредственный предок и потомок». Узлы добавляются горизонтально и вертикально.
  4.  Потомок соединен единственной связью с предком.
  5.  Предок может иметь несколько потомков.
  6.  Доступ к данным производится через предка.
  7.  Может существовать множество экземпляров узла.
  8.  При удалении узла удаляется все его поддерево.

Пример

(А)  (Б)

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

Аномалия включения: В БД (А) невозможно включить не оперировавшего хирурга.

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

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

Конец примера

Достоинства

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

Недостатки

Основной недостаток – невозможность реализации отношения «многие к многим» в рамках одной базы данных. Реализация такого отношения на основе двух БД затрудняет управление.

Первая СУБД, построенная по иерархической модели – IMS компании IBM (1969 г.). Она до сих пор эксплуатируется на разных платформах. Кроме того, примером иерархической СУБД может служить ДИАМС, входящий в программное обеспечение ЭВМ типа СМ-4 (зарубежный аналог – MAMS фирмы DEC). Есть вариант этой СУБД и для персональных ЭВМ.

Сетевая модель

Сетевая модель основана на рекомендациях рабочей группы по базам данных КОДАСИЛ (CODASYL), которые стали фактически первым стандартом в области систем баз данных (1969-1978 гг.). В дальнейшем изложении используются терминология и ограничения, введенные этим комитетом.

Согласно рекомендациям, база данных делится на области, те – на записи, состоящие из полей. С другой стороны, база состоит из наборов, а те – из записей:

Пример

Область “Пациент” Область “Хирург”

Связь «пациент-операция» означает «пациент перенес операцию», «хирург-операция» – «хирург выполнил операцию».

Конец примера


Определения

Запись – иерархия, образованная из простейших (атомарных) элементов данных, их групп и повторяющихся групп.

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

Тип набора – множество экземпляров набора. К набору относятся записи – члены набора и владелец набора. Записи-владельцы (члены) могут быть одновременно владельцами (членами) других наборов.

Первое определение совпадает с определением записи в языке КОБОЛ. Третье определение задает отношение «владелец-член».

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

Ограничения КОДАСИЛ

  1.  Тип набора определяет отношение 1:М между типом записи-владельца и типом записи-члена.
  2.  Экземпляр типа записи-члена может участвовать только в одном экземпляре типа набора.

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

Пример

Отношение «пациент-хирург» – это отношение M:N, и согласно ограничению КОДАСИЛ, его впрямую реализовать нельзя. Однако проблема решатся просто, если пациент и хирург будут владельцами, а операция – членом набора:

Такая связь часто называется Y-структурой. Кроме нее, встречаются другие связи:

иерархическая многочленная

Конец примера

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

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

Достоинства

  •  Реализуется отношение "многие к многим".
  •  Высокая производительность.

Недостатки

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

Первая СУБД, построенная по сетевой модели – IDMS (1971 г.). Правами на нее обладает компания Computer Associates, она до сих пор поставляет и развивает эту СУБД. Примером может служить и СУБД IMAGE/1000 фирмы Hewlett-Packard.


Лекция 4

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

Постановка задачи

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

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

Диаграмма

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

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

СУБД

База данных реализована в сетевой СУБД IMAGE/1000 фирмы Hewlett-Packard. Устройство ее следующее. Общие сведения о базе данных хранятся в корневом файле. Наборы-владельцы (ключевые наборы), как и наборы-члены (детальные наборы) реализованы в виде отдельных файлов, структура которых различна.

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

Диаграмма фрагмента БД «Санатории»

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

Описание на ЯОД

В СУБД IMAGE/1000 реализован специальный ЯОД, подробное описание которого выходит за рамки курса. Приведенный фрагмент определения БД «Санатории» дает достаточное представление о характере этого языка. Пояснения приводятся в комментариях (ограничители комментариев – <<..>>).

$CONTROL: TABLE, ROOT, FIELD;

BEGIN DATA BASE: SANAT::29; <<Имя корневого файла и номер диска>>

LEVELS:  <<Уровни доступа к данным>>

1  INSP <<Инспектор>>

10 MNGR <<Руководитель>>

11 ADM <<Администратор>>

ITEMS: <<Описание атрибутов:>>

<<имя, тип, длина, доступ по чтению и записи>>

NOM, X6(1,1); <<Номер>>

NAME, X34(1,1); <<Текст, соответствующий номеру>>

NOMLK, I1(1,1);  <<Номер люкса (комнаты)>>

OFFICE, X6(1,1);  <<Код учреждения>>

OFFNAM, X34(1,1);  <<Название учреждения>>

POST, X6(1,1);  <<Код должности>>

POSTNAM, X34(1,1);  <<Название должности>>

SANAT, X6(1,1);  <<Код санатория>>

SANAM, X34(1,1);  <<Название санатория>>

PROFIL, I1(1,1);  <<Код профиля санатория>>

PRONAM, X34(1,1);  <<Название профиля санатория>>

ADDRESS, X80; <<Адрес>>

WAY, X80; <<Дорога в санаторий>>

NLUX, I1; <<Число люксов в санатории>>

NROOM, I1; <<Число комнат в санатории>>

NPAL, I1; <<Число коек в палатах санатория>>

.  .  .

SETS:

<< Владелец должности >>

NAME: NKPOS::29,A; <<Имя владельца; A – автоматический>>

  ENTRY:  <<Атрибуты>>

     POST(4),  <<Имя атрибута и количество ссылок>>

CAPACITY: 817;  <<Размер набора (таблицы)>>

<< Номер люкса (комнаты) >>

NAME: NOLXKO::29,A;

  ENTRY:

     NOM(4),

CAPACITY: 817;

.  .  .

<< Описание люксов >>

NAME: NOLUX::29,D; <<Имя члена; D – детальный>>

  ENTRY:

     NOM(NOLXKO), <<Имя атрибута и ссылка на владельца>>

     NOMLK,

     SANAT(NKLPOS),

     NMEST,

     CATEG(NKLMN),

     QUALIT,

CAPACITY: 101;

<< Описание должности >>

NAME: NOPOST::29,D;

  ENTRY:

     POST(NOLXKO),

     POSNAM,

CAPACITY: 311;

<< Вид льготы >>

NAME: NOLGO::29,D;

  ENTRY:

     NOMORD,

     NAME,

CAPACITY: 7;

.  .  .

END.

Лекция 5

Реляционная модель

Принципы

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

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

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

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

Модель

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

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

Структурная часть реляционной модели состоит из следующих компонент:

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

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

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

Кодд приводит критерии, по которым СУБД можно отнести к реляционным. Эти критерии следующие:

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

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

Уточнения

Определение. Пусть существует n доменов D1,…,Dn. Отношение R представляется как подмножество D1D2Dn, т.е. подмножество упорядоченных n-ок  (d1,d2,…,dn) – кортежей. Домен Di представлен i-м элементом. Вместо упорядоченности чаще используют уникальные имена.

Не каждое отношение может быть объектом реляционной модели. Важное свойство отношений реляционной модели – нормализованность.

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

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

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

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

Таким образом, мы сформулировали следующие свойства отношений:

  1.  Нормализованные отношения представляются в виде табличной структуры.
  2.  Упорядоченность кортежей теоретически несущественна.
  3.  Все кортежи различны.


В терминологии реляционной модели следующие понятия рассматриваются как синонимы:

Таблица синоним Отношения,

Столбец синоним Атрибута,

Строка синоним Кортежа.

Наконец, осталось дать следующее

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

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

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

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

Пример

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

Заголовок ведомости

Номер
ведом
ости

Код
предм
ета

Код
преподавателя

Дата сдачи

Семестр

Группа

1

10

7

03.01.2005

5

306

2

5

3

07.01.2005

7

406

Ключи – (1) номер ведомости; (2) код предмета, семестр, группа.

Внешние ключи – (1) код предмета; (2) код преподавателя.

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

Предметы

Код предмета

Название предмета

5

Машинная графика

10

Базы данных

Ключи – (1) код предмета.

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

Преподаватели

Код преподавателя

ФИО преподавателя

Должность преподавателя

3

Чернышов Л.Н.

Доцент

7

Лукин В.Н.

Доцент

Ключи – (1) код преподавателя; (2) ФИО преподавателя.

Таблица, как и предыдущая, служит справочником. Она имеет атрибут «Должность», который тоже может быть представлен кодом.

Успеваемость

Номер ведомости

Номер студента

Оценка

1

1

5

1

2

4

2

1

5

2

2

3

1

3

3

2

3

5

Ключи – (1) номер ведомости, номер студента.

Внешние ключи – (1) номер ведомости; (2) номер студента.

Основная таблица, отражающая успехи студентов. Каждый кортеж однозначно определяется уникальным кодом ведомости и номером студента в списке группы. Для получения дополнительных атрибутов, например, номера группы, используется внешний ключ «Код ведомости» (связь с таблицей Заголовок ведомости), для расшифровки фамилии студента служит внешний ключ «Номер студента».

Студенты

Номер студента

Группа

Номер зачетки

ФИО студента

1

306

9708104

Иванов И.И.

2

306

9708035

Петров П.П.

3

306

9708117

Сидоров С.С.

1

506

9508017

Алексеев А.А.

1

506

9508027

Борисов Б.Б.

1

506

9508037

Васильев В.В.

Ключи – (1) группа, номер студента; (2) номер зачетки.

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

Конец примера


Лекция 6

Методы хранения данных и доступа к ним

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

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

Для оценки методов доступа и хранения используются понятия эффективности доступа и эффективности хранения.

Определение. Эффективность доступа – отношение числа логических обращений к числу физических при выборке элемента данных.

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

Например, если на одно логическое обращение требуется два физических, то эффективность доступа 0,5. Если на 10 байт информации требуется одна двухбайтовая ссылка, эффективность хранения 10/12.

Последовательный метод

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

Прямой метод

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

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

Индексные методы

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

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

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

Существует множество индексных методов доступа. Рассмотрим три из них: индексно-последовательный, индексно-произвольный и метод инвертированных списков.

Индексно-последовательный метод

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

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

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

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

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

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

Пример

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

Конец примера

Индексно-произвольный метод

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

Как и в индексно-последовательном методе, нужно стремиться к тому, чтобы весь индекс размещался в памяти. Но в данном случае, в силу плотности индекса, ситуация хуже из-за большего размера индекса. Более того, иногда он может превышать размер информационного файла. Уменьшение области поиска достигается, например, построением многоуровневого индекса. Ключи обычно бывают упорядоченными для последующего дихотомического поиска, но не исключаются и другие алгоритмы. Естественно, упорядоченность записей в информационном файле не существенна, однако иногда она позволяет заметно сократить время работы. Например, выдача отчета по всему файлу с сортировкой по ключу поиска приведет к последовательному просмотру статей индекса, но к хаотичному выбору записей в случае их сильного перемешивания по этому ключу. Это, в свою очередь, приводит к «дерганью» головки дисковода, что резко увеличивает время доступа. Решение проблемы – сортировка по ключу поиска. К замедлению поиска приводит и дублирование значений ключей, следовательно, этот метод наиболее эффективен для первичных индексов.

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

Эффективность хранения зависит от размера индекса.

Пример

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

Конец примера

Инвертированные списки

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

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

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

Эффективность доступа зависит от эффективности поиска в индексе, но в любом случае она ниже 0,5 (доступ к индексу и доступ к записи файла). Для повышения эффективности следует размещать индексы в оперативной памяти.

  1.  

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

Пример

В приведенном примере в информационном файле (правый прямоугольник) размещается список студентов с оценками. Требуется выбрать всех студентов, имеющих одинаковое значение оценки. Левый прямоугольник символизирует индекс, в котором находится единственный вторичный ключ – «оценка». Каждому его значению соответствует список, в котором перечислены соответствующие номера записей информационного файла. Выбор всех двоечников сводится к нахождению в индексе соответствующего значения ключа «оценка» и загрузки записей, указанных в списке. Если нужно найти тех, кто получил «4» или «5», следует найти и объединить соответствующие списки. Подобные действия выполнялись бы, если бы запись содержала еще один вторичный ключ, скажем, предмет. Тогда для выборки тех, кто получил пятерки по предмету «Базы данных», следовало бы в соответствующих индексах найти списки для требуемых значений и взять их пересечение.

Конец примера

Хеширование

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

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

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


Лекция 7

Реляционная алгебра: определения, изменение отношений

Схема, отношение. Ключ

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

Определение. Схема – конечное множество имен атрибутов {A1, A2 , ..., An}.

Каждому имени Ai ставится в соответствие домен Di: Di=dom(Ai). Обозначим D = i=1n Di .

Определение. Отношение r со схемой R – конечное множество отображений {t1, t2 , ..., tn} из R в D, причем, для каждого отображения t r и каждого i значение атрибута Ai берется из Di . Эти отображения называются кортежами.

Пример

Дана схема отношений Рейсы = {номер, пункт отправления, пункт назначения, время вылета, время прилета}. Здесь определены следующие домены:

  1.  dom(номер) – множество целых чисел {1..999};
  2.  dom(пункт отправления) = dom(пункт назначения) = {аэропорты};
  3.  dom(время вылета) = dom(время прилета) – время суток (часы, минуты).

Тогда отношение со схемой Рейсы может выглядеть так:

83

Новгород

Чита

11:30

17:30

84

Чита

Новгород

20:50

3:40

109

Новгород

Липецк

21:50

23:50

213

Новгород

Байконур

10:00

14:00

214

Байконур

Новгород

16:00

20:00

Конец примера

Примем следующие обозначения. Будем обозначать первыми заглавными латинскими буквами (A, B, ...) имена атрибутов, буквами R, Q – схемы атрибутов, строчными первыми (a, b, ...) – атрибуты, строчными r, q – отношения. Схему R={A1, A2, ..., An} будем обозначать R[A1, A2, ..., An] или A1A2...An , отношение r со схемой R обозначим r(R) или r(A1A2...An).

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

Значение кортежа t на атрибуте A будем называть A-значением кортежа t. Если XR, будем называть t(X) X-значением кортежа t. Предполагается, что существует значение : t()= для каждого кортежа t, t1()=t2().

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

Определение. Ключ отношения со схемой R – это K={B1, B2 , ..., Bm } R  со свойством: для t1, t2 r, t1t2, BK такой, что t1(B) t2(B), то есть не существует двух различных кортежей, имеющих одинаковое значение на всех атрибутах K (t1(K) t2 (K)).

Атрибуты, входящие в ключ, будем выделять подчеркиванием, например r(ABCD) или R[ABCD]. Если отношение содержит более одного ключа, каждый из них задается отдельно. Ключи, явно перечисленные в схеме, называются выделенными, остальные – возможными, один из выделенных называется первичным.

Приведенное определение ключа слишком широкое, оно допускает существование подключа, то есть если K – ключ отношения r(R) и KKR, то K тоже ключ.

Определение. Ключ отношения r(R) – это подмножество K R такое, что для t1, t2 r, t1t2, следует t1(K) t2 (K) и ни одно K K не обладает этим свойством.

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

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

Изменение отношений во времени.

Размещение дополнительной информации производится операцией добавления ADD(r; A1=d1, A2=d2 , ..., An=dn).

Пример

Для добавления рейса из Астрахани в Барнаул достаточно записать:
ADD(Рейсы; номер = 117, пункт отправления = Астрахань, пункт назначения = Байконур, время вылета = 22:05, время прилета = 0:43).

Конец примера

Вариант для фиксированного порядка атрибутов: ADD(r; d1, d2, ..., dn).

Возможные ошибки при добавлении:

  1.  кортеж не соответствует схеме;
  2.  некоторые значения не принадлежат доменам;
  3.  есть совпадения по ключу.

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

Удаление информации производится операцией DEL(r; A1=d1, A2=d2 , ..., An=dn) или DEL(r; d1, d2 , ..., dn).

Если K={B1, B2 , ..., Bm } – ключ отношения, для удаления достаточно записать DEL(r; B1=b1, B2=b2 , ..., Bm=bm).

Пример

Если {пункт отправления, пункт назначения, время вылета} – ключ отношения Рейсы, для удаления рейса из Новгорода в Читу можно записать:
DEL(Рейсы; пункт отправления = Новгород, пункт назначения = Чита, время вылета = 11:03). 

Если ключ – это номер рейса, достаточно записать:
DEL(Рейсы; номер = 83).

Конец примера

Возможная ошибка – отсутствие удаляемого кортежа. Заметим, что допускается удаление последнего кортежа, то есть, пустое отношение может существовать.

Модификация информации производится операцией изменения. Пусть {C1, C2, ... Cp} {A1, A2, ... An}. Тогда CH(r; A1=d1, A2=d2 , ..., An=dn ; C1=c1, C2=c2 , ..., Cn=cp) или, в случае ключа, CH(r; B1=b1, B2=b2 , ..., Bm=bm ; C1=c1, C2=c2 , ..., Cn=cp).

Пример

Для изменения времени вылета и времени прилета рейса 109 из отношения Рейсы можно записать:
CH(Рейсы; номер = 109, пункт отправления = Новгород, пункт назначения = Липецк, время вылета = 21:50, время прилета = 23:50; время вылета = 20:00, время прилета = 22:00).

Если в ключ – это номер рейса, достаточно записать:
CH(Рейсы; номер = 109; время вылета = 20:00, время прилета = 22:00).

Конец примера

Того же эффекта можно достигнуть последовательным удалением изменяемого кортежа и добавлением нового. Поэтому ошибки модификации представляют собой объединение ошибок удаления и добавления.


Лекция 8

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

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

Булевы операции

К булевым операциям относятся операции пересечения, объединения, разности. Пусть r, s – отношения со схемой R. Они могут рассматриваться как подмножества множества всех кортежей, определяемых этой схемой, поэтому к ним применимы булевские операции.

Пересечением называется отношение q(R) = r s, содержащее кортежи, которые одновременно принадлежат и r, и s. Объединением называется отношение q(R) = r s, содержащее кортежи, которые принадлежат либо r, либо s. Разностью называется отношение q(R) = r - s, содержащее кортежи, которые принадлежат r, но не принадлежат s. Или формально:

rs ={t|(tr)&(ts)};

rs ={t|(tr)(ts)};

rs ={t|(tr)&(ts)}.

Заметим, что r s = r – (r – s), то есть достаточно лишь двух операций.

Обозначим dom(R) множество всех кортежей над атрибутами из схемы R и их доменами: dom(R) = {t(d1 d2 dn)| di dom(Ai)}. Дополнение отношения определим как r(R): r = dom(R) - r(R). Но если какой-либо атрибут из R имеет бесконечный домен, r будет тоже иметь бесконечное число кортежей, то есть по определению не будет отношением.

Определение. Пусть r(A1, A2,..., An) – отношение, Di = dom(Ai). Тогда активный домен атрибута Ai относительно r – это множество adom(Ai,r) = {dDi | tr, t(Ai)=d}.

Пусть adom(R,r) – множество всех кортежей над атрибутами из R и их активными доменами относительно r: adom(R, r) = {t(d1 d2 dn)| di adom(Ai, r)}. Тогда активным дополнением r будем называть . Так как число значений атрибутов, принадлежащих кортежам из r, конечно, то активное дополнение всегда будет отношением.

Пример

r

(A

B

C)

s

(A

B

C)

a1

b1

c1

a1

b2

c1

a1

b2

c1

a2

b2

c1

a2

b1

c2

a2

b2

c2

rs

(A

B

C)

rs

(A

B

C)

r - s

(A

B

C)

a1

b2

c1

a1

b2

c1

a1

b1

c1

a2

b2

c1

a2

b1

c2

a2

b2

c2

a1

b1

c1

a2

b1

c2

Тогда

Пусть D1={a1, a2}, D2={b1, b2, b3}, D3={c1, c2}. Тогда dom(R) – все комбинации значений атрибутов из доменов, r = dom(R) - r – все комбинации, за исключением тех, что входят в r. Активный домен B не содержит b3, поэтому adom(R,r) – все комбинации значений, не содержащие b3. Тогда активное дополнение – все комбинации из adom(R,r) без кортежей из r.

Конец примера

Выбор; свойства выбора

Пусть теперь A – это некоторый атрибут отношения r(R) и a – элемент множества значений, которые может принимать отображение t на этом атрибуте. Выберем из отношения r те кортежи, для которых отображение t на A принимает значение a, и результат обозначим через A = a(r). Это унарная операция (она применяется к одному отношению), в результате которой у нас появляется новое отношение r (R).

Определение. Выбором A = a(r) называется отношение r (R) = A = a(r){tr | t(A)=a}.

Пример

Пусть отношение r – расписание рейсов с атрибутами номер (№), пункт отправления (ПО), пункт назначения (ПН), время вылета (ВВ) и время прилета (ВП).

Расписание  (№ ПО ПН ВВ ВП)

119

Новгород

Чита

11:30

17:30

94

Чита

Керчь

20:50

3:40

117

Баку

Орёл

21:50

23:50

216

Новгород

Москва

10:00

14:00

217

Москва

Киев

16:00

20:00

ПО = Новгород(расписание) (№ ПО ПН ВВ ВП)

119

Новгород

Чита

11:30

17:30

216

Новгород

Москва

10:00

14:00

Конец примера

Пусть r и s – отношения со схемой R; A, B, C,…  – конечное число атрибутов в R, пусть adom(A), bdom(B), cdom(C),… . Тогда верны следующие утверждения.

Утверждение 8.1. Операторы выбора коммутативны относительно операции композиции (т.е. результат их применения не зависит от последовательности):

A = a  B = b(r)  A = a(B = b(r)) = B = b(A = a(r))  B = b  A = a(r).

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

A = a(B = b(r)) = A = a({tr | t(B) = b}) =

= { t{tr | t(B) = b}| t (A) = a }=

= { tr | t(A) = a, t(B) = b} =

= { tr | t(B) = b, t(A) = a} =

= { t{tr | t(A) = a}| t (B) = b }=

= B = b({tr | t(A) = a}) = B = b(A = a(r)).

Введём следующее обозначение: A = a  B = b  A = a, B = b . Положим X = (A, B, C,…), а x = (a, b, c,…), тогда оператор выбора можно обозначить X = x. .

Утверждение 8.2. Операция выбора дистрибутивна относительно бинарных булевых операций:

A = a(rs) = A = a(r)  A = a(s), где {, , – }.

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

A = a(rs) = A = a({t | tr, ts}) =

= {t{t | tr, ts} | t (A) = a} =

= {t | tr, t(A) = a} {t | ts, t(A) = a} =

= A = a({t | tr})  A = a({t | ts}) = A = a(r)  A = a(s).

Аналогично доказываются равенства A = a(rs)=A = a(r)A = a(s) и A = a(rs) = = A = a(r) A = a(s).

Замечание. Операции выбора и активного дополнения не перестановочны (не коммутируют). Можно показать, что A = a(r)  A = a ().

Проекция; свойства проекции

Пусть r – отношение со схемой R, X  R.

Определение. Проекцией X(r) называется отношение r(X) = X(r) {t(X) | tr }.

Это унарная операция, но в отличие от операции выбора, которая выдаёт строки по заданным условиям, она выдаёт столбцы, заголовки которых перечислены в X.

Пример

Воспользуемся отношением расписание из предыдущего примера:

{ВВ, ВП}( расписание) = (ВВ ВП)

11:30

17:30

20:50

3:40

21:50

23:50

10:00

14:00

16:00

20:00

ПН( расписание) = (ПН)

Чита

Керчь

Орёл

Москва

Киев

Конец примера

Если Y – собственное подмножество X, то Y(X(r)) = Y(r). В общем случае, если X1  X2  Xm, то X1  X2  Xm = X1.

Утверждение 8.3. Операторы проекции и выбора перестановочны относительно композиции:

X A = a (r)  X(A = a (r)) = A = a (X(r))  A = a  X (r).

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

X(A = a (r)) = X({tr | t(A) = a}) =

 = {t(X) | t{tr| t (A) = a}} =

 = {t(X) | tr, t (A) = a} =

 = A = a ({t(X) | tr}) = A = a (X(r)).


Лекция 9

Операции реляционной алгебры (продолжение)

Соединение

Определение. Пусть r(R) и s(S) – отношения. Соединением r и s называется отношение r s = q(RS) = {t(RS) | tr  r, ts  s : tr = t(R), ts = t(S)}.

Пример

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

r s = (Рейс      Пилот       Самолёт)

43

Сидоров

ТУ-154

43

Борисов

ТУ-154

43

Петров

ИЛ-86

105

Сидоров

ТУ-134

s(Пилот    Самолёт)

Сидоров

ТУ-134

Сидоров

ТУ-154

Борисов

ТУ-154

Петров

ИЛ-86

r(Рейс  Самолёт)

43

ТУ-154

43

ИЛ-86

105

ТУ-134

Конец примера

Если RS = {B1B2Bl} = , то соединение rs, результатом которого является множество кортежей t(A1A2Ak C1C2Cm), таких, что t(A1A2Ak)r и t(C1C2Cm)s, называется декартовым произведением отношений r и s. Декартово произведение обозначается r  s.

Пример

Исходные отношения:

Их соединение (декартово произведение):

Конец примера

Свойства соединения

Свойство 1. Имитация выбора.

С помощью оператора соединения найдём A=a(r) для отношения r(R). Для этого определим отношение s(A) с одним единственным кортежем t таким, что t(A) = a. Тогда r  s = A=a(r).

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

r  s = {t | tr r, ts  s, tr = t(R), ts = t(A)} =

= {t | tr  r, tr = t(R), t(A) = a} =

= {t | t(A) = a } = A=a(r).

Свойство 2. Обобщённая операция выбора.

Введём новое отношение s(A) с k кортежами t1, t2,…, tk, где ti(A) = ai и ai  dom(A), i =1, 2,…, k. Тогда r  s = A=a1(r) A=a2(r) A=ak(r).

Свойство 3. Коммутативность оператора соединения.

Из определения следует, что r  s = s  r.

Свойство 4. Ассоциативность оператора соединения.

Для отношений q, r, s  (q  r)  s = q (r  s). Следовательно, последовательность соединений можно записывать без скобок.

Свойство 5. Многократные соединения.

Пусть r1(S1), r2(S2),…, rn(Sn) – отношения, R = S1S2Sn. Обозначим S – последовательность схем S1, S2,…, Sn. Пусть t1, t2,…, tn – последовательность кортежей, ti ri, i = 1, 2,…, n.

Определение. Кортежи t1, t2,…, tn соединимы на S, если существует кортеж t на R, что ti = t(Si) для каждого i = 1, 2,…, n. Кортеж t называется результатом соединения кортежей t1, t2,…, tn на S.

Пример

Кортежи <a1  b1>, <b1  c2>, <a1  c2> соединимы с результатом <a1  b1   c2>, а кортежи  <a2  b1>, <b1  c2>, <a2   c2> – c результатом <a2  b1   c2>:

 

 

Конец примера

Если в определении принять n=2 и если кортежи t1 и t2 соединимы на S=S1, S2 с результатом t, то t1=t(S1), t2=t(S2), следовательно, tr(S1) r(S2). Обратно, если tr(S1) r(S2), то должны существовать t1 и t2 в r(S) такие, что t1=t(S1), t2=t(S2), то есть они соединимы на S с результатом t. Следовательно, r(S1) r(S2) состоит из результатов соединений соединимых на S кортежей t1 и t2 .

Лемма. Отношение r1 r2 rn состоит из всех кортежей t, которые являются результатом соединения соединимых на S кортежей ti ri, i = 1, 2,…, n. 

Не каждый кортеж каждого отношения может войти в соединение.

Определение. Отношения r1, r2,…, rn полностью соединимы, если каждый кортеж в каждом отношении является членом списка соединимых на S кортежей.

Пример

Из предыдущего примера <a1 b2> r1, <b2 c1> r2 не соединимы. При добавлении к r3  кортежа <a1 c1> отношения становятся полностью соединимыми с результатом

Конец примера

Свойство 6. Проекция соединения.

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

Пусть r(R) и s(S) – отношения, q = r s, RS – схема q. Пусть r = R(q), тогда r  r (для любого кортежа t из отношения q верно t(R) r, а r =t(R) t q).

Включение может быть собственным:

Может быть равенство (r = r): 

Ясно, что равенство может быть при соединении полностью соединимых отношений, но может быть и без этого.

Если s = S(q), то r = r и s = s тогда и только тогда, когда r и s – состоят из полностью соединимых кортежей, то есть полностью соединимы.

Свойство 7. Соединение  проекций.

Поменяем местами проекции и соединения. Пусть q – отношение со схемой RS, r = R(q), s = S(q). Пусть q′= r s. Если t q, то t(R) r, t(S) s    tq′, т.е. q′ q. При q′ = q отношение разложимо без потерь на схемы R и S.

Свойство 8. Соотношение операций объединения и соединения.

Пусть r и r – отношения со схемой R и s – отношение со схемой S. Покажем, что (rr) s = (r s)(r  s). Обозначим левую часть равенства как q  (rr)  s, а правую буквой q  (r s)(r  s). Для кортежа tq найдутся кортежи tr и ts такие, что t = tr  ts, причем trr или trr и tss. Если trr, то t r  s, если же trr, то t r  s, то есть q  q. Чтобы установить включение q  q, выберем tq. Тогда trs или trs, следовательно, t (rr)  s. Включения q  q и q  q выполняются одновременно только в том случае, когда q = q.


Лекция 10

Операции реляционной алгебры (продолжение)

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

Деление

Определение. Пусть r(R) и s(S) – отношения, SR. Положим R = R - S. Тогда r, разделенное на s – это отношение r(R)={t | tss trr: tr(R)=t & tr(S)=ts}.

Отношение r– частное от деления r на s, что обозначается r= rs. Иначе rs – это максимальное подмножество r множества R (r), такое, что r  s r. Соединение здесь – декартово произведение.

Пример

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

Пусть заданы два множества типов самолетов, представленных в виде отношений с одним атрибутом:

Для получения информации о пилотах,

имеющих право пилотирования самолетов из множества q или множества s может быть использована операция деления.

Конец примера

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

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

Определение. Пусть A1,…,Anразличные атрибуты, а ci является константой из dom(Ai) для 1 i  n, тогда с1 : А1,…,сn : An - постоянный кортеж с1,…,сn над схемой А1А2Аn.

Постоянное отношение над схемой А1А2Аn представляется как множество кортежей. Пусть cij – константа из dom(Ai ) для 1  i  n и 1  j  k, тогда

 

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

  

   

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

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

Пример

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

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

Конец примера

Определение. Пусть r – отношение со схемой R, AR, ВR – A, dom(A)=dom(B). Пусть R = (R – A)B. Тогда r с A, переименованным в В (обозначается АВ(r)) есть отношение r(R ) = {t | tr, t (RA) = t(R – A) & t (B) = t (A)}.

Пример (продолжение)

Отношение с искомыми парами рейсов:

Конец примера

Пусть r – отношение со схемой R,

A1,…, Ak  R;

B1,…, Bk  R – (A1Ak);   (1)

i: dom(Bi) = dom(Ai).

Обозначим одновременное переименование атрибутов A1,…, Ak в B1,…, Bk как A1,…, Ak  B1,…, Bk(r). Благодаря условию (1) оно всегда может быть записано в виде последовательности переименований. Если это условие не выполняется, без введения дополнительных атрибутов такую замену выполнить нельзя. Очевидный пример – обмен A, B B, A .

Эквисоединение, естественное и -соединение

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

Определение. Пусть r(R), s(S) – отношения, Ai R , Bi S , dom(Ai) = dom(Bi), 1 i  n (Ai и Bi могут быть одинаковыми). Эквисоединением r и s по A1, A2,…,Am и B1, B2,…, Bm называется отношение q(RS) = {t | tr r, tss, t(R) = tr, t(S) = ts, t(Ai) = t(Bi)}. 

В дальнейшем операцию эквисоединения отношений r и s по A1, A2,…,Am и B1, B2,…, Bm будем обозначать так:

r [A1 = B1, A2 = B2,…, Am = Bm] s.


Пример

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

Конец примера

Уточним определение. Не исключается существования A такого, что (A  R) & (A  S). Потребуем, чтобы в эквисоединении все атрибуты различались по именам, то есть, чтобы RS = . Это не сильное ограничение, так как путем переименования атрибутов в s и r можно добиться пустого пересечения их схем.

Замечание. Если в эквисоединении нет сравнений, то оно совпадает с декартовым произведением: r [ ] s = r  s.

Соединение, определённое ранее, иногда называют естественным.

Утверждение. Эквисоединение может быть выражено через переименование и естественное соединение. 

Естественное соединение также может быть выражено через эквисоединение. Например, для отношений r(A, B, C), s(B, C, D), атрибутов B и C с dom(B) = dom(B), dom(C) = dom(C): r  s = (r [B = B, C = C] B, CB, C (s) ).

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

Определение. Если знак сравнения , а A и B – атрибуты, то говорят, что A -сравним с B, если – бинарное отношение в dom(A)  dom(B).

Определение. Атрибут A -сравним, если он -сравним сам с собой.

Расширим оператор выбора, используя понятие -сравнимости. Пусть r – отношение со схемой R, атрибут A  R, a  dom(A) – константа, , A -сравним. Тогда расширенный оператор выбора Aa(r) = {t  r | t(A)  a}. Аналогично этот оператор определяется для случая сравнения между атрибутами, с учетом того, что B  R, dom(B)=dom(A): AB = {t  r | t(A)t(B)}.

Пример

Отношение время определяет время вылета рейса из аэропорта отправления и время его прибытия в аэропорт назначения. Применим оператор выбора для нахождения рейсов, у которых время прибытия не превышает 12 часов, и рейсов, у которых время вылета меньше времени прибытия, по крайней мере, на 2 часа (обозначим соответствующую операцию как <<). Кортежи первой выборки (s), пометим символом «*», второй (q) – «+».

s = время прибытия  12.00 (время)

q = время вылета << время прибытия (время)

Конец примера

Эквисоединение – это расширенное соединение для сравнения разных столбцов на равенство. Можно не ограничиваться равенством, а воспользоваться любой операцией .

Определение. Пусть r(R) и s(S) – отношения, для которых RS = , и пусть AR и BS -сравнимы для . Тогда -соединением называется отношение q(RS) = {t | trr, tss, t(R) = tr, t(S) = ts, tr(A)ts(B)}, которое обозначается q(RS) = r [AB] s.

Пример

В приведенных отношениях заданы времена вылета и прилета самолетов, совершающих рейсы соответственно из пункта a в пункт b и из пункта b в пункт c. Требуется узнать, какие рейсы могут проходить транзитом из города a в c через b.

транзит_ac = время_ab [прилёт < вылет] N, прилёт, вылетN, прилёт, вылет(время_bc) =

Конец примера

Реляционная алгебра. Полнота ограниченного множества операторов

Обозначим U – множество атрибутов (универсум), D – множество доменов, dom – полная функция из U в D, R = {R1, R2,…, Rp} – множество схем, Ri  U, d = {r1(R1), r2(R2),…, rp(Rp)} – множество наборов отношений, – множество бинарных отношений над доменами из D.

Определение. Реляционная алгебра над U, D, dom, R, d, – семиместный кортеж B=( U, D, dom, R, d, , O), где O –  множество операторов объединения, пересечения, разности, активного дополнения, проекции, естественного соединения, деления, переименования, которые используют атрибуты из U, и оператор выбора, использующий операторы из .

Теорема. Для выражения E над реляционной алгеброй существует выражение E’ над ней же, которое определяет ту же функцию и использует лишь операторы (1) постоянных отношений с единственным атрибутом и единственным кортежем, (2) выбора с одним сравнением, (3) естественного соединения, (4) проекции, (5) объединения, (6) разности, (7) переименования.

Следствие. Для реляционной алгебры с операцией дополнения в формулировке предыдущей теоремы изменится пункт (6): Для выражения E над реляционной алгеброй с операцией дополнения существует … (6)  дополнения, (7) переименования. 

Операторы расщепления и фактора

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

Определение. Пусть (t) – предикат на кортежах над R, тогда расщеплением r по называется пара отношений (s, s), каждое со схемой R, такие, что s = {tr | (t)} и s = { tr |(t)}. Обозначается эта пара SPLIT (r).

Пример

Рассмотрим отношение право, определённое в начале этой лекции. Пусть предикат (t) = {t(тип самолёта) = ТУ-134} {t(тип самолёта) = ТУ-154}. Тогда SPLIT (право) = (s, s), где

Конец примера

Определение. Пусть дано отношение r(R) и B1, B2,…, Bk  R, а L  R. FACTOR(r; B1, B2,…, Bk; L) = (s, s), где s = s((RB1B2Bk)L), s = s (B1B2BkL), причём по L возможно осуществить соединение s и s.

Действие последнего оператора рассмотрим на примере.

Пример

Рассмотрим список отдыхающих в некотором доме отдыха.

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

Конец примера


Лекция 11

Язык структурных запросов SQL

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

Продавцы

Ном_прод

Имя_прод

Город

Комиссия

11

Иванов

Москва

0,12

12

Петров

Тула

0,13

14

Сидоров

Москва

0,11

17

Борисов

Киров

0,15

13

Титов

Пенза

0,10

Покупатели

Ном_пок

Имя_пок

Город

Значимость

21

Комов

Москва

100

22

Емелин

Омск

200

23

Мохов

Тула

200

24

Попов

Рязань

300

26

Окулов

Москва

100

28

Глинка

Тула

300

27

Зимин

Омск

100

Заказы

Ном_зак

Сумма

Ном_пок

Ном_прод

Дата

301

18,7

28

17

03.10

303

767,2

21

11

03.10

302

1900,1

27

14

03.10

305

5160,4

23

12

03.10

306

1098,1

28

17

03.10

309

1713,2

22

13

04.10

307

75,7

24

12

04.10

308

4723,0

26

11

05.10

310

1309,9

24

12

06.10

311

3891,8

26

11

06.10

Здесь имена атрибутов обозначают следующее:

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

Начальные понятия

Язык, предназначенный для работы с реляционными базами данных – SQL (язык структурных запросов – Structured Query Language) – был призван продемонстрировать возможность эффективной работы с множествами, представленными отношениями. Возможности языка должны быть достаточными для реализации всех операторов реляционной алгебры. Язык должен быть непроцедурным – предполагалось, что таким образом облегчается работа пользователя, не умеющего программировать.

Большинству этих задач разработанный язык отвечает, однако не всем и не в той степени, как рассчитывали авторы. Во-первых, непонятно, какой смысл вкладывался в термин «структурный». То, что получилось, имеет очень слабое отношение к устоявшемуся понятию «структурное программирование». Далее, может ли язык работать с множествами? Да, и языковые средства для этого достаточно хороши. Однако об эффективности, особенно на первых порах внедрения языка, следует говорить осторожно. Первые реализации были столь громоздки, что при появлении СУБД на персональных ЭВМ об SQL даже речи не было. Более того, в течение значительного периода времени его считали умирающим языком и немного жалели о его гибели. Автору в это время приходилось читать лекции по базам данных, на которых слушатели отдавали дань уважения этому языку, но относились к нему как к исторической реликвии. Но все-таки языку удалось устоять, чему в немалой степени способствовал рост производительности ЭВМ, а также более эффективные методы реализации языка. Кроме того, уже существовал большой контингент специалистов по базам данных, владеющим языком и, что очень важно, действовал стандарт SQL.

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

Стандарт ANSI

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

Типы данных

Типы данных в различных версиях SQL могут заметно различаться, что связано с набором типов данных, принятом в конкретной СУБД. В стандарте ANSI рекомендуется использовать символьные (например, CHAR, VARCHAR) и числовые (INT, DEC) типы данных. В СУБД FoxPro используется широкий спектр типов  данных (различные формы символьных числовых типов, типы даты и времени и т.п.). Все они отражены в соответствующей реализации SQL.

Интерактивный и встроенный SQL

В стандарте предусмотрено существование двух форм языка: интерактивной и встроенной. Первая форма предполагает работу непосредственно в среде SQL и не требует наличия какой-либо другой программной среды. Считается, что запросы формулируются в режиме диалога и выполняются интерпретатором языка. Во втором случае язык каким-то способом встраивается в другую языковую систему и общается с пользователем через нее. То есть, интерфейс обеспечивает среда другого языка, а SQL выполняет запросы, поступающие из программы. В чистом виде это реализовано, например, в среде Delphi, а FoxPro даже включает операторы SQL в базовый язык.

Синтаксис

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

Текст ::= команда; ... команда;

Команда ::= фраза ... фраза

Фраза ::= Ключевое_слово аргумент аргумент ... аргумент

Подразделы SQL

Согласно рекомендации ANSI, SQL состоит из следующих разделов: Язык Определения Данных (ЯОД или DDL), Язык Манипулирования Данными (ЯМД или DML), Язык Управления Данными (ЯМД или DCL). Последний раздел может включаться в ЯМД. Первый раздел служит для определения схем данных (таблиц), второй – для манипуляций данными, которые выполняются через запросы к базе данных.

Простейшие действия

Определение таблиц – это разовая работа, изменение структуры – эпизодическая, а манипулирование данными – деятельность постоянная. И если изменение содержания базы данных большой сложности не представляет, то выборка необходимой информации может быть довольно замысловатой. Именно на запросы расходуется наибольшее время работы с БД. Поэтому основу языка SQL составляют запросы к базе данных. Запросы определяются командой Select.

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

Select [Distinct] <список атрибутов> From <таблица> [Where <условие>];

Здесь <список атрибутов> – схема (перечень атрибутов) отношения, которое будет результатом выполнения команды. В список может включаться символ «*», который обозначает всю схему исходной таблицы с именем <таблица>. В результирующую выборку попадают атрибуты лишь из тех строк, для которых <условие> истинно. Фраза Where не обязательная, если она отсутствует, в выборку попадают атрибуты из всех строк. Заметим, что в результирующей выборке могут возникнуть повторяющиеся строки, если список атрибутов не содержит ключ. Для удаления дублирующихся строк служит вариант Distinct.

Пример

Выбрать содержимое всей таблицы продавцов (представлены два варианта):

Select * From Продавцы;

Select ном_прод, имя_прод, город, комиссия From Продавцы;

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

Select Distinct имя_прод, город From Продавцы;

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

Select дата, ном_пок, ном_зак From Заказы;

Выбрать продавцов из Москвы:

Select имя_прод, город From Продавцы Where город=’Москва’;

Конец примера

Предикат, определяющий условия выбора, может содержать обычные операции отношения (<, <=, =, <>, >=, >), операцию betweenand (истина, когда первый операнд не меньше второго и не больше третьего) и логические операции (and, or, not). Для задания множества служат круглые скобки, ограничивающие его определение. Множество может определяться как простым перечислением элементов, так и запросом. Последний вариант будет рассматриваться позже. Для определения принадлежности элемента множеству служит операция in. Для символьных значений допускается выбор по маске. Символ «%» маскирует любую цепочку в искомой строке, символ «_» – лишь один символ, фраза like определяет маску.

Пример

Выбрать продавцов из Москвы, у которых комиссионные меньше 0,1:

Select Имя_прод, Комиссия From Продавцы

Where Город=’Москва’ and Комиссия<0,1;

Выбрать продавцов как из Москвы, так и из Тулы (два варианта):

Select * From Продавцы

Where Город=’Москва’ or Город=’Тула’;

Select * From Продавцы

Where Город in (’Москва’, ’Тула’);

Выбрать продавцов, у которых комиссионные в интервале от 0,1 до 0,12, причем, в первом случае интервалы включаются, во втором – нет:

Select * From Продавцы 

Where Комиссия between 0.1 and 0.12;

Select * From Продавцы 

Where Комиссия between 0.1 and 0.12 and not Комиссия in (0.1, 0.12);

Выбрать продавцов, у которых первая или вторая буква фамилии – «М»:

Select * From Продавцы

Where Имя_прод like ‘М%’ or Имя_прод like ‘_м%’;

Конец примера

Согласно требованиям к реляционным базам данных, атрибуты должны иметь возможность принимать пустое значение. В SQL оно обозначается как null. Пустое значение может принимать поле любого типа. Для проверки атрибута на пустоту служит операция is null. Сравнение с пустым значением неопределенно (unknown): a=null. Неопределенное значение возникает и в результате проверки предиката принадлежности: a in (null). Обычно неопределенное значение интерпретируется как ложь, но не всегда: not ложь – истина, а not unknown unknown.

Использование not в SQL более свободно, чем в обычных языках программирования: допустимо и (not a is null), и (a is not null), и (not a in (…)), и (a not in (…)).

Функции агрегирования

Функции агрегирования возвращают единственное (скалярное) значение для группы кортежей. Всего различают пять таких функций:

  •  COUNT – количество непустых строк или значений атрибутов, отличных от null, удовлетворяющих заданному условию;
  •  SUMсумма значений атрибута;
  •  AVG – среднее значение атрибута;
  •  MAX – максимальное значение атрибута;
  •  MIN – минимальное значение атрибута.

В команде Select они используются в списке выбираемых полей наряду с именами атрибутов. Их аргументы – имена атрибутов, причем, для SUM и AVG допустимы аргументы только числового типа.

Рассмотрим подробнее функцию COUNT. Она подсчитывает количество всех непустых атрибутов, даже если их значение повторяется. Для исключения повторений используется вариант Distinct. Вариант COUNT(*) подсчитывает количество строк в выборке, включая и пустые, и повторяющиеся. Применять Distinct здесь нельзя. Вариант All позволяет считать все непустые значения атрибута, включая повторяющиеся.

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

Пример

Подсчитать количество продавцов, которые выполняли заказы:

Select COUNT(Distinct ном_прод) From Заказы;

Подсчитать количество продавцов:

Select COUNT(*) From Продавцы;

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

Select COUNT(All сумма) From Заказы;

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

Select SUM(сумма/1000) From Заказы;

Конец примера

Группировка

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

Пример

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

Select MAX(сумма), ном_прод From Заказы

Group By ном_прод;


Сумма

Ном_прод

1900,1

14

5160,4

12

1098,1

17

1713,2

13

4723,0

11

Конец примера

Фраза Group By может содержать более одного атрибута, по которым группируются записи. В этом случае первый атрибут в списке определяет самую внешнюю группу, второй – группу внутри первой и т.п.

При работе с группами данных может возникнуть необходимость отбирать группы по какому-нибудь признаку, например, определить общие суммы заказов по дням и среди них отобрать те, которые превышают некоторое число. Если бы дело касалось записей, задача легко решалась бы фразой Where: Where сумма > . Но к группе она неприменима. Для отбора групп по некоторому признаку используется фраза Having.

Пример

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

Select дата, Sum(сумма) From Заказы 

Group By дата Having Sum(сумма)>5000;

Конец примера

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

Пример

Выбрать наибольшие заказы, выполняемые продавцами, номера которых 12 или17:

Select ном_прод, MAX(сумма) From Заказы 

Group By ном_прод Having ном_прод in (12, 17);

Конец примера

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

Select дата, MAX(SUM(сумма)) From Заказы Group By дата;

Group By предполагает, что групп будет столько, сколько различных дат. С другой стороны, SUM(сумма) применяется к каждой группе, а MAX(SUM(сумма)) для всех групп выработает единственное значение, что противоречит предыдущему утверждению.

Возможности форматирования

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

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

Пример

Select Имя_прод, город, Комиссия*100, ‘%’ From продавцы;

Имя_прод

Город

Иванов

Москва

12

%

Петров

Тула

13

%

Сидоров

Москва

11

%

Борисов

Киров

15

%

Титов

Пенза

10

%

Конец примера

Для упорядочивания записей в выборке используется фраза Order by, в которой, как и в случае группировки, задается список атрибутов. Процесс упорядочивания начинается с самого правого атрибута списка и заканчивается самым левым. Каждый атрибут может быть снабжен признаком Asc для возрастающего порядка или Desc для убывающего. По умолчанию записи упорядочиваются по возрастанию значения указанного атрибута. Атрибут из списка Order by должен быть указан в выборке. Вместо имени, в списке может быть задан номер атрибута из списка выбора, это важно, если столбец задан агрегатной функцией или вообще безымянный. Однако гораздо лучше переименовать выбираемые данные так, чтобы имена столбцов были понятными. Переименование выполняется конструкцией <выбираемое выражение> As <имя>.

Упорядочивание может сочетаться с группировкой, в этом случае Order by выполняется последним.

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

 Пример

Select ном_зак, сумма, дата From Заказы

Order By дата, сумма Desc ;

Ном_зак

Сумма

Дата

305

5160,4

03.10

302

1900,1

03.10

306

1098,1

03.10

303

767,2

03.10

301

18,7

03.10

309

1713,2

04.10

307

75,7

04.10

308

4723,0

05.10

311

3891,8

06.10

310

1309,9

06.10

Select ном_прод, MAX(сумма) As макс_сумма From Заказы

Group By ном_прод Order By ном_прод;


Ном_прод

макс_сумма

11

4723,0

12

5160,4

13

1713,2

14

1900,1

17

1098,1

Select Ном_прод, Max(сумма) From Заказы

Group By Ном_прод Order By 2 Decs;

Ном_прод

12

5160,4

11

4723,0

14

1900,1

13

1713,2

17

1098,1

Конец примера


Лекция 12

Язык структурных запросов SQL (продолжение)

Соединение

В SQL реализуются различные варианты эквисоединения. Известно, что с помощью переименования и эквисоединения можно реализовать естественное соединение. Но в SQL к переименованию прибегать не обязательно: допускается именование атрибута с указанием имени таблицы, к которой он относится. Таким образом, можно обеспечить уникальность имен даже в случае непустого пересечения схем соединяемых отношений. Соответствующая конструкция – <имя таблицы>.<имя атрибута>.

Остановимся на единственном варианте эквисоединения, отвечающем оператору реляционной алгебры, различные варианты Join рассматривать не будем. Напомним, что этот оператор записывается как r[A1 = B1, A2 = B2,…, Am = Bm]s, где r и s – соединяемые отношения, а A1, A2,…, Am и B1, B2,…, Bm – атрибуты, по равенству которых производится соединение. В SQL соответствующий оператор выглядит так:

Select <список атрибутов> From r, s

Where A1 = B1 and A2 = B2 and and Am = Bm;

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

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

Пример

Подобрать продавцов и покупателей, живущих в одном городе:

Select имя_пок, имя_прод, покупатели.город From Покупатели, Продавцы 

Where Покупатели.город=Продавцы.город;

Имя_пок

Имя_прод

Город

Комов

Иванов

Москва

Комов

Сидоров

Москва

Мохов

Петров

Тула

Глинка

Петров

Тула

Окулов

Иванов

Москва

Окулов

Сидоров

Москва

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

В следующем примере ном_пок в таблице Покупатели играет роль первичного (родительского) ключа, а в таблице Заказы – внешнего.

Select имя_пок, ном_зак From Покупатели, Заказы

Where Заказы.ном_пок=Покупатели.ном_пок;

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

Конец примера

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

Select <список атрибутов> From r пн1, s пн2 …

и

Select <список атрибутов> From r As пн1, s As пн2 …

Здесь пн1 и пн2 – псевдонимы таблиц r и s соответственно.

Пример

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

Select ном_зак, имя_пок From Заказы, Покупатели, Продавцы 

Where Заказы.ном_пок=Покупатели.ном_пок

and Заказы.ном_прод=Продавцы.ном_прод

and Покупатели.город<>Продавцы.город;

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

Select a.имя_пок As пок1, b. имя_пок As пок1, a.значимость 

From Покупатели a, Покупатели b

Where a.значимость=b.значимость;

пок1

пок2

Значимость

Комов

Окулов

100

Комов

Комов

100

Комов

Зимин

100

Окулов

Окулов

100

Окулов

Комов

100

Окулов

Зимин

100

Зимин

Зимин

100

Зимин

Окулов

100

Зимин

Комов

100

Емелин

Мохов

200

Емелин

Емелин

200

Мохов

Мохов

200

Мохов

Емелин

200

Попов

Попов

300

Попов

Глинка

300

Глинка

Попов

300

Глинка

Глинка

300

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

Select a.имя_пок, b.имя_пок, a.значимость From Покупатели a, Покупатели b

Where a.значимость=b.значимость;

and a.имя_пок < b.имя_пок;

пок1

пок2

Значимость

Комов

Окулов

100

Зимин

Окулов

100

Зимин

Комов

100

Емелин

Мохов

200

Глинка

Попов

300

Конец примера

Вложенные запросы

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

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

Пример

Найти все заказы, которые выполняет продавец Сидоров:

Select * From Заказы 

Where ном_прод=(Select * From Продавцы Where имя_прод=’Сидоров’);

Запрос корректен, если есть ровно один продавец Сидоров. Если такого нет – результат не определен, если их более одного – результат ошибочен.

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

Select * From Заказы 

Where сумма>(Select AVG(сумма) From Заказы Where дата=’04.10’);

Найти все заказы для продавцов из Москвы:

Select * From Заказы 

Where ном_прод in (Select ном_прод From Продавцы 

Where город=’Москва’);

Такой же результат можно получить, используя операцию соединения:

Select a.* From Заказы a, Продавцы b

Where a.ном_прод = b.ном_прод and город=’Москва’;

Найти комиссионные всех продавцов, обслуживающих покупателей из Москвы:

Select комиссия From Продавцы 

Where ном_прод in (Select ном_прод From Заказы

Where ном_пок in (Select ном_пок From Покупатели

Where город=’Москва’));

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

Select значимость, COUNT(Distinct ном_пок) From Покупатели

Having значимость > (Select AVG(значимость) From Покупатели

Where город=’Тула’);

Конец примера

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

Связанные запросы

Для реализации вложенного запроса может потребоваться информация из таблиц внешнего запроса. Запросы такого типа называются связанными.

Пример

Выбрать всех покупателей, которые сделали заказы 3 октября:

Select * From Покупатели a

Where ’03.10’ in (Select дата From Заказы b Where a.ном_пок=b.ном_пок);

Конец примера

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

  1.  Выбрать очередную строку внешней таблицы, от которой зависит внутренний подзапрос, она называется строкой-кандидатом.
  2.  Сохранить ее под псевдонимом, указанном во внешней фразе From.
  3.  Выполнить подзапрос. Используемые в подзапросе значения строки-кандидата называются внешними ссылками.
  4.  Оценить результат внешнего запроса на основании результата подзапроса.
  5.  Повторить процедуру для следующих строк внешней таблицы.

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

Пример

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

Select Distinct a.* From Покупатели a, Заказы b

Where a.ном_пок=b.ном_пок and дата=’03.10’;

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

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

Select ном_прод, имя_прод From Продавцы a

Where 1<(Select COUNT(Distinct ном_пок) From Заказы 

Where ном_прод=a.ном_прод);

Конец примера

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

Пример

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

Select * From Заказы a

Where сумма>(Select AVG(сумма) From Заказы b 

Where a.ном_пок=b.ном_пок);

Конец примера

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

Предикаты, определенные на подзапросах

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

Функция Exists истинна, если ее аргумент (подзапрос) содержит хотя бы один элемент, в противном случае она ложна. Легко видеть, что в подзапросе этой функции использование агрегатных функций бессмысленно. Рассмотрим применение функции Exists на примерах.

Пример

Выбрать всех покупателей из Тулы, если хотя бы один из них сделал заказ:

Select * From Покупатели Where город=’Тулаand

Exists(Select * From Заказы Where ном_пок in

 (Select ном_пок From Покупатели Where город=’Тула’));

Заметим, что здесь в подзапросе используется конструкция Select *… Использование ее в Exists – это единственный случай корректного употребления варианта «*» в подзапросе.

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

Select Distinct ном_прод From Заказы a Where

Exists(Select * From Заказы b Where a.ном_прод=b.ном_прод

and a.ном_пок<>b.ном_пок);

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

Select Distinct a.ном_прод, имя_прод From Заказы a, Продавцы c Where 

Exists(Select * From Заказы b 

Where a.ном_прод=b.ном_прод

and a.ном_пок<>b.ном_пок) and a.ном_прод=c.ном_прод;

Конец примера

Функция All истинна, если каждое значение ее аргумента (подзапроса) удовлетворяет условию, в которое она входит. Естественно, эта функция редко может применяться для операции равенства: в этом случае все элементы выборки должны быть равны между собой. Неравенство – более содержательная операция, она обозначает, что левая часть не равна ни одному из элементов выборки. Правда, этот предикат легко реализуется операцией in. Более интересны операции «больше», «меньше» и т.п. Рассмотрим применение функции All на примерах.

Пример

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

Select * From Покупатели Where значимость>

All(Select значимость From Покупатели Where город=’Тула’);

Этот же запрос можно сформулировать с Exists:

Select * From Покупатели a Where

not Exists(Select * From Покупатели b 

Where a.значимость<=b.значимость and b.город=’Тула’);

Конец примера

Функция Any (синоним – Some) истинна, если хотя бы одно значение ее аргумента (подзапроса) удовлетворяет условию, в которое она входит. Эта функция чаще используется для операции равенства, чем для «больше», «меньше» и т.п. Рассмотрим применение функции Any на примерах.

Пример

Выбрать всех покупателей, живущих в одном городе с продавцами:

Select * From Покупатели Where город= Any(Select город From Продавцы;

Этот же запрос можно сформулировать с in. С Exists этот запрос выглядит так:

Select * From Покупатели a Where

Exists(Select * From Продавцы b Where a.город=b.город);

Конец примера

Любой запрос как с Any, так и с All, может быть выражен через Exists, но в этом случае требуется более глубокая вложенность запросов и нередко встречаются связанные подзапросы.

Уточним, как ведут себя функции Any, All и Exists в особых случаях. Для пустой выборки All принимает значение истина, Any и Existsложь. При сравнении с null функции Any и All принимают неопределенное значение, Exists никогда неопределенное значение не принимает.

Объединение

Операция объединения реализуется фразой Union, которая объединяет два независимых подзапроса. Эта операция объединяет два множества в одно, значит, элементы исходных множеств должны быть однотипными. Понятно, что в каждом подзапросе должно быть одинаковое количество столбцов, и они должны быть сравнимы. С точки зрения стандарта ANSI сравнимость сводится к тому, чтобы тип и размер столбцов из каждой пары совпадали. Другое ограничение связано с допустимостью null-значений. Если они запрещены в одном подзапросе, они должны быть запрещены и в другом. Нельзя использовать Union в подзапросах, а в объединяемых выборках – агрегатные функции. В конкретных реализациях могут быть и другие ограничения.

При объединении из результата автоматически исключаются тождественные строки, в отличие от команды Select. Чтобы их оставить, следует использовать вариант Union All.

Для получения требуемого порядка строк в выборке используют, как обычно, фразу Order By, она ставится единственный раз, причем, в конце.

Пример

Выбрать номера покупателей, значимость которых выше 200 или которые сделали заказ на сумму более 3000:

Select ном_пок From Покупатели Where значимость>200