Министерство образования российской федерации московский государственный институт электроники и математики (Технический университет)
 Скачать 1.02 Mb.
|
|
ФАКУЛЬТЕТ Шифр_факультета, Название факультета КАФЕДРА Шифр_кафедры, Название_кафедры КУРС Номер_курса, Начало_сессии, Окончание_сессии ГРУППА Индекс_группы, ФИО_старосты ДИСЦИПЛИНА Шифр_дисциплины, Название_дисциплины СТУДЕНТ Номер_зачетной_книжки, ФИО_студента Рис.2.4. Пример иерархической базы данных Корневая запись дерева должна содержать ключ с уникальным значени- ем. Ключи некорневых записей должны иметь уникальные значения только в экземплярах групповых отношений, т.е. на одном и том же уровне иерархии в разных ветвях дерева могут быть экземпляры записей с одинаковыми ключами. Это объясняется тем, что каждая запись идентифицируется полным сцеплен- ным ключом, который образуется путём конкатенации всех ключей экземпля- ров родительских записей. Таким образом, попасть в любую вершину можно, только проделав полный путь по дереву от корня. Связи между записями в ИМД обычно выполнены в виде ссылок (т.е. хранятся адреса связанных записей). Подробнее об этом рассказано в разделе 5.5."Организация связей между хранимыми записями". Основным недостатком ИМД является дублирование данных. Оно вызва- но тем, что каждая сущность (атрибут) может относиться только одной к роди- тельской сущности. Таким образом, если надо сохранить, например, данные о детях сотрудника, а на предприятии трудится и отец, и мать ребенка, то инфор- мацию о детях придётся хранить дважды. Это может вызвать нарушение логи- ческой целостности БД при внесении изменений в данные о детях. Если данные имеют естественную древовидную структуризацию, то ис- пользование иерархической модели данных не вызывает проблем. Но на прак- тике часто требуется реализовать структуры данных, отличные от иерархиче- ской. Для решения этих задач конкретные СУБД, основанные на ИМД, вклю- чают дополнительные средства, облегчающие представление произвольно ор- ганизованных данных. 2.4. Реляционная модель данных (РМД) 2.4.1. Понятие отношения Реляционная модель данных была предложена математиком Э.Ф. Коддом (Codd E.F.) в 1970 г. РМД является наиболее широко распространенной моде- лью данных и единственной из трех основных моделей данных, для которой разработан теоретический базис с использованием теории множеств. – 18 – В основе РМД лежит понятие отношения, представляющего собой под- множество декартова произведения доменов. Домен – это множество значений, которое может принимать элемент (например, множество целых чисел, множе- ство комбинаций символов длиной N и т.п.). Пусть D 1 , D 2 ,…, D k – произвольные конечные и не обязательно различ- ные множества (домены). Декартово произведение этих множеств определяет- ся следующим образом: D 1 D 2 ...D k = {(d 1 , d 2 ,..., d k ) | d i D i , i=1,…,k}. Таким образом, декартово произведение позволяет получить все возмож- ные комбинации элементов исходных множеств. Пример. Для доменов D 1 = (1,2), D 2 = (A,B,C) декартово произведение D = D 1 D 2 будет таким: D = {(1,A), (1,B), (1,C), (2,A), (2,B), (2,C)}. Подмножество декартова произведения доменов называется отношением. Элементы отношения называют кортежами. Элементы кортежа принято называть атрибутами. Количество атрибутов кортежа определяет арность от- ношения. Отношения арности 1 называют унарными, арности 2 – бинарными, арности n – n-арными. Отношение содержит информацию о сущностях одного типа. Каждый кортеж отношения соответствует одному экземпляру сущности. 2.4.2. Свойства отношений Отношение обладает двумя основными свойствами: 1. в отношении не должно быть одинаковых кортежей, т.к. это множество; 2. порядок кортежей в отношении несущественен. Отношение удобно представлять как таблицу, где строка является кортежем, столбец соответствует домену (рис. 2.5, отношение СТУДЕНТЫ). домен 1 домен 2 домен 3 (ключ) домен 4 домен 5 Группа ФИО студента Номер зачётной книжки Год рождения Размер стипендии С–72 Волкова Елена Павловна С-12298 1981 566.40 С–91 Белов Сергей Юрьевич С-12299 1980 400.00 . . . С–72 Фролов Юрий Вадимович С-14407 1981 0 Рис.2.5. Пример табличной формы представления отношения Отношение имеет имя, которое отличает его от имен всех других отно- шений. Атрибутам реляционного отношения назначаются имена, уникальные в рамках отношения. Обращение к отношению происходит по его имени, а обра- щение к атрибуту – по имени отношения и имени атрибута. Каждый атрибут определён на некотором домене, несколько атрибутов отношения могут быть определены на одном и том же домене (например, номе- ра рабочего и домашнего телефона). Домен задаётся типом данных и ограниче- – 19 – ниями целостности, например, оклад – это число больше нуля. Значение атри- бута может быть не определено в момент внесения записи в БД. Для таких слу- чаев предусмотрено специальное значение – null, которое можно интерпрети- ровать как "неизвестное значение". Ключ отношения – это атрибут, значения которого идентифицируют кортеж. Таким образом, ключ имеет уникальные в рамках отношения значения. (На рис. 2.5 ключ выделен полужирным шрифтом). Если ключ состоит из не- скольких атрибутов, он называется составным. Ключей может быть несколько; основной ключ – первичный, его значения не могут обновляться. Другие ключи называются возможными или потенциальными ключами. РМД не поддерживает групповые отношения. Для связей между отноше- ниями используются внешние ключи. Внешний ключ – это атрибут подчинённо- го отношения, который является копией первичного (или уникального) ключа родительского отношения. (Пример – отношение ДЕТИ, связанное с отношени- ем СТУДЕНТЫ по внешнему ключу Номер зачётной книжки, рис. 2.6). внешний ключ Номер зачётной книжки Имя, отчество ребенка Дата рождения С-12298 Антон Павлович 01.12.01 С-12298 Юлия Павловна 01.12.01 С-12299 Ольга Сергеевна 16.04.02 Рис.2.6. Отношение "Дети", связанное с отношением "Студенты" по внешнему ключу Фактически, внешние ключи логически связывают экземпляры сущно- стей разных типов между собой. Таким образом, внешний ключ можно тракто- вать как ограничение целостности на две таблицы, в соответствии с которым множество значений внешнего ключа является подмножеством значений ключа родительской таблицы. Если связь необязательная, то значение внешнего ключа может быть неопределённым (null). Перечень атрибутов отношения с их типами данных и размерами опреде- ляют схему отношения. Отношения, построенные по одинаковой схеме, назы- вают односхемными; по разным схемам – разносхемными. Все операции над данными в РМД выполняются над отношением и тре- буют задания имени отношения. Если операция применяется к части отноше- ния, то может потребоваться идентификация кортежа или группы кортежей и задание имен атрибутов. В РМД используются следующие операции: запомнить: внесение информации в БД (требует формирования значений уникального ключа и обязательных атрибутов кортежа); обновить: модификация данных – изменение значений отдельных атрибутов кортежей; извлечь: чтение данных; удалить: физическое или логическое удаление данных (кортежа или группы кортежей). – 20 – Структуризация данных в РМД существенно отличается от структуриза- ции данных по версии CODASYL. В таблице 2.1. приведено соответствие этих двух вариантов структуризации. Таблица 2.1. Сравнение структуризации данных в РМД и по версии CODASYL Термины версии CODASYL Термины (и синонимы) РМД Элемент данных Атрибут (поле) Агрегат Запись (группа) Кортеж (запись, строка) Совокупность записей одного типа Отношение (таблица) Набор (групповое отношение) База данных База данных 2.4.3. Достоинства и недостатки РМД Широкое распространение реляционной модели объясняется в первую очередь простотой представления и формирования базы данных, универсально- стью и удобством обработки данных, которая осуществляется с помощью дек- ларативного языка запросов SQL (Structured Query Language). Существуют два стандарта SQL, определённые американским нацио- нальным институтом стандартов (ANSI): SQL-89 (SQL1) и SQL-92 (SQL2). В настоящее время в стадии разработки находится новый стандарт – SQL3. Боль- шинство коммерческих систем управления базами данных (СУБД) поддержи- вают стандарт SQL2, который принят ISO (International Standards Organization) в качестве международного стандарта. (Подробнее об SQL рассказано в [10]). Моделирование предметной области в рамках реляционной модели соз- даёт некоторые сложности, т.к. в этой модели нет специальных средств для отображения различных типов связей. Отсутствие множественных связей, на- пример, "многие ко многим", вызывает увеличение объёма хранимой (дубли- руемой) информации. Отсутствие возможности указания типов связей (напри- мер, "работает" или "имеет"), приводит к тому, что семантика связей в принци- пе не может быть отражена в реляционной модели данных и зависит от того, как связь интерпретируется приложениями. Отсутствие специальных механизмов навигации (как в иерархической или сетевой моделях), с одной стороны, ведёт к упрощению модели, а с другой – к многократному увеличению времени на извлечение данных, т.к. во многих случаях требуется просмотреть всё отношение для поиска нужных данных. В РМД нет понятий режим включения и класс членства, поэтому набор средств описания ограничений целостности очень мал. (Подробнее об этом рас- сказано в разделе 8.1."Обеспечение целостности данных"). Обработка данных в отношениях осуществляется с помощью операций реляционной алгебры. 2.4.4. Операции реляционной алгебры Операндами для операций реляционной алгебры являются реляционные отношения. Результатом выполнения операций реляционной алгебры также яв- – 21 – ляется отношение. Использование реляционной алгебры накладывает на отно- шения два ограничения: порядок столбцов (полей) в отношении фиксирован; отношения конечны. Существует пять основных операций реляционной алгебры – проекция, селекция, декартово произведение, разность, объединение – и три вспомога- тельных: соединение, пересечение и деление. Вспомогательные операции могут быть выражены через основные, но в некоторых системах реализуются отдель- но для удобства пользователей. 1. Проекция (projection, обозначается "") – это унарная операция (выполняе- мая над одним отношением), служащая для выбора подмножества атрибутов из отношения R. Она уменьшает арность отношения и может уменьшить его мощность, исключая одинаковые кортежи. 2. Селекция (selection, обозначается "") – это унарная операция, результатом которой является подмножество кортежей исходного отношения, удовлетво- ряющих условиям, которые накладываются на значения определённых атри- бутов. 3. Декартово произведение (cartesian product, обозначается "") соответствует определению декартова произведения для РМД. 4. Объединение (union, обозначается "U") – это бинарная операция над одно- схемными отношениями R и S, результатом которой является отношение, включающее все кортежи обоих отношений без повторов. 5. Разность (set difference, обозначается "–") – это бинарная операция над од- носхемными отношениями (R–S), результатом которой является множество кортежей отношения R, не принадлежащих отношению S. 6. Пересечение (intersection, обозначается "∩") – это бинарная операция над односхемными отношениями R и S, результатом которой является подмно- жество кортежей, принадлежащих обоим исходным отношениям: R ∩ S = R – (R – S) 7. Соединение (join, обозначается "") – это бинарная операция над разно- схемными отношениями R и S. Кортежи результирующего отношения со- держат все атрибуты обоих отношений (возможно, за исключением повто- ров). В общем случае соединение происходит по условию F, которое опре- деляет соотношение между значениями атрибутов из разных отношений. Фактически, соединение является подмножеством декартова произведения, для которого выполняется некоторое условие: R F S = F (R S) Если условием соединения является равенство значений атрибутов, такая операция называется эквисоединением. Естественным называется эквисое- динение, построенное по условию равенства значений одинаковых атрибу- тов кортежей исходных отношений. 8. Деление (division, обозначается "/") – это бинарная операция над разносхем- ными отношениями R и S. Пусть отношение R содержит атрибуты {r 1 , r 2 ,...,r k , r k+1 ,...,r n }, а отношение S – атрибуты {r k+1 ,...,r n }. Тогда результи- – 22 – рующее отношение содержит атрибуты {r 1 ,r 2 ,...,r k }. Кортеж отношения R включается в результирующее отношение, если его декартово произведение с отношением S входит в R. Деление можно выразить так: R / S = r1,…,rk (R) – r1,…,rk (( r1,…,rk (R) S) – R). 2.4.5. Преобразования операций реляционной алгебры Операндами операций реляционной алгебры являются отношения, по- этому для их выполнения необходимо просмотреть все кортежи исходного от- ношения (или отношений). Следствием этого является большая размерность реляционных операций. Уменьшения размерности операций можно достичь, изменяя последовательность выполняемых операций. В качестве примера при- ведём отношения R1 и R2, содержащие по 1000 кортежей, причём только 10 кортежей в каждом отношении удовлетворяют условию F. Если выполнять сле- дующую последовательность операций: F (R1 U R2), то после выполнения объединения получится 2000 кортежей (если отношения не содержат одинаковых кортежей), а после селекции останется 20 записей. Ес- ли изменить последовательность выполнения операций: F (R1) U F (R2), то после селекции останется по 10 записей из каждого отношения, объединение которых даст 20 требуемых кортежей. Следовательно, не потребуется хранить промежуточный результат в 2000 кортежей и просматривать его для поиска кортежей, удовлетворяющих условию. Оптимизация выполнения запросов реляционной алгебры основана на понятии эквивалентности реляционных выражений. Операндами выражений являются переменные-отношения R i и константы. Каждое выражение реляци- онной алгебры определяет отображение кортежей переменных-отношений R i (i=1,…,n) в кортежи единственного отношения, которое получается в результа- те подстановки кортежей каждого R i и выполнения всех определяемых выра- жением вычислений. Два выражения реляционной алгебры считаются эквивалентными, если они описывают одно и то же отображение. Существуют законы, которые в соответствии с этим определением позволяют выполнять эквивалентные преобразования выражений реляционной алгебры: 1. Закон коммутативности для декартовых произведений: R1 R2 = R2 R1 2. Закон коммутативности для соединений (F – условие соединения): R1 F R2 = R2 F R1 3. Закон ассоциативности для декартовых произведений: (R1 R2) R3 = R1 (R2 R3) 4. Закон ассоциативности для соединений (F1, F2 – условия): – 23 – (R1 F1 R2) F2 R3 = R1 F1 (R2 F2 R3) 5. Комбинация селекций (каскад селекций): F1 ( F2 (R)) = F1 F2 (R) 6. Комбинация проекций (каскад проекций): A1,A2,...,Am ( B1,B2,...,Bn (R)) = A1,A2,...,Am (R) где {A m } {B n }. 7. Перестановка селекции и проекции: F ( A1,A2,...,Am (R)) = A1,A2,...,Am ( F (R)) 8. Перестановка селекции с объединением: F (R1 U R2) = F (R1) U F (R2) 9. Перестановка селекции с декартовым произведением: F (R1 R2) = ( F (R1)) R2 (если F содержит атрибуты, присутствующие только в R1); F (R1 R2) = R1 ( F (R2)) (если F содержит атрибуты, присутствующие только в R2); F (R1 R2) = ( F1 (R1)) ( F2 (R2)) (если F = F1F2, где F1 содержит атрибуты, присутствующие только в R1, а F2 содержит атрибуты, присутствующие только в R2); F (R1 R2) = F2 ( F1 (R1) R2) (если F = F1F2, где F1 содержит атрибуты, присутствующие только в R1, а F2 содержит атрибуты, присутствующие и в R1, и в R2). 10. Перестановка селекции с разностью: F (R1 – R2) = F (R1) – F (R2) 11. Перестановка проекции с декартовым произведением: A1,A2,...,Am (R1R2) = ( B1,B2,...,Bn (R1)) ( С1,С2,...,Сr (R2)) где атрибуты {B n } {A m }, {С r } {A m } и атрибуты B 1 ,B 2 ,...,B n представлены в отношении R1, а атрибуты С 1 ,С 2 ,...,С r – в R2. 12. Перестановка проекции с объединением: A1,A2,...,Am (R1 U R2) = ( A1,A2,..., Am (R1)) U ( A1,A2,...,Am (R2)) 2.5. Другие модели данных Всё возрастающая сложность приложений баз данных и ограниченность реляционной модели привели к развитию модели Кодда, которое сначала полу- чило название расширенной реляционной модели, а позже получило свое разви- тие в объектно-реляционных моделях данных (ОРМД). 2.5.1. Объектно-реляционные модели данных Объектно-реляционные модели данных (ОРМД) основаны на понятии объекта, аналогичного понятию объекта в объектно-ориентированном про- граммировании. В ОРМД используются такие объектно-ориентированные ком- – 24 – поненты, как пользовательские типы данных, инкапсуляция, полиморфизм, на- следование, переопределение методов и т.п. К сожалению, до настоящего времени (2003 г.) разработчики не пришли к единому мнению о том, как следует определять ОРМД. Модели, поддерживае- мые различными производителями СУБД, существенно отличаются по своим функциональным характеристикам, поэтому о включении объектов в РМД можно говорить только как об общем направлении развития баз данных. О пер- спективах этого направления свидетельствует тот факт, что ведущие фирмы– производители СУБД, в числе которых Oracle, Informix и INGRES, расширили возможности своих продуктов до объектно-реляционной СУБД (ОРСУБД). В большинстве реализаций ОРМД объектами признаются агрегат и таб- лица (отношение), которая может входить в состав другой таблицы. Методы обработки данных представлены в виде хранимых процедур и триггеров, кото- рые являются процедурными объектами базы данных, и связаны с таблицами. На внутреннем (физическом) уровне все данные ОРБД хранятся в виде отноше- ний, и ОРСУБД поддерживают язык SQL. 2.5.2. Объектно-ориентированные модели данных Ещё один подход к построению БД – использование объектно- ориентированных моделей данных (ООМД). Моделирование данных в ООМД базируется на понятии объекта. Для ООМД, как и в случае с ОРМД, не сущест- вует общепризнанной модели данных. При создании объектно-ориентированных СУБД (ООСУБД) используют- ся разные методы, а именно: встраивание в объектно-ориентированный язык средств, предназначенных для работы с БД; расширение существующего языка работы с базами данных объектно-ориентированными функциями; создание объектно-ориентированных библиотек функций для работы с СУБД; создание нового языка и новой объектно-ориентированной модели данных. К достоинствам ООМД можно отнести широкие возможности моделиро- вания предметной области, выразительный язык запросов и повышенную про- изводительность. Эти модели обычно применяются для сложных предметных областей, для моделирования которых не хватает функциональности реляцион- ной модели (например, систем автоматизации проектирования, издательских систем и т.п.). Среди недостатков ООМД следует отметить отсутствие универ- сальной модели, недостаток опыта создания и эксплуатации ООБД, сложность использования и недостаточность средств защиты данных. В 1997 г. рабочая группа ODMG (Object Database Management Group), об- разованная фирмами-производителями ООСУБД, выпустила стандарт ODMG 2.0 для ООСУБД, в котором описана объектная модель, язык определения за- просов, язык объектных запросов и связующие языки С++, Smalltalk и Java. |