Содержание к диссертации
Введение
І. Упорядоченность данных в системах управления данными 13
1.1 Модели данных и поддержка семантики 13
1.2 Упорядоченность данных в моделях данных 16
1.2.1 Иерархическая и сетевая модели данных 16
1.2.2 Реляционная модель данных 18
1.2.3 Объектно-ориентированные модели данных 24
1.2.4 Расширение реляционной модели с учетом семантики 27
1.3 Реализация упорядоченности данных в СУБД 32
Выводы по первой главе .45
2 Разработка модели данных упорядоченного множества элементов на основе доменно-ориентированного подхода 4 6
2 .1 Последовательности данных 48
2 . 2 Операции над последовательностями 54
2.2.1 Семантика операций над линейно упорядоченными последовательностями 55
2.2.2 Семантика операций над частично
упорядоченными последовательностями 78
Выводы по второй главе 81
3 Реализация операций над упорядоченными данными в доменно-ориентированиой системе 82
3 .1 Модель навигации 82
3.2 Описание упорядоченности данных в доменно-ориентированной системе 87
3.3 Подход к проектирОБанию информационных систем, поддерживающих упорядоченность 88
3.4 Оценка применения методов реализации упорядоченности доменно-ориентированных структур 94
Выводы по третьей главе 99
Заключение 100
Список основных сокращений 102
Список использованных источников
- Упорядоченность данных в моделях данных
- Расширение реляционной модели с учетом семантики
- Семантика операций над линейно упорядоченными последовательностями
- Подход к проектирОБанию информационных систем, поддерживающих упорядоченность
Упорядоченность данных в моделях данных
Построение любой информационной системы подразумевает использование СУБД, оперирующей большими объемами данных. Структура данных системы, их поведение и связи между ними описываются с помощью модели данных.
Основной единицей организации и обработки данных в иерархической и сетевой модели данных служит запись (или группа данных), состоящая из элементов. Элемент данных - наименьшая {обычно поименованная) единица структуры данных, к которой СУБД может адресоваться. Элементы данных группируются в агрегаты данных поименованные совокупности элементов или более мелких входящих агрегатов. Запись - это агрегат, который не входит в состав никакого другого агрегата.
Наиболее распространенными способами упорядочения записей-членов являются: - сортированный (по ключу упорядочения) с направлением по убыванию или возрастанию; - хронологический {новая запись помещается в конец списка); - обратнохронологический (новая запись помещается в начало списка). .
Особенности учета упорядоченности в иерархической и сетевой моделях заключаются в следующем: - в иерархической модели данные организованы в иерархические структуры, точнее, в упорядоченные наборы нескольких экземпляров одного типа дерева [3], т.е. с математической точки зрения учитывается частичный порядок; - обработка данных начинается только с корневой записи, а доступ к некорневым записям обеспечивается только по иерархическому пути [13]; - в сетевой модели данных обработка может быть начата с записи любого типа независимо от её расположения в БД и от извлеченной записи возможны переходы, как к её подчиненным записям, так и к тем, которым она подчинена (реализация упорядоченности происходит Б момент вставки элемента, т.е. существуют операции вставить за элементом/перед ним) ; . .,- - отношения в сетевой модели характеризуются способом упорядочения подчиненных записей.
Основными понятиями реляционных баз данных являются тип данных, домен, атрибут, кортеж, первичный ключ и отношение [7] .
Понятие "тип данных" в реляционной модели данных полностью . адекватно понятию типа данных в языках программирования. Обычно в современных реляционных БД допускается хранение символьных, числовых данных, битовых строк, специализированных числовых данных (таких как "денежный тип"), а также специальных "темпоральных" данных (дата, время, временной интервал). Достаточно активно развивается подход к расширению возможностей реляционных систем абстрактными типами данных (соответствующими возможностями обладают, например, системы семейства Ingres/Postgres).
Понятие домена более специфично для баз данных, хотя и имеет некоторые аналогии с подтипами в некоторых языках программирования. В самом общем виде домен определяется заданием некоторого базового типа данных, к которому относятся элементы домена, и произвольного логического выражения, применяемого к элементу типа данных. Если вычисление этого логического выражения дает результат "истина", то элемент данных является элементом домена.
Расширение реляционной модели с учетом семантики
Современные реляционные СУБД ограничены в средствах поддержки упорядоченности данных [37,40]. Главная причина неэффективной работы реляционных СУБД с последовательностями заключается в плохой совместимости основ реляционной модели и природы упорядоченной последовательности данных. Одной из фундаментальных основ реляционной модели является понятие отношения -неупорядоченного множества кортежей [7 ] . Напротив, принципиальным свойством последовательности является упорядоченность ее элементов.
В любой реляционной СУБД кортеж отношения отображается на некоторую запись в файле операционной системы, содержащей данное отношение. Когда пользователь вводит запрос для извлечения кортежа из СУБД, СУБД отображает логическую запись на физическую, а затем помещает эту физическую запись в буфер СУБД в первичном устройстве хранения {оперативная память компьютера). Обычно физическая запись состоит из нескольких логических записей, хотя иногда, в зависимости от размера, одна логическая запись может соответствовать одной физической записи. Более того, одна логическая запись может даже соответствовать нескольким физическим записям. Иногда вместо понятия физическая запись используются термины блок и страница. Порядок хранения записей в файле и доступа к ним зависит от структуры (или организации) файла. Например,-если выборка строк с данными о сотрудниках компании должна выполняться по именам в алфавитном порядке, то наиболее подходящей структурой для хранения этих данных является фай;л, отсортированный по именам сотрудников.
В реляционных СУБД упорядоченность данных проявляется на физическом уровне, в попытке использования эффективной структуры хранения данных на внешнем устройстве, которая обеспечивает быструю загрузку базы данных, а затем ее преобразование в структуру, более подходящую для повседневной эксплуатации.
Но не все СУБД позволяют определить оптимальную файловую организацию для каждого отношения. Во многих, случаях реляционная СУБД может предоставлять лишь ограниченный выбор или даже вообще не позволять выбрать определенную файловую организацию, но в некоторых СУБД на организацию размещения данных на внешних устройствах можно в определенной степени повлиять путем задания индексов.
Рассмотрим особенности файловой организации и использования индексов в реляционных СУБД [16,50].
В первую очередь рассмотрим типы организации файлов. Порядок хранения записей в файле и доступа к ним зависит от структуры (или организации) файла.
Существуют следующие основные .типы организации файлов: - неупорядоченная организация файла предусматривает произвольное неупорядоченное размещение записей на диске; упорядоченная (последовательная) организация предполагает размещение записей в соответствии со значением указанного поля; в хешированием файле записи хранятся в соответствии со значением некоторой хеш-функции. Для каждого типа организации файлов используется соответствующий набор методов доступа {действия, выполняемые при сохранении или извлечении записей из файла)
Поскольку некоторые методы доступа могут применяться только к файлам с определенным типом организации (например, нельзя применять индексный метод доступа к файлу, не имеющему индекса), термины организация файла и метод доступа часто рассматриваются как эквивалентные.
Рассмотрим основные типы организации файлов.
Неупорядоченный файл (который иногда называют кучей) имеет простейшую структуру. Записи размещаются в файле в том порядке, в котором они в него вставляются. Каждая новая запись помещается на последнюю страницу файлаг а если на последней странице для нее не хватает места, то в файл добавляется новая страница.
Семантика операций над линейно упорядоченными последовательностями
Рассмотрим основные операции, определенные в модели данных, в которой над элементами (кортежами) отношения задается строгий порядок ( ) [38,41]. Применение в качестве основы для построения модели данных упорядоченного множества элементов - последовательности позволит естественным образом выразить такое важное семантическое свойство как упорядоченность, которое присуща организациям данных в- современных системах управления данными, в прикладных приложениях.
Формальное задание операций над последовательностями позволит специфицировать возможные преобразования над данными и разработать алгебраический язык манипулирования данными аналогично .реляционной алгебре[7] .
Выделим две группы операторов [38]:
1. Операции над последовательностями, аналогичные теоретико-множественным операциям: - объединение, - пересечение, - разность, - декартово произведение.
2. Специальные операции: - конкатенация, - селектирование (выборка), - проецирование, - соединение, , - деление. : .Все вышеперечисленные операции модифицированы с J \ учетом того, что их. операндами являются упорядоченные множества (S, ), а не произвольные множества.
Наряду с обобщенными операциями над последовательностями в системах управления данными рассмотрим и операции над отдельными элементами последовательностей. К таким операциям относятся: - операция включения элемента последовательности; - операция удаления элемента последовательности. Операция объединения последовательностей Рассмотрим последовательности Sx ={apa2,...,av) и S2=(bvb2,...,bw) из упорядоченного множества S. Операция объединения последовательностей S} и S2 предполагает дописывание в конец последовательности S: элементов из S2, отличающихся от элементов S}, при этом сохраняя порядок их следования. Операция обозначается- U .
Для наглядного представления операций над упорядоченными последовательностями удобно использовать графы. На рисунке 2.1 изображена операция объединения последовательностей. Пример 2.1 Пусть отношения Sx и S2 будут такими, как показано на рисунке 2.2 {отношение S] представляет штатных преподавателей. отношение преподавателей, работающих по совместительству) Тогда выражение S US (рисунок 2.2) представляет собой преподавателей, работающих или по штату, или по совместительству, при этом порядок следования элементов сохраняется. : .Операция обладает следующими свойствами: Г ,и52 Я21Д (2.11) Sl(]E = E[)S,=S]t (2.12) где Е - пустая последовательность S S S (2.13) 5,U ( ) = 6 )1) (2.14)
Докажем приведенные свойства. Доказательство свойства (2.11) 1. Возьмем произвольный х є O U ) о о 2 . Тогда х. е 5 или х. є 52, где ІФ j . о о 3. Возьмем тот же ІЄ (S2U]) 4. Тогда х. є 52 или JC . Ё5,, где ІФ j . Таким образом, исходя из п. 2 и п. 4, U S2U«S,, т.е. операция объединения не обладает свойством коммутативности. Доказательство свойства (2.12) D О 1. Возьмем произвольный х є (,1 ) . D 2. Тогда х є S} и только 5,, так как Е - пустая последовательность. о о 3 . Возьмем произвольный у є (ElJS ) . 4. Тогда у є Si и только Sx, так как Е - пустая последовательность.
Подход к проектирОБанию информационных систем, поддерживающих упорядоченность
В доменно-ориентированной системе для определения упорядоченности данных предложена следующая спецификация функций навигации.
Движение по заданному направлению навигации позволяет формировать маршрут. В каждом маршруте имеется возможность выбора подмаршрута. Домен содержит в своем описании определение маршрута (route): ROUTE идентификатор_маршрута [ имя_маршрута ]{ тип_направления; элементы_маршрута; . CHOICE; [SUBROUTE]; Для идентификации маршрутов в доменно-ориентированной системе управления для каждого маршрута генерируется уникальный идентификатор маршрута, представляющий собой внутрисистемный номер (ВСН) [29] . Для подмаршрутов генерируется идентификатор на основе маршрута родителя. По данному идентификатору можно однозначно определить, какие маршруты использовались в качестве базовых маршрутов.
Имя маршрута - это необязательный произвольно выбираемый уникальный идентификатор, помещаемый между служебным словом route и открывающейся фигурной. скобкой " ["
Тип направления определяет вектор движения по элементам маршрута. Выделены такие типы как 1) next следующий элемент; 2) prev-предыдущий элемент; 3) тах-конечный элемент; 4)min-начальный элемент. . .Служебное слово CHOICE представляет собой функцию выбора движения по маршруту. Дл определения подмаршрута используется служебное слово SUBROUTE. Пример 3.2 Описание маршрута для домена, графическая интерпретация которого приведена на рисунке 3.2 следующее: ROUTE 101 «Расписание групп ПЭ»{ next; занятие 1 і 6 ; CHOICE { время, аудитория, контингент: занятиеі+ }; } Параметрами функции выбора движения по маршруту являются время проведения занятия, номер аудитории, контингент учащихся.
В качестве языка проектирования доменно-ориентированных информационных систем поддерживающих упорядоченность используем унифицированный язык моделирования UML.
Унифицированный язык моделирования UML - это широко признанный стандарт описания объектно ориентированных систем. Консорциум OMG определил язык UML как стандартный язык моделирования [ 61] . UML используется для описания моделей сложных систем графическим способом [2] . Заметим, однако, что UML не является методологией разработки программного обеспечения.
При использовании доменно-ориентированного подхода любая информационная система (ИС) строится из набора заранее подготовленных компонент - доменов [30]. В разработке самих доменов эффективно используется СОМ-технологии. СОМ-объект считается полноценным доменом, предоставляющим базовый набор интерфейсов [ 6 ] . В процессе разработки систем на основе доменов необходимо создать компонентную модель предметной области и включить доменные интерфейсы в объектную модель. Стандартный язык UML предлагает подобные концепции -интерфейс и компонент [2,44] . Компонент описывает физическую структуру компонентов программного обеспечения информационной системы. Он представляет исполняемую единицу кода, обеспечивающую инкапсуляцию соответствующих служб. Доступ к службам, предоставляемым компонентом, осуществляется с, помощью интерфейса. Компоненты взаимодействуют с другими компонентами-через отношения зависимости [2].
