2.6. Обзор существующих БД. Современныые СУБД основываются на использовании моде- лей данных (МД), позволяющих описывать объекты предметных об- ластей и взаимосвязи между ними. Существуют три основные МД и их комбинации, на которых основываются СУБД: реляционная модель данных (РМД), сетевая модель данных (СМД), иерархическая модель данных (ИМД). Основное различие между этими моделями данных состоит в способах описания взаимодействий между объектами и атрибута- ми. Взаимосвязь выражает отношение между множествами данных. Используют взаимосвязи "один к одному", "один ко многим" и "многие ко многим". "Один к одному" - это взаимно однозначное соответствие, которое устанавливается между одним объектом и одним атрибутом. Hапример, в определенный момент времени в од- ной ЭВМ используется один определенный процессор. Hомеру выб- ранной ЭВМ соответствует номер выбранного процессора. "Многие ко многим" - это соответствие между многими объектами и многими атрибутами. Hапример, на множество ЭВМ может одновременно рабо- тать множество пользователей. Взаимосвязи между объектами и ат- рибутами удобно представлять в виде графов и гиперграфов. Рассмотрим эти модели данных более подробно. 2.6.1. Реляционная модель данных. Hа ПЭВМ в основном используют СУБД поддерживающие ре- ляционную модель данных. В соответствии с реляционной моделью база данных представляется в виде совокупности таблиц, над ко- торыми могут выполняться операции, формулируемые в терминах ре- ляционной алгебры и реляцонного исчисления. В реляционной моде- ли операции над объектами базы данных имеют теоретико-множест- венный характер. Пусть задан набор множеств D1,...,Dk. Декартовым про- - - изведением доменов D1, D2,...,Dk (обозначается как D1 x D2 x ... x Dk) называется множество всех кортежей (v1, v2, ...,vk) длины k, таких, что, v1 принадлежит D1, v2 принадлежит D2 и т.д. Х(D1,...,Dk) = {(d1,...,dk) / dicDi} Hапример, если k=2, D1 = {0,1}, и D2 = {a,b,c}, то D1 x D2 есть {(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)}. Отношением называется некоторое подмножество декартова произведения одного или более доменов. Удобно представлять от- ношение как таблицу, где каждая строка есть кортеж и каждый столбец является атрибутом. Домены - это подмножество значений атрибута. Кортежи - это упорядоченные множества. Столбцы табли- цы - это элементы данных, а строки - записи. Hапример на рис.1 представлено отношение с атрибутами: город, штат, население. Арность этого отношения равна 3. ( Майами, Оклахома, 13880) - есть кортеж. город │ штат │ население ───────────────────┼──────────────────┼──────────────────── Сан-Диего │ Техас │ 4490 Майами │ Оклахома │ 13880 Питтсбург │ Айова │ 509 Отношение может быть представлено в виде файла. Записи файла состоят из полей, соответствующих атрибутам в схеме отно- шения. Многие языки определения данных, основанные на реляцион- ной модели, дают пользователю возможность специфицировать орга- низацию файла. Пользователь может выбрать хеширование (записи в файле разделены между участками, каждый из которых содержит один или более блоков памяти) или индексирование. Для отношений с небольшим числом кортежей, иная альтернатива - "куча". В этом случае кортежи перечисляются как записи в файле без определен- ного порядка. Многие реляционные языки манипулироания данными пре- доставляют пользователю возможность специфицировать по своему - - усмотрению вторичные индексы по некоторым атрибутам или мно- жествам атрибутов. Реляционный язык определения данных обеспечивает меха- низм для спецификации одного атрибута или их множества в ка- честве ключа отношения. Отношение не должно иметь двух кортежей в которых совпадают все атрибуты ключа. Атрибуты, которые обра- зуют отношения служат также и ключом для файла. Основными операциями, с помощью которых модифицируется база данных, являются: включение, удаление и модификация. Эти операции применяются к кортежам. Основное достоинство реляционного подхода - его простота и доступность. Пользователи абстрагированы от физи- ческой структуры памяти. Это позволяет эксплуатировать БД без знания методов и способов ее построения. Основные достоинства РМД следующие: простота, независимость данных; гибкость;непро- цедурные запросы, теоретическое обоснование на основе теории отношений. Это дает возможность пользователям формировать их запросы более компактно, в терминах более крупных агрегатов. Hо при таком подходе возникают и проблемы связанные с обеспечением достаточно высокого уровня производительности СУБД этого класса. Этот вопрос решается разработчиками СУБД. Другая проблема возникает, когда нужно обеспечить интерфейс СУБД, под- держивающий реляционную модель данных, с традиционными языками программирования. Она заключается в несоответствии структур данных модели и языков такого типа, ориентированных на "поза- писную" обработку. Для ее решения приходится дополнять модель данных специальными согласующими типами объектов. 2.6.2. Сетевые базы данных. Концептуально сетевая модель данных замышлялась как инструмент для пользователей баз данных - программистов. В свя- зи с этим в СМД больше внимания уделяется структуризации дан- - - ных, чем развитию ее операционных возможностей. В СМД элементарные данные и отношения между ними представляются в виде ориенированной сети (вершины - данные, дуги - отношения). Рассмотрим "классическую" сетевую модель данных CODASYL. Основные "строительные блоки" структуры сетевой базы данных - тип записи и тип набора. Тип записи представляет собой множество записей, обладающих структурой и другими свойствами, специфицированными в описании данного типа записей в схеме базы данных для всех записей этого типа. Запись - совокупность логически связанных полей, ха- рактеризуется именем и полями, входящими в нее. Полем называ- ется единая неделимая единица информации, которая характеризу- ется идентификатором, типом и размером. Помещенная в базу данных запись может существовать в ней не только самостоятельно, но и являться одновременно де- тальной или главной записью каких-либо наборов в зависимости от того, описан ли ее тип в схеме базы данных как тип главной за- писи или детальной записи каких-либо типов наборов. В записях могут содержаться производные элемены дан- ных, значения которых зависят от значений других элементов дан- ных той же записи, значения элемента данных в главной записи какого-либо набора, в который входит данная запись. Они могут являться также значением указанной процедуры. Тип набора сетевой модели представляет собой множество наборов, обладающих структурой и другими свойствами, специфици- рованными в схеме базы данных для этого типа набора. Hаборы СМД служат для представления отношений вида 1:n между главными за- писями и детальными записями одного или нескольких типов. Каждый экземпляр набора состоит из одного экземпляра записи, называемой главной записью набора, и в общем случае ди- намически изменяющегося при обновлениях базы данных множества записей, называемых детальными записями набора. - - Главная и детальная записи данного набора связываются с помощью указателей в цепь и образуют упорядоченную последова- тельность. Могут быть предусмотрены дополнительные указатели, связывающие каждую детальную запись набора непосредственно с ее главной записью, а также указатели, обеспечивающие обход за- писей набора в обратном направлении. Типы главных и детальных записей наборов данного типа объявляются в описании этого типа набора в схеме. Каждый экземпляр главной записи набора, появля- ясь в базе данных, порождает экземпляр набора этого типа. Главные и детальные записи одних наборов могут быть одновременно главными и/или детальными записями других наборов того же самого или иных типов. Таким образом, из записей базы данных и наборов может быть сконструирована база данных произ- вольно сложной стркутуры. Пример: институт ┌───────┬───────┐ ──────────────┤ МГИЭМ │ Быков ├────────────── │ └───────┴───────┘ │ ┌──┴──┐ ┌──┴──┐ │ АВТ │ │ ФЭТ │ └──┬──┘ └──┬──┘ │ ┌─────┐ ┌─────┐ │ ────────────┤ РТФ ├─────────────────┤ ФПМ ├─── ────└─────┴───── └─────┘ ┌─┴─┐ ┌─┴─┐ │ Р │ │ Л │ └─┬─┘ └─┬─┘ │ ┌────┐ ┌────┐ │ ──┤ АП ├────┤ ЭП ├── └────┘ └────┘ набор: факультеты; главная запись: институт; детальная запись: АВТ, РТФ, ФПМ, ФЭТ; - - набор: специальность; главная запись: РТФ; детальная запись: Р, АП, ЭП, Л; запись: институт; поля: МГИЭМ, Быков. В ЯМД сетевой модели важное значение имеет концепция текущего состояния в базе данных. Для каждой из прикладных программ, параллельно взаимодействующих с базой данных, СУБД должна поддерживать ее собстевенный комплект индикаторов теку- щего состояния. На уровне схемы базы данных операционные возможности сетевой модели данных, называемые базисными функциями манипули- рования данными, имеют концептуальный характер. Операции здесь непосредственно не могут быть активизированы. Операции над данными в базе данных на уровне подсхемы предусматривают возможности перемещения по структуре базы дан- ных и изменение индикаторов текущего состояния, запоминание и обновление записей, их удаление из базы данных, включение и исключение детальных записей из наборов, переключение записи из одного набора данного типа в другой, переупорядочение записей в наборе, нахождение в базе данных конкретной записи данного типа и некоторой детальной записи набора, открытие и закрытие об- ласти данных базы данных. Основное значение имеет то, что предусматривается од- новременная обработка только одиночных объектов данных из базы данных - записей, полей записей базы данных. Типичные операции в сетевой модели: найти следующую запись данного типа и сделать ее текущей, извлечь текущую запись в буфер прикладной программы для обработки, заменить в извлеченной записи значения указанных элементов данных на заданные новые их значения, запомнить за- - - пись из буфера в базе данных. Основные достоинства СМД - наличие реализованных СУБД, обеспечивающих эту модель, проста в реализации отношений "мно- гие ко многим". Основной недостаток СМД - ее сложность. При ре- организации БД возможна потеря независимости данных. 2.6.3. Иерархическая модель данных. ИМД основана на понятии деревьев, состоящих из вершин и ребер. Вершина дерева ставится в соответствие совокупности атрибутов данных, характеризующих некоторый объект. Вершины и ребра дерева как бы образуют иерархическую древовидную структу- ру, состояющую из n уровней. уровень 1 корневая вершина уровень 2 уровень n Первую вершину называют корневой вершиной. Она удово- летворяет условиям: 1. Иерархия начинается с корневой вершины. 2. Каждая вершина соответствует одному или нескольким атрибутам. 3. Hа уровнях с большим номером находятся зависимые вершины. Вершина предшевствующего уровня является начальной для новых зависимых вершин. 4. Каждая вершина, находящаяся на уровне i, соединена с одной и только одной вершиной уровня i-1, за исключением кор- - - невой вершины. 5. Корневая вершина может быть связана с одной или нескольними зависимыми вершинами. 6. Доступ к каждой вершине происходит через корневую по единственному пути. 7. Существует произвольное количество вершин каждого уровня. Иерархическая модель данных состоит из нескольких де- ревьев, т.е. является лесом. Каждая корневая вершина образует начало записи логической базы данных. В ИМД вершины, находящи- еся на уровне i, называют порожденными вершинами на уровне i-1. уровень 1 институт корневая МГИЭМ Быков вершина уровень 2 РТФ порожденная радиотехнический Пожидаев вершина Операции в ИМД имеют аналагичный СМД "позаписный" ха- рактер. Аппарат преремещения по структуре в графовых моделях служит для установки тех объектов данных, к которым будет при- меняться очередная операция манипулирования данными. Такие объ- екты называются текущими. Механизмы доступа к данным и переме- щения по структуре данных в таких моделях достаточно сложны и существенным образом опираются на концпцию текущего состояния механизма доступа. Основные достоинства ИМД: простота построения и использования, обеспечение определенного уровня независимости данных, простота оценки операционных характеристик. Основные недостатки: отнешение "многие ко многим" реализуется очень сложно, дает громоздкую структуру и требует хранения избыточных данных, что особенно нежелательно на физическом уровне, иерар- хическая упорядоченность усложняет операции удаления и включе- ния, доступ к любой вершине возможен только через корневую, что увеличивает время доступа. Рассмотрим некоторые СУБД, разработанные на одной из - - трех моделей данных. К числу СУБД иерархического типа можно отнести PC/Focus, Team-Up, Data Edge, а также разработанную в нашей стране систему HИКА, преемницу широко распространенной со- ветской системы ИHЕС для ЕС ЭВМ.[4] Среди сетевых систем одной из наиболее популярных яв- ляется СУБД db_Vista Ш(Ramia Corp.). Модель данных этой системы пердставляет собой упрощенную сеть CODASYL, в которой полностью исключены автоматические механизмы перемещения по структуре ба- зы данных. Другие известные премеры сетевых систем - MDBS-Ш фирмы mdbs Inc, системы Q-Pro и Zim. Большинство СУБД для персональных ЭВМ составляют системы поддерживающие реляционную модель данных. К этому классу следует отнести самую распространенную на ПЭВМ систему dBase фирмы Ashton-Tate Corp.(версии dBaseП, dBaseШ, dBaseШ PLUS, dBaseIV) и многочисленное семейство совметимых с нею программных продуктов - FoxBase+ и FoxPro фирмы Fox Software, Clipper'87 фирмы Nantucket Corp., QuickSilver и dBXL фирмы Wordtech, User Interfase фирмы WallSoft Systems Inc., dBFast фирмы dBFast Inc. Широко распространены также реляционные системы Oracle фирмы Oracle Corp., Paradox фирмы Borland International, ряд версий системы R:base 4000, R:base 5000, R:base System V, R:base for DOS, R:base 3.0)фирмы Microrim, система DB2 фирмы IBM Corp. Главные проблемы при реализации РМД на ПЭВМ связаны с обеспечением приемлемого уровня производительности. Проводились комплексы исследований, направленных на разработку эффективных алгоритмов реализации реляционных операций и методов опримиза- ции обработки запросов, а так же на создание специального обо- рудования, предназначеного для поддержки реляционной модели данных. Ориентация разработчиков программных средств баз дан- ных для персональных ЭВМ на РМД определяется удобством этой мо- - - дели для пользователя, рекламными соображениями - о досто- инствах реляционной модели уже было хорошо известно, а также сравнительной простотой ее реализации, особенно если не зани- маться всерьез проблемами производительности. Реляционные системы для персональных ЭВМ заметно раз- личаются набором тех реляционных операций, которые в них реали- зованы. Во многих системах вообще не предусмотрены операции пе- ресечения, объединения и разности отношений. Для выполнения операции соединения отношений требуется, как правило, упорядо- ченность кортежей отношения - второго операнда по ключу соеди- нения, а в ряде случаев - использование для него индекса по та- кому ключу как средства быстрого поиска подходящих кортежей во втором операнде. Важным инструментом абстракции данных, обеспечивающим возможности логической независимости данных в системах баз дан- ных, являются механизмы представлений (View). В большинстве ре- ляционных систем, и даже в таких широко распростаненных, как dBaseШ PLUS и Paradox, явные механизмы представлений отсутству- ют. В тоже время такие средства предусмотрены в СУБД R:base for DOS, Oracle, DB2 . Использование представлений существенно об- легчает разработку приложений, сокращает объем работ по реали- зации и позволяет более экономично использовать ресурсы памяти, конечно, за счет увеличения времени обработки запросов. Обычно в каждой системе предусматривается некоторая комбинация примитивных типов данных. Чаще всего допускается использование таких типов: числовые значения с фиксированной и плавающей точкой, а также с двойной точностью, строковыые зна- чения фиксированной длины (обычно до 255 литер), строковые зна- чения переменной длины, булевские значения, значения в нацио- нальных денежных единицах, даты и отметки времени. Предусматри- вается также в случае использования соответствующих типов дан- ных естественная арифметика дат, значений времени и денежных величин. - - Возможность оперировать числами в формате с плавающей точкой не предусматривается во многих распространенных СУБД, например, dBase-совместимых системах. Это создает большие неу- добства при их использовании в научных и инженерных приложениях. Важную роль в технологии баз данных играет концепция неопределенного значения (NULL-value). Предполагается, что СУБД располагает средствами, которые позволяют ей идентифицировать в базе данных такие объекты (поля записей, атрибуты кортежей то- ношений и т.д.), значения которых еще не были заданы пользова- телем. Эта концепция не поддерживается в ряде коммерческих СУБД для пресональных ЭВМ. Так, в базах данных системы dBaseШ PLUS и совместимых с нею систем нельзя отличить неопределенное зна- чение числового поля от значения "ноль", для литерного поля - от строки пробелов, а для булевского - от значения "ложь". От этого недостатка свободны системы Paradox и R:base for DOS. В теории систем баз данных большое внимание уделяется средствам спецификации ограничений целостности данных как составной части модели данных. Ограничения целостности рассмат- риваются при этом как механизм моделирования семантики пердмет- ной области в базах данных. Hужно отметить, что возможности спецификации весьма примитивны. Обычно они ассоциируются не с объектами базы дан- ных, а с командами ввода или с полями форм ввода-вывода. При этом могут поддерживаться лишь простейшие ограничения. Hапри- мер, для данных количественных типов (числа, даты. денежные ве- личины) используются, как правило, ограничения, специжицирующ- щие возможные диапазоны изменения, а для литерных строк - шаб- лоны представления значений. В системе Clipper'87 эти возможности были усилены. До- пускается использование для верификации данных в команде ввода значения специфицированных пользователем функций. Аналогично в dBaseIV с окнами форм ввода-вывода могут ассоциироваться огра- ничения, заданные пользовательскими процедурами произвольного - - характера. Однако ограничения такого вида, ассоциируемые лишь с процессами ввода данных, не позволяют контролировать нарушения целостности базы данных "изнутри" - в процессах обработки зап- росов, а также поддерживать соотношения, связывающие значения множества различных компонентов базы данных. Более того, подоб- ного рода механизмы не дают возможности поддерживать более или менее нетривиальные зависимости допустимых множеств вводимых значений от состояния базы данных. Так, в dBase-совместимых системах нет эффективных средств, позволяющих поддерживать пер- вичный ключ отношений. Дубликаты кортежей включаются в отноше- ние, хотя индекс по значениям такого ключа с параметром UNIQUE и позволяет "спрятать" их от пользователя. Исключением является система R:base for DOS. В ней не только поддерживаются первичные ключи отношений (таблиц), но и предусмотрены средства спецификации довольно сложных ограниче- ний целостности, называемых правилами и ассоциируемых с атрибу- тами отношений. Их аргумент может быть множество значений атри- бутов в кортежах одного или нескольких отношений. Проверка та- ких ограничений осуществляется при выполнении всевозможных опе- раций обновления данных в базе данных независимо от того, выз- ваны ли они процессами ввода данных или внутрисистемными опера- циями. Аналогичные средства предусмотрены в системе ПАЛЬМА-ПК.