Шехтман В.Е. Базы данных, SQL и все такое. Курс лекций

Подождите немного. Документ загружается.

ЗАГОЛОВКИ_ПРИЕМ_АКТ, СОДЕРЖАНИЕ_ПРИЕМ_АКТ, ОСТАТКИ и т. д. В этих

именованных блоках данных действительно содержится информация об объектах

рассматриваемой предметной области и их взаимосвязях: поставщиках, товарах,

остатках на складе и т. д.

Логическая структура БД – определение БД, не зависящее от физической организации.

Выше мы дали именно логическое определение данных для торговой фирмы, т. к. нигде не

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

Банк данных – система специально организованных баз данных, программных,

технических, организационно-методических средств для централизованного

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

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

создания и использования БД пользователями. При этом должны быть выполнены

перечисленные выше требования.

Запрос – процесс обращения пользователя к БД с целью ввода, чтения или изменения

информации в БД.

С момента зарождения дисциплины баз данных было разработано несколько

способов их физической организации. На раннем этапе наибольшее распространение

получили системы, основанные на файлах.

1.3 Файлы операционной системы

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

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

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

зрения операционной системы проста: это последовательность записей, содержащих

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

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

модули. С точки зрения файловой системы объектные файлы также обладают очень

простой структурой – последовательность записей или байтов. Система

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

этой системы структуру объектного модуля. При этом логическая структура

объектного модуля неизвестна файловой системе, эта структура поддерживается

системой программирования. Тоже можно сказать и о файлах – образах выполняемых

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

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

системы. Та же ситуация с файлами, содержащими графическую и звуковую

информацию.

Итак, файловые системы обычно обеспечивают хранение слабо

структурированной информации, оставляя структуризацию прикладным программам.

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

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

стандартные и сравнительно дешевые средства файловой системы, можно реализовать

те структуры хранения, которые наиболее соответствуют специфике данной

прикладной области. Однако ситуация коренным образом отличается для

информационных систем второй сферы применения вычислительной техники. Эти

системы главным образом ориентированы на хранение, выбор и модификацию

постоянно существующей информации. Структура информации зачастую очень

сложна, и хотя структуры данных различны в разных информационных системах,

между ними много общего.

Таким образом, СУБД решают множество проблем, которые затруднительно или

вообще невозможно решить при использовании файловых систем. При этом

существуют

 приложения, для которых вполне достаточно файлов;

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

данными во внешней памяти для них требуется;

 приложения, для которых нужны базы данных.

Для дальнейшего нам потребуется определение: модель данных – система

описания структур данных, операций по их обработке и ограничений целостности. С

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

установленные между ними.

Рассмотрим основные модели данных, которые в разное время служили основой

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

последовательностью.

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

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

иерархическую структуру — перевернутый граф (дерево). К основным понятиям

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

называют совокупность атрибутов данных, описывающих некоторый объект. Каждый

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

и с нулем) узлов нижнего уровня. Исключением является узел самого высокого уровня,

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

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

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

каждой записи базы данных существует единственный путь от корневой записи.

Примером иерархической модели данных может служить адрес. Действительно, на

первом уровне (в корне дерева) лежит страна, на втором – регион, на третьем – город,

на четвертом – улица, дом и квартира. Один и тот же город не может принадлежать

двум странам или регионам. Другим примером иерархической модели является

пространство доменных имен интернета – система DNS. Пример иерархической

структуры данных представлен на рисунке 1.2.

Организация

Отдел 2

Сотрудник

Сектор

Сотрудник

Отдел 3

Отдел 1

Рисунок 1.2 – Иерархическая модель данных. Структура организации

1.5 Сетевая модель данных

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

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

отличием сетевой модели данных является то, что узел может быть связан с любым

другим узлом, в том числе лежащим на уровне, не связанном непосредственно с

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

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

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

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

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

представлена на рисунке 1.3.

Сотрудник

Проект 1

Проект 3

Проект 2

Рисунок 1.3 – Сетевая модель данных. Принадлежность сотрудников проектам

Общим для иерархической и сетевой моделей данных является способ их

физической реализации: для указания узлов, связанных с некоторым узлом, приходится

в явной форме использовать физические адреса. Физический адрес – это адрес ячейки

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

данных возникает необходимость хранения и поддержки информации, не относящейся

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

Иерархическая и сетевая модели данных обладают определенными

недостатками, затрудняющими обработку и доступ к данным, основными из которых

являются следующие:

 высокая логическая сложность работы с данными;

 зависимость приложений от физической реализации базы данных;

 наличие только навигационного метода доступа к данным. Это означает,

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

организовывать в программе перебор запись за записью – нельзя

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

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

С течением времени упомянутые способы организации данных уступили своѐ

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

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

В основе реляционной модели данных лежит идея о том, что любой набор

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

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

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

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

Реляционная модель данных отличается простотой структуры данных, удобным

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

формального аппарата алгебры отношений (реляционного исчисления) для обработки

данных.

Датой рождения реляционной теории баз данных принято считать 6 июня 1970

года, когда сотрудник фирмы IBM, доктор Э. Кодд, опубликовал статью "Реляционная

модель данных для больших коллективных банков". Именно в этой статье впервые

встретился термин "реляционная модель данных".

После публикации статьи доктор Э. Кодд продолжил работу по развитию

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

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

данных аппарат теории множеств, а конкретно — объединение, пересечение, разность,

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

представлен в виде простых двумерных таблиц, называемых в математике

―отношением‖ (relation). От этого слова и произошло название "реляционная модель

данных". Разработанная Коддом теория реляционных баз данных описывает правила

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

Теоретической основой реляционной модели является теория отношений,

основу которой заложили американец Ч. С. Пирс и немец Э. Шредер в конце XIX века.

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

некоторых специальных операций, т. е. образует с этими операциями абстрактную

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

данными в реляционной модели.

2 Введение в реляционную модель данных

Основной структурой данных в рассматриваемой модели является отношение

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

можно проиллюстрировать с помощью таблицы 2.1, на которой представлено

отношение R.

Таблица 2.1 – Иллюстрация понятия отношения

Домен A Домен B Домен C …

Кортеж 1

Кортеж 2

…

Вхождение кортежа со значениями атрибутов A, B, C означает, что верен

предикат (логическое высказывание) R(A1, B1, C1): R(A1, B1, C1) = True. Также

R(A1, B1, C1) = True, но R(A1, B2, C2) = False, т. к. в отношении R нет кортежа со

значениями атрибутов A1, B2, C2.

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

данных, в том числе данные, хранящиеся в сетевых и иерархических базах данных и

взаимосвязи между ними.

Отношение и есть ―реляционная структура‖. N-арное отношение – это

подмножество декартова произведения D

D

…D

множеств D

, D

, …, D

(n>=1),

…

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

называют доменами. Отношение моделирует реальную ситуацию и содержит только

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

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

Пример:

Рассмотрим отношение R, хранящее информацию о религиях и их основателях.

Оно образовано доменами ―Основатели мировых религий‖ и ―Мировые религии‖ (см.

таблицу 2.2)

Таблица 2.2 – Отношение R

Основатели мировых религий

Мировые религии

Будда

Буддизм

Христос

Христианство

Магомет

Мусульманство

Это отношение не включает никаких других кортежей, так, например предикат

R(Магомет, Буддизм)

неверен и, следовательно, такого кортежа в отношении быть не должно.



Столбец отношения содержит подмножество домена и называется атрибутом

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

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

отношения имеет уникальное имя. (Кстати, факт отсутствия одинаковых строк

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

разговор о которой впереди). Заметим, что порядок строк в отношении произвольный.

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

отношение – это двумерный массив со следующими свойствами:

1. Каждый элемент отношения является минимальным элементом данных,

неразложимым на составные части (для обозначения этого свойства применяют

термин ―атомарность‖).

2. Элементы в столбце имеют один тип (термин ―домен‖ можно определить как

множество атомарных значений одного типа).

3. Каждый столбец имеет уникальное имя.

4. В отношении нет совпадающих строк.

5. Порядок следования строк и столбцов в отношении не определен.

Ввиду того что терминология не устоялась, и, более того, в разных областях

применяют для обозначения одних и тех же понятий разные термины, приведем

словарь этих терминов (таблица 2.3).

Таблица 2.3 – Соответствие терминов

Реляционная

теория

Практика

реляционных баз

данных

СУБД

Отношение

Сущность

Таблица

Кортеж

Запись

Строка

Атрибут

Поле

Колонка, столбец

Пример:

Рассмотрим отношение, хранящее сведения о поставках товаров (таблица 2.4).

Таблица 2.4 – Отношение Поставки

Продукт

Поставщик

Цена за ящик

Бананы

Глобус

150

Помидоры

Глобус

230

Лук

Плодовощторг

Домен поставщиков включает имена фирм: ―Глобус‖, ―Плодовощторг‖,

―Центрпродсервис‖. Ясно, что в него могут входить и имена других фирм, кроме тех,

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

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

Домен поставщиков и домен продуктов содержат данные одного типа

(строкового), но имеют разный смысл. В домене данные должны быть сравнимы.

Домен атрибута – множество всех возможных значений атрибута. Так, домен

поставщиков – все возможные поставщики, все они не обязаны содержаться в нашем

отношении.



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

количество кортежей в нем.

Реляционная база данных – совокупность отношений (relations) (набор

двумерных таблиц) и связей между ними. Таблицы в базе данных связаны различными

отношениями (relationships) (обратите внимание: из-за перевода двух разных

английских слов одним русским словом возможны недоразумения! Поэтому лучше

вместо ―отношения между отношениями‖ говорить ―связи между отношениями‖, хотя

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

Если два отношения отличаются только порядком строк или столбцов, то они

считаются одинаковыми.

Отношение – динамическая модель реального объекта. Экземпляр отношения –

реализация отношения в текущий момент времени. Схема S

отношения R – перечень

имен атрибутов отношения с указанием домена, к которому они относятся:

= (A

, A

, …), A

 D

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

Если атрибуты принимают значения из одного домена, то говорят, что они Θ-

сравнимы. Например, если домен содержит числа, то Θ есть множество [=, <>, >=, <=,

<, >]. Домен может содержать символьные данные. Для такого домена изначально

определены только операции = и <>. Однако если иметь в виду лексикографическое

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

Схема S

отношения R эквивалентна схеме S

отношения R1 если R и R1 имеют

одинаковую степень и возможно упорядочивание имен атрибутов в S такое, что на

одинаковых местах находятся сравнимые атрибуты (т.е. атрибуты из одного домена):

= (A

, …, A

)

= (B

, …, B

)

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

~ S

 n=m, A

, B

из D

Реляционная модель предполагает наличие множества взаимосвязанных

отношений. Связи между отношениями поддерживаются неявно (в отличие от сетевой

и иерархической моделей). Как и какие связи поддерживаются? В реляционной модел,

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

отношениями. Одно отношение в связи выступает основным, другое подчиненным. Это

означает, что один кортеж основного отношения соответствует нескольким кортежам

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

наборы атрибутов, по которым они связаны.

Чтобы обеспечить эффективный доступ к данным, непротиворечивость и

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

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

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

Множество атрибутов составляют возможный ключ (иначе говорят

потенциальный ключ или ключ-кандидат), если обеспечивается следующее:

1. Уникальность. Никакие два кортежа не могут иметь одинаковых значений для

всех атрибутов, входящих в ключ.

2. Минимальность. Ни один из атрибутов не может быть исключен из ключа без

нарушения уникальности ключа.

Один из возможных ключей объявляют первичным (PRIMARY KEY). Этот ключ

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

кортежа одного отношения с несколькими кортежами другого (подчиненного)

отношения, в подчиненное отношение включают тот же набор атрибутов, что составил

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

атрибутов – вторичный ключ (FOREIGN KEY). Вторичный ключ определяет не один

кортеж, а множество кортежей подчиненного отношения, соответствующих одному

кортежу основного отношения.

Пример:

Отношение Налогоплательщик имеет схему S

Налогоплательщик

=(ИНН, ФИО).

Отношение Доходы имеет схему S

Доходы

=(ИНН, Сумма дохода, Источник

получения).

У одного налогоплательщика может быть несколько источников поступления

доходов. Поэтому надо связать одну запись о налогоплательщике (основное

отношение) с несколькими записями о доходах (вспомогательное отношение).

Первичный ключ отношения Налогоплательщик – атрибут ИНН. Вторичный

ключ отношения Доходы – атрибут ИНН. Оба отношения связаны между собой общим

атрибутом ИНН.



Механизм реальных СУБД обеспечивает уникальность ключа, но

минимальность ―лежит на совести‖ программиста. Любое отношение содержит, по

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

отношения).

3 Реляционная алгебра

Вспомним некоторые определения из курса дискретной математики. Пусть М –

некоторое множество элементов. Предикат (логическое высказывание) – это функция b

= f(x

, …, x

), где x

 M, b  {True, False}, m:=1,…,m. Модель – это множество

элементов M с заданными над элементами предикатами. Операция p: y = p(x

, …, x

);

y, x

 M, i:=1,…,n. Алгебра (абстрактная) – это модель с конечным множеством

операций.

Иными словами, алгебра – это множество объектов из основного множества M c

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

(основного) множества M. Основное множество в реляционной алгебре – это

множество отношений. Кодд определил семь базовых операций и одну

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

операции могут быть определены через другие операции.

Теоретико-множественные операции являются основными, их всего четыре.

Остальные называются специальными.

Для иллюстрации дальнейшего материала введем в рассмотрение два отношения

с одинаковыми схемами, интерпретируемых как множество товаров, имеющихся в

наличии в двух разных магазинах (таблиц 3.1).

Таблица 3.1 – Отношения Маг1, Маг2

Шифр товара

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

товара

Отношение Маг1

Ф1

Бананы

Ф2

Арбузы

Ф3

Авокадо

Ф4

Яблоки

Ф5

Помидоры

Ф6

Фейхоа

Отношение Маг2

Ф1

Бананы

Ф7

Груши

Ф2

Арбузы

Ф6

Фейхоа

3.1 Теоретико-множественные операции

3.1.1 Объединение отношений R1 и R2 (записывается как R1  R2) – это

отношение R3 с той же схемой что и исходные отношения R1 и R2, {r|r  R1  r  R2},

содержащее множество кортежей, принадлежащих R1 или R2 или и R1 и R2.  –

логическое сложение (ИЛИ).

Рисунок 3.1 – Графическая иллюстрация операции Объединение

Для введенных выше отношений выполним операцию Маг1  Маг2. Еѐ результатом

является отношение, приведенное в таблице 3.2 .

Таблица 3.2 – Результат операции объединения

Шифр товара

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

товара

Ф1

Бананы

Ф2

Арбузы

Ф3

Авокадо

Ф7

Груши

Ф4

Яблоки

Ф5

Помидоры

Ф6

Фейхоа

3.1.2 Пересечение отношений R1 и R2 (записывается R1  R2) – это отношение

R3 с той же схемой, что и отношения R1 и R2, {r|r  R1  r  R2} содержащее

множество кортежей, принадлежащих и R1 и R2.  – обозначение операции

логического умножения (И).

Рисунок 3.2 – Графическая иллюстрация операции Пересечение

Для Маг1  Маг2 результатом является отношение, представленное в таблице 3.3 .

Таблица 3.3 – Результат операции пересечения

Шифр товара

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

товара

Ф1

Бананы

Ф2

Арбузы

Ф6

Фейхоа

3.1.3 Разность отношений R1 и R2 (записывается R1 \ R2) – это отношение R3 с

той же схемой, что и отношения R1 и R2, {r| r  R1  r not  R2} содержащее

множество кортежей, принадлежащих R1, но не принадлежащих R2.

Рисунок 3.3 – Графическая иллюстрация операции Разность

Результаты применения этой операции приведены в таблицах 3.4 и 3.5 .

Таблица 3.4 – Результат операции Маг1 \ Маг2

Шифр товара

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

товара

Ф3

Авокадо