UNION|INТERSECT|MINUS|TIМES|JOIN|DIVIDEBY

Базы данных

Основные понятия и определения

Термин «база данных» (database) был введен в обиход в области вычислительной техники примерно в 1962 году. Этот термин страдает от обилия различных интерпретаций, например,

· «База данных - это самодокументированное собрание интегрированных данных».

· «База данных - это централизованное хранилище данных, обеспечивающее хранение, доступ, первичную обработку и поиск информации».

· «База данных – это совокупность связанных данных, организованных по определенным правилам, предусматривающим общие принципы описания, хранения и манипулирования, независимая от прикладных программ».

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

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

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

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

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

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

Целостность данных. В общем случае целостность данных означает корректность данных и их непротиворечивость. Для обеспечения целостности накладывают ограничения целостности. В частности, эти ограничения могут иметь вид логических выражений, значения которых всегда должны быть «истина». Если значение хотя бы одного логического выражения ограничения целостности данных принимает значение «ложь», то имеет место быть нарушение целостности данных. Ограничения такого вида иногда называют бизнес-правилами. Примеры ограничений: вес детали должен быть положительным; цвет детали должен быть «Красный», «Синий» или «Зеленый»; возраст родителей не может быть меньше возраста их биологического ребенка.

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

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

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

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

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

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

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

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

Масштабируемость.

Производительность.

К основным функциям СУБД относятся:

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

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

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

· Реализация поддержки языка описания данных и языка запросов к данным.

· Обеспечение безопасности данных.

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

Обычно современная СУБД содержит следующие компоненты:

· ядро, которое отвечает за управление данными во внешней и оперативной памяти и журналирование,

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

· подсистему поддержки времени исполнения, которая интерпретирует программы манипуляции данными, создающие пользовательский интерфейс с СУБД,

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

Классификация СУБД по типу модели данных:

· Дореляционные

o Инвертированные списки (файлы)

o Иерархичекие

o Сетевые

· Реляционные

· Постреляционные

o Объектно-реляционные

o Объектно-ориентированные

o Многомерные

o Прочие (NoSQL)

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

Основоположником теории реляционных баз данных является британский учёный Эдгар Кодд, который в 1970 году опубликовал первую работу по реляционной модели данных. Наиболее распространенная трактовка реляционной модели данных принадлежит Кристоферу Дейту. Согласно Дейту, реляционная модель состоит из трех частей: структурной, целостностной и манипуляционной.

Структурная часть реляционной модели описывает, из каких объектов состоит реляционная модель. Постулируется, что основной структурой данных, используемой в реляционной модели, являются нормализованные «n-арные» отношения. Основными понятиями структурной части реляционной модели являются тип данных, домен, атрибут, схема отношения, схема базы данных, кортеж, отношение, потенциальный, первичный и альтернативные ключи, реляционная база данных.

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

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

· домен имеет уникальное имя (в пределах базы данных),

· домен определен на некотором типе данных или на другом домене,

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

· домен несет определенную смысловую нагрузку.

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

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

Атрибут отношения – это пара вида <имя_атрибута, имя_домена >. Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов.

Схема отношения – это именованное множество упорядоченных пар <имя_атрибута, имя_домена>. Степенью или «арностью» схемы отношения является мощность этого множества. Схема базы данных в реляционной модели – это множество именованных схем отношений. Понятие схемы отношения близко к понятию структурного типа в языках программирования (например, record в языке Pascal или struct в языке C).

Кортеж, соответствующий данной схеме отношения, – это множество упорядоченных пар <имя_атрибута, значение_атрибута>, которое содержит одно вхождение каждого имени атрибута, принадлежащего схеме отношения. Значение атрибута должно быть допустимым значением домена, на котором определен данный атрибут. Степень или «арность» кортежа совпадает с «арностью» соответствующей схемы отношения.

Отношение, определенное на множестве из n доменов (не обязательно различных), содержит две части: заголовок (схему отношения) и тело (множество из m кортежей). Значения n и m называются соответственно степенью и кардинальностью отношения. Отношения обладают следующими свойствами.

· В отношении нет одинаковых кортежей. Действительно, тело отношения есть множество кортежей и, как всякое множество, не может содержать неразличимые элементы.

· Кортежи не упорядочены (сверху вниз). Причина следующая – тело отношения есть множество, а множество не упорядочено.

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

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

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

В реляционной модели каждый кортеж любого отношения должен отличатся от любого другого кортежа этого отношения (т.е. любое отношение должно обладать уникальнымключом).

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

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

Реляционная база данных – это набор отношений, имена которых совпадают с именами схем отношений в схеме базы данных.

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

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

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

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

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

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

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

Внешний ключ в отношении R2 – это непустое подмножество множества атрибутов FK этого отношения, такое, что: a) существует отношение R1 (причем отношения R1 и R2 необязательно различны) с потенциальным ключом CK; b) каждое значение внешнего ключа FK в текущем значении отношения R2 обязательно совпадает со значением ключа CK некоторого кортежа в текущем значении отношения R1.

Требование ссылочной целостности состоит в следующем:

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

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

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

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

1) Традиционные операции над множествами: объединение (UNION), пересечение (INTERSECT), разность (MINUS) и декартово произведение (TIMES). Все операции модифицированы, с учетом того, что их операндами являются отношения, а не произвольные множества.

2) Специальные реляционные операции: ограничение (WHERE), проекция (PROJECT), соединение (JOIN) и деление (DIVIDE BY).

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

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

реляционное_выражение::=

унарное_выражение | бинарное_выражение

унарное_выражение::=

переименование | ограничение | проекция

переименование::=

терм RENAME имя_атрибута AS имя_атрибута

терм::=

имя_отношения | (реляционное_выражение)

ограничение::=

терм WHERE логическое_выражение

проекция::=

терм | терм [ список_имен_атрибутов ]

бинарное_выражение::=

проекция бинарная_операция реляционное_выражение

бинарная_операция:: =

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

1) Реляционные операторы UNION, INTERSECT и MINUS требуют, чтобы отношения были совместимыми по типу, т. е. имели идентичные заголовки.

2) Легко проверить, что операторы UNION, INTERSECT, TIMES и JOIN ассоциативны и коммутативны.

3) Если отношения A и B не имеют общих атрибутов, то операция соединения A JOIN B эквивалентна операции A TIMES B, т. е. в таком случае соединение вырождается в декартово произведение. Такое соединение называют естественным.

4) Другой допустимый синтаксис для синтаксической категории переименования таков:

(терм RENAМE список-переименований). Здесь каждый из элементов списка переименований представляет собой выражение имя_атрибута AS имя_атрибута.

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

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

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

A JOIN B = ((A TIMES (B RENAME Y AS Y1)) WHERE Y=Y1)[X, Y, Z]

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

A INTERSECT B = A MINUS (A MINUS B)

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

A DIVIDEBY B = A[X] MINUS ((A[X] TIMES B) MINUS A)[X]

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

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

S(Sno: integer, Sname: string, Status: integer, City: string)

P(Pno: integer, Pname: string, Color: string, Weight: real, City: string)

SP(Sno: integer, Pno: integer, Qty: integer)

В данном примере имена доменов представлены именами типов, имена типов отделяются от имен атрибутов двоеточием, первичные ключи выделены подчеркиванием, а имена внешних ключей схемы отношения SP (ПОСТАВКА) совпадают с именами первичных ключей схем отношений S (ПОСТАВЩИК) и P (ДЕТАЛЬ).

1) Получить имена поставщиков, которые поставляют деталь под номером 2.

((SP JOIN S) WНEPE Рno = 2) [ Sname ]

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

(((Р WНERE Color = 'Красный') JOIN SP) [ Sno ] JOIN S) [ Sname ]

Другая формулировка того же запроса:

(((Р WНERE Color = 'Красный') [ Рno ] JOIN SP) JOIN S) [ Sname ]

Этот пример подчеркивает одно важное обстоятельство: возможность сформулировать один и тот же запрос несколькими способами.

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

((SP [ Sno, Рno] DIVIDE BY Р [ Рno ] JOIN S) [ Sname ]

4) Получить номера поставщиков, поставляющих по крайней мере все те детали, которые поставляет поставщик под номером 2.

SP [ Sno, Рno ] DIVIDE ВY (SP WНEPE Sno = 2) [ Рno ]

5) Получить все пары номеров поставщиков, размещенных в одном городе

(((S RENAМE Sno AS FirstSno) [ FirstSno, City ] JOIN

(S RENAМE Sno AS SecondSno) [ SecondSno, City ])

WНEPE FirstSno < SecondSno) [ FirstSno, SecondSno ]

6) Получить имена поставщиков, которые не поставляют деталь под номером 2.

((S[ Sno ] MINUS (SP WНEPE Рno = 2) [ Sno ]) JOIN S) [Sname]

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

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

Упрощенный синтаксис выражений исчисления кортежей в форме БНФ имеет вид.

объявление-кортежной-переменной::=

RANGE OF переменная IS список-областей

область::=

отношение |

реляционное-выражение

реляционное-выражение::=

(список-целевых-элементов)[ WHERE wff ]

целевой-элемент::=

переменная |

переменная.атрибут [ AS атрибут ]

wff::=

условие |

NOT wff |

условие AND wff |

условие OR wff |

IF условие THEN wff |

EXISTS переменная (wff) |

FORALL переменная (wff) |

(wff)

условие::=

(wff) |

компаранд операция-отношения компаранд

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

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

2) Категории отношение, атрибут и переменная – это идентификаторы (т. е. имена).

3) Реляционное выражение содержит заключенный в скобки список целевых элементов и выражение WHERE, содержащее формулу wff («правильно построенную формулу»). Такая формула wff составляется из кванторов (EXISTS и FORALL), свободных и связанных переменных, констант, операторов сравнения, логических (булевых) операторов и скобок. Каждая свободная переменная, которая встречается в формуле wff, должна быть также перечислена в списке целевых элементов.

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

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

RANGE OF T IS R1, R2,..., Rn

Тогда отношения R1, R2,..., Rn должны быть совместимы по типу т. е. они должны иметь идентичные заголовки, и кортежная переменная T изменяется на объединении этих отношений, т. е. её значение в любое заданное время будет некоторым текущим кортежем, по крайней мере одного из этих отношений.

Примеры объявлений кортежных переменных.

RANGE OF SX IS S

RANGE OF SPX IS SP

RANGE OF SY IS

(SX) WHERE SX.City = 'Смоленск',

(SX) WHERE EXISTS SPX (SPX.Sno = SX.Sno AND SPX.Pno = 1)

Здесь переменная кортежа SY может принимать значения из множества кортежей S для поставщиков, которые или размещены в Смоленске, или поставляют деталь под номером 1, или и то и другое.

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

1) Получить имена поставщиков, которые поставляют деталь под номером 2.

SX.Sname WНERE EXISTS SPX (SPX.Sno = SX.Sno AND SPX.Pno = 2)

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

SX.Sname WНERE EXISTS SPX (SX.Sno = SPX.Sno AND

EXISTS РХ (РХ.Рno = SPX.Рno AND PX.Color = 'Красный'))

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

SX.Sname WНERE FORALL РХ (EXISTS SPX (SPX.Sno = SX.Sno AND SPX.Pno = РХ.Рno))

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

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