Характеристика современных автоматизированных информационных систем
.pdfЛевым внешним соединением называется соединение, при котором кортежи отношения R, не имеющие совпадающих значений в общих столбцах отношения S, также включаются в результирующее отношение.
Для обозначения отсутствующих значений во втором отношении используется определитель NULL. Внешнее соединение становится все более распространенным в РСУБД, к тому же в настоящее время оно является оператором, включенным в новый стандарт SQL. Преимуществом внешнего соединения является то, что при таком соединении сохраняется исходная информация, т.е. внешнее соединение сохраняет кортежи, которые были бы утрачены при использовании других типов соединений.
Аналогично строится правое внешнее соединение, в результирующем отношении которого содержатся все кортежи правого отношения. Кроме того, существует и полное внешнее соединение, в результирующее отношение которого помещаются все кортежи из обоих отношений и в котором для обозначения несовпадающих значений кортежей используются определители
NULL.
• Полусоединение (semi-join). Операция полусоединения определяет отношение, которое содержит те кортежи отношения R, которые входят в соединение отношений R и S.
Преимущество полусоединения заключается в том, что оно позволяет сократить количество кортежей, которые нужно обработать для получения соединения. Это особенно полезно при вычислении соединений в распределенных системах.
Оператор деления. Оператор деления может быть полезен в случае запросов особого типа, которые довольно часто встречаются в приложениях баз данных. Предположим, что отношение R определено на множестве атрибутов А, а отношение S – на множестве атрибутов В, причем В А (т.е. В является подмножеством А). Пусть С = А – В, т.е. С является множеством атрибутов отношения R, которые не являются атрибутами отношения S. Результатом оператора деления является набор кортежей отношения R, определенных на множестве атрибутов С, которые соответствуют комбинации всех кортежей отношения S.
Реляционная модель данных. Как уже говорилось, наиболее популярны реляционные модели данных. В соответствии с реляционной моделью данных данные представляются в виде совокупности таблиц, над которыми могут выполняться операции, формулируемые в терминах реляционной алгебры или реляционного исчисления.
В отличие от иерархических и сетевых моделей данных в реляционной модели операции над объектами имеют теоретико-множественный характер. Это дает возможность пользователям формулировать их запросы более компактно, в терминах более крупных агрегатов данных.
Основные понятия реляционных баз данных.
Необходимо иметь возможность уникальной идентификации каждого отдельного кортежа отношения по значениям его атрибутов.
Суперключ – атрибут или множество атрибутов, которое единственным образом (superkey) идентифицирует кортеж данного отношения.
Поскольку суперключ может содержать дополнительные атрибуты, которые необязательны для уникальной идентификации кортежа, нас будут интересовать суперключи, состоящие только из тех атрибутов, которые действительно необходимы для уникальной идентификации кортежей.
Потенциальный ключ – суперключ, который не содержит подмножества, также являющегося суперключом данного отношения.
Потенциальный ключ К для данного отношения R обладает двумя свойствами:
•уникальность. В каждом кортеже отношения R значение ключа К единственным образом идентифицируют этот кортеж;
•неприводимость. Никакое допустимое подмножество ключа К не обладает свойством уникальности.
Отношение может иметь несколько потенциальных ключей. Если ключ состоит из нескольких атрибутов, то он называется составным ключом. Рассмотрим отношение Branch. Конкретное значение атрибута City может определять сразу несколько отделений компании (например, в Москве может находиться два отделения). Поэтому данный атрибут не может быть выбран в качестве потенциального ключа. Однако, поскольку для каждого отделения компании задается его уникальный номер, каждое значение этого номера (атрибут Вnо) может определять не больше одного кортежа, а потому Вnо является потенциальным ключом. Аналогично, атрибуты Tel_No и Fax_No также являются потенциальными ключами этого отношения.
Первичный ключ – это потенциальный ключ, который выбран для уникальной идентификации кортежей внутри отношения.
Поскольку отношение не содержит кортежей-дубликатов, всегда можно уникальным образом идентифицировать каждую его строку. Это значит, что отношение всегда имеет первичный ключ. В худшем случае все множество атрибутов может использоваться как первичный ключ, но обычно, чтобы различить кортежи, достаточно использовать несколько меньшее подмножество атрибутов. Потенциальные ключи, которые не выбраны в качестве первичного ключа, называются альтернативными ключами. Если в отношении Branch выбрать в качестве первичного ключа атрибут Bno, то альтернативными ключами этого отношения будут атрибуты Tel_No и Fax_No.
Внешний ключ – это атрибут или множество атрибутов внутри отношения, которое соответствует потенциальному ключу некоторого (может быть, того же самого) отношения.
Если некий атрибут присутствует в нескольких отношениях, то его наличие обычно отражает определенную связь между кортежами этих отношений. Например, атрибут Вnо намеренно включен в отношенияBranch и Staff для установления связи между сведениями об отделениях компании и сведениями о сотрудниках, которые работают в каждом из отделений. В отношении Branch атрибут Вnо является первичным ключом, а в отношении Staff он введен для установления соответствия между сведениями о сотрудниках и сведениями о тех отделениях компании, в которых они работают. В отношении Staff атрибут Вno является внешним ключом. В таком случае говорят, что атрибут Вnо в отношении Staff ссылается на первичный ключ, т.е. на атрибут Вnо в базовом отношении Branch. Эти общие атрибуты играют важную роль в манипулировании данными.
Нормализация реляционной модели данных
Нормализация – это формальный метод анализа отношений на основе их первичного ключа (или потенциальных ключей, как в случае нормальной формы Бойса–Кодда) и существующих функциональных зависимостей. Он включает ряд правил, которые могут использоваться для проверки отдельных отношений таким образом, чтобы вся база данных могла быть нормализована до желаемой степени нормализации. Если некоторое требование не удовлетворяется, то нарушающее данное требование отношение должно быть декомпозировано на отношения, каждое из которых (в отдельности) удовлетворяет всем требованиям нормализации.
Зачастую нормализация осуществляется в несколько последовательно выполняющихся этапов, каждый из которых соответствует некоторой нормальной форме, обладающей известными свойствами. В ходе нормализации формат отношений становится все более строгим и менее уязвимым по отношению к аномалиям обновления. При работе с реляционной моделью данных важно понимать, что только удовлетворение требований первой нормальной формы (1НФ) обязательно для создания отношений приемлемого качества. Все остальные формы могут использоваться по желанию проектировщиков. Однако нормализацию рекомендуется выполнять как минимум до ЗНФ.
На рис. 12 показана схема процесса нормализации и продемонстрирована взаимосвязь между разными нормальными формами. Видно, что одни 1НФотношения могут находиться во 2НФ, другие 2НФ-отношения – в ЗНФ и т.д.
Покажем процесс нормализации на примере преобразования данных, которые в исходном состоянии имели табличный формат со строками и столбцами.
Первая нормальная форма (1 НФ). Перед обсуждением первой нормальной формы целесообразно предварительно дать определение того состояния, которое предшествует ей.
Рис. 12. Схема взаимосвязей между отдельными нормальными формами
Ненормализованная форма – таблица, содержащая одну или несколько повторяющихся групп данных
Первая нормальная форма (1НФ) – отношение, в котором на пересечении каждой строки и каждого столбца содержится только одно значение.
Процесс нормализации начинается с преобразования данных из формата источника (например, из формата стандартной формы ввода данных) в формат таблицы со строками и столбцами. На исходном этапе таблица находится в ненормализованной форме (ННФ) и часто называется ненормализованной таблицей. Для преобразования ненормализованной таблицы в первую нормальную форму (1НФ) в исходной таблице следует найти и устранить все повторяющиеся группы данных. Повторяющейся группой называется группа, состоящая из одного и более атрибутов таблицы, в которой возможно наличие нескольких значений для единственного значения ключевого атрибута таблицы. Обратите внимание на то, что в данном контексте термин “ключ” равным образом относится и к одному атрибуту, и к группе атрибутов, которые единственным образом идентифицируют каждую строку ненормализованной таблицы. Существует два подхода исключения повторяющихся групп из ненормализованных таблиц.
В первом подходе повторяющиеся группы устраняются путем ввода соответствующих данных в пустые столбцы строк с повторяющимися данными. Иначе говоря, пустые места при этом заполняются дубликатами неповторяющихся данных. Этот подход часто называют “выравниванием” (“flattening”) таблицы. Полученная в результате этих действий таблица, которая теперь будет называться отношением, содержит атомарные (или единственные) значения на пересечении каждой строки с каждымстолбцом, а потому находится в первой нормальной форме. В результате такого подхода в полученное отношение вносится некоторая избыточность данных, которая в ходе дальнейшей нормализации будет устранена.
Во втором подходе один атрибут или группа атрибутов назначаются ключом ненормализованной таблицы, а затем повторяющиеся группы изымаются и помещаются в отдельные отношения вместе с копиями ключа исходной таблицы. Далее в новых отношениях устанавливаются первичные ключи. Иногда ненормализованные отношения могут содержать одну или несколько повторяющихся групп внутри повторяющихся групп первого порядка. В таких случаях данный прием применяется до тех пор, пока повторяющихся групп совсем не останется. Полученный набор отношений будет находиться в первой
нормальной форме только тогда, когда ни в одном из них не будет повторяющихся групп атрибутов.
Хотя оба этих подхода одинаково корректны, следует отметить, что при использовании второго подхода полученные отношения находятся как минимум в 1НФ и обладают меньшей избыточностью данных. При выборе первого подхода выровненное 1НФ-отношение декомпозируется в ходе дальнейшей нормализации на те же отношения, которые могли бы быть получены с помощью второго подхода.
Вторая нормальная форма (2НФ). Вторая нормальная форма применяется к отношениям с составными ключами, т.е. к таким отношениям, первичный ключ которых состоит из двух и более атрибутов. Дело в том, что отношение с первичным ключом на основе единственного атрибута всегда находится, по крайней мере, в 2НФ. Отношение, которое не находится в 2НФ, может страдать от аномалий обновления. Например, предположим, что необходимо изменить арендную плату (Rent) для объекта недвижимости с номером ‘PG4’. Для этого потребуется обновить две строки отношения Customer Rental. Если значение арендной платы будет обновлено только в одной строке, то в результате база данных будет приведена в противоречивое состояние.
2НФ – отношение, которое находится в первой нормальной форме и каждый атрибут которого, не входящий в состав первичного ключа, характеризуется полной функциональной зависимостью от этого первичного ключа.
Нормализация 1НФ-отношений с образованием 2НФ-отношений включает устранение частичных зависимостей, что демонстрируется на примере отношения Customer_Rental (см. табл. 16). Если в отношении между атрибутами существует частичная зависимость, то функционально-зависимые атрибуты удаляются из него и помещаются в новое отношение вместе с копией их детерминанта.
Третья нормальная форма (3НФ). Хотя 2НФ-отношения в меньшей степени обладают избыточностью данных, чем 1НФ-отношения, они все еще могут страдать от аномалий обновления. Так, при попытке обновления имени владельца недвижимости (например, Tony Shaw с номером С093 (атрибут Owner No)) потребуется обновить две строки отношения Ргорerty_Owner. Если обновить только одну из этих двух строк, база данных попадет в противоречивое состояние. Эта аномалия обновления вызывается транзитивной зависимостью, присутствующей в данном отношении. Она может быть устранена путем приведения данного отношения к третьей нормальной форме. В этом разделе транзитивные зависимости рассматриваются вместе с третьей нормальной формой.
Транзитивная зависимость – если для атрибутов А, В и С некоторого отношения существуют зависимости вида А–>В и В–>С, то говорят, что
атрибут С транзитивно зависит от атрибута А через атрибут В (при условии, что атрибут А функционально не зависит ни от атрибута В, ни от атрибута С).
Транзитивная зависимость является описанием такого типа функциональной зависимости, которая возникает при наличии следующих функциональных зависимостей между атрибутами А, В и С:
А–>В и В–>С.
В данном случае транзитивная зависимость А–>С осуществляется через атрибут В. Это утверждение справедливо только в том случае, если атрибут А функционально не зависит от атрибутов В и С.
3НФ – отношение, которое находится в первой и второй нормальных формах и не имеет не входящих в первичный ключ атрибутов, которые находились бы в транзитивной функциональной зависимости от этого первичного ключа.
Нормализация 2НФ-отношений с образованием 3НФ-отношений включает устранение транзитивных зависимостей. Если в отношении существует транзитивная зависимость между атрибутами, то транзитивно-зависимые атрибуты удаляются из него и помещаются в новое отношение вместе с копией их детерминанта.
Определение нормальной формы Бойса–Кодда. Нормальная форма Бойса–Кодда
(НФБК) учитывает функциональные зависимости, в которых участвуют все потенциальные ключи отношения, а не только его первичный ключ. Для отношения с единственным потенциальным ключом его ЗНФ и НФБК являются эквивалентными.
Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом.
Для проверки принадлежности отношения к НФБК необходимо найти все его детерминанты и убедиться в том, что они являются потенциальными ключами. Напомним, что детерминантом является один атрибут или группа атрибутов, от которой полностью функционально зависит другой атрибут.
Различие между 3НФ и НФБК заключается в том, что функциональная зависимость А–>В допускается в 3НФ-отношении, если атрибут В является первичным ключом, а атрибут А не обязательно является потенциальным ключом. Тогда как в НФБК-отношении эта зависимость допускается только тогда, когда атрибут А является потенциальным ключом. Следовательно, нормальная форма Бойса–Кодда является жесткой версией формы 3НФ, поскольку каждое НФБК-отношение является 3НФ-отношением, но не всякое 3НФ-отношение является НФБК-отношением.
Четвертая нормальная форма (4НФ). В ходе исследований был выявлен еще один тип зависимости – многозначная зависимость, которая может вызвать проблеммы, связанные с избыточностью данных.
В случае многозадачной зависимости, существующей между атрибутами А, В и С некоторого отношения, для каждого значения А имеется
набор значений атрибута B и набор значений атрибута C. Однако входящие в эти наборы значения атрибутов B и С не зависят друг от друга.
4НФ – это отношение в нормальной форме Бойса–Кодда, которое не содержит нетривиальных многозадачных зависимостей.
Пятая нормальная форма (5НФ). При любой декомпозиции отношения на два других отношения полученные отношения имеют свойство соединения без потерь. Это значит, что полученные отношения можно снова соединить и получить прежнее отношение в исходном виде. Однако бывают случаи, когда требуется декомпозировать отношение на более чем два отношения. В таких (достаточно редких) случаях возникает необходимость учитывать зависимость соединения, которая устраняется с помощью пятой нормальной формы.
Зависимость соединения – это свойство декомпозиции, которое вызывает генерацию ложных строк при обратном соединении декомпозированных отношений с помощью операции естественного соединения.
5НФ – это отношение без зависимостей соединения.
Реляционная алгебра: основные понятия.
Реляционная алгебра – это теоретический язык операций, которые на основе одного или нескольких отношений позволяют создавать другое отношение без изменения самих исходных отношений.
Реляционная алгебра является языком последовательного использования отношений, в котором все кортежи, возможно, взятые даже из разных отношений, обрабатываются одной командой, без организации циклов. Для команд реляционной алгебры предложено несколько вариантов синтаксиса. Ниже мы воспользуемся общепринятыми символическими обозначениями для этих команд и представим их в неформальном виде.
Реляционная алгебра: Общая интерпретация реляционных операций.
Операция выборки (или ограничения) работает с одним отношением R и
определяет результирующее отношение, которое содержит только те кортежи (строки) отношения R, которые удовлетворяют заданному условию (предикату).
Объединение отношений R и S с кортежами I и J соответственно можно получить в результате их конкатенации с образованием одного отношения с максимальным количеством кортежей (I + J), если кортежи-дубликаты
исключены. При этом отношения R и S должны быть совместимы по объединению.
Разность двух отношений R и S состоит из кортежей, которые имеются в отношении R, но отсутствуют в отношении S. Причем отношения R и S должны быть совместимы по объединению.
Операции соединения. Как правило, пользователей интересует лишь некоторая часть всех комбинаций кортежей декартового произведения, которая удовлетворяет заданному условию. Поэтому вместо декартового произведения обычно используется одна из самых важных операций реляционной алгебры – операция соединения. В результате ее выполнения на базе двух исходных отношений создается некоторое новое отношение.
Перечислим различные типы операций соединения:
•Тета-соединение (-join). Операция тета-соединения определяет отношение, которое содержит кортежи из декартового произведения отношений R и S, удовлетворяющие предикату F.
•Соединение по эквивалентности (equi-join). Это соединение является частным видом тета-соединения..
•Естественное соединение (natural join). Естественным соединением называется соединение по эквивалентности двух отношений R и S, выполненное по всем общим атрибутам х, из результатов которого исключается по одному экземпляру каждого общего атрибута.
•Внешнее соединение (outer join). Зачастую при соединении двух отношений кортеж из одного отношения не находит соответствующего кортежа в другом отношении.
• Полусоединение (semi-join). Операция полусоединения определяет отношение, которое содержит те кортежи отношения R, которые входят в соединение отношений R и S.
Оператор деления. Оператор деления может быть полезен в случае запросов особого типа, которые довольно часто встречаются в приложениях баз данных.
Реляционная модель данных. В соответствии с реляционной моделью данных данные представляются в виде совокупности таблиц, над которыми могут выполняться операции, формулируемые в терминах реляционной алгебры или реляционного исчисления.
Ключи в реляционных базах данных
Суперключ – атрибут или множество атрибутов, которое единственным образом (superkey) идентифицирует кортеж данного отношения.
Потенциальный ключ – суперключ, который не содержит подмножества, также являющегося суперключом данного отношения.
Потенциальный ключ К для данного отношения R обладает двумя свойствами:
• уникальность; • неприводимость.
Первичный ключ – это потенциальный ключ, который выбран для уникальной идентификации кортежей внутри отношения.
Потенциальные ключи, которые не выбраны в качестве первичного ключа,
называются альтернативными ключами.
Внешний ключ – это атрибут или множество атрибутов внутри отношения, которое соответствует потенциальному ключу некоторого отношения.
Реляционные системы управления базами данных.
На протяжении многих лет предложенные Коддом правила вызывали массу наре-
каний у заинтересованных лиц и специалистов. Одни сочли их не более чем чисто теоретическими упражнениями. Другие заявили, что их продукты уже удовлетворяют многим этим правилам, если не всем. Эта дискуссия способствовала росту понимания пользователями и сообществом разработчиков СУБД важнейших свойств действительно реляционных СУБД. Чтобы подчеркнуть особое значение этих правил, они были разделены на пять функциональных групп.
1.Фундаментальные правила.
2.Структурные правила.
3.Правила целостности.
4.Правила управления данными.
5.Правила независимости от данных.
Фундаментальные правила (правила 0 и 12). Образно выражаясь, правила 0 и 12
являются “лакмусовой бумажкой”, которая позволяет определить принадлежность системы к реляционным СУБД. Если система на удовлетворяет этим правилам, то ее не следует считать реляционной
Это правило гарантирует, что все попытки доступа к базе данных контролируются СУБД таким образом, что целостность базы данных не может быть нарушена без ведома пользователя или администратора базы данных. Это, однако, не исключает возможностей использования языка низкого уровня с интерфейсом последовательной построчной обработки.
Структурные правила (правила 1 и 6). Фундаментальным структурным понятием реляционной модели является отношение. Кодд утверждает, что РСУБД должна поддерживать работу с несколькими структурными элементами, включая отношения, домены, первичные и внешние ключи. Для каждого отношения (таблицы) базы данных должен быть определен первичный ключ.
Правила целостности (правила 3 и 10). Кодд предложил два правила поддержки целостности данных. Поддержка целостности данных является важным критерием оценки пригодности системы для практических нужд. Чем больше ограничений целостности может поддерживаться самой СУБД, а не отдельными ее приложениями, тем выше гарантии качественности данных.
Правила манипулирования данными (правила 2, 4, 5 и 7). Идеальная РСУБД должна поддерживать 18 функций управления данными (будут рассматриваться в юните 2). Они определяют полноту языка запросов (здесь термин “запрос” включает и операции вставки, обновления и удаления). Правила манипулирования данными определяют способ применения функций управления данными. Строгое следование этим правилам позволяет изолировать пользователя и прикладные программы от физического и логического механизмов реализации средств манипулирования данными.
Правила независимости от данных (правила 8, 9 и 11). Кодд определяет три правила независимости данных от приложений, которые эти данные используют. Строгое соблюдение этих правил гарантирует, что пользователи и разработчики будут защищены от необходимости вносить тотальные изменения в приложения при каждой реорганизации базы данных на низком уровне
Независимость от распределения данных означает, что прикладная программа, осуществляющая доступ к СУБД на отдельном компьютере, должна без какихлибо модификаций продолжать работать и в том случае, когда данные в сети будут перенесены с одного компьютера на другой. Другими словами, для конечного пользователя должна быть создана иллюзия того, что данные централизованно хранятся на единственном компьютере, а ответственность за перемещение и поиск данных среди (возможно) нескольких мест их хранения должна возлагаться исключительно на систему. Обратите внимание, что здесь не сказано о том, что реляционная СУБД должна непременно поддерживать работу с распределенной базой данных. Здесь просто имеется в виду, что язык запросов должен оставаться неизменным и в том случае, когда возможность работы с распределенными данными реализуется в некоторой СУБД.
Развитие и стандартизация языка SQL.
Непроцедурный, структуризированный язык запросов (SQL) – язык,
ориентированный на операции с данными, представленными в виде логически взаимосвязанных совокупностей таблиц. Особенность предложений языка запросов SQL – ориентированность в большей степени на конечный результат обработки данных, чем на процедуру этой обработки. SQL сам определяет, где