Содержание к диссертации
Введение
Глава 1. Анализ моделей и методов хранения и обработки сложно структурированных данных во внешней памяти 14
1.1 Проблема хранения сложно-структурированных данных программных приложений во внешней памяти 14
1.2 Анализ методов и средств хранения сложно-структурированных данных во внешней памяти 15
1.3 Анализ моделей баз данных и систем управления базами данных 18
1.4 Анализ подходов к отображению сложно-структурированных данных в реляционные базы данных 32
Выводы по главе 1 43
Глава 2. Модель преобразования нагруженных псевдографов в РБД 45
2.1 Описание нагруженных псевдографов 45
2.2 Операции модели преобразования псевдографов в РМД 51
2.2.1 Операция преобразования доменов псевдографа в домены РМД 52
2.2.2 Операции преобразования множества вершин и множества типов вершин в набор реляционных отношений 55
2.2.3 Операции преобразования множества ребер и множества типов ребер в набор реляционных отношений 58
2.2.4 Операция преобразования множества ограничений псевдографа в множество ограничений РМД 60
2.3 Правила изменения набора отношений РМД 61
2.4 Пример преобразования псевдографа в РМД 66
Выводы по главе 2 69
Глава 3. Преобразование фундаментальных структур данных в РБД 70
3.1 Отображение списков в РМД 70
3.1.1 Отображение односвязных списков в РМД 70
3.1.2 Отображение двусвязных списков в РМД 74
3.1.3 Отображение циклических списков в РМД 78
3.2 Отображение стеков и очередей в РМД 79
3.3 Отображение одномерных и ассоциативных массивов, множеств и мультимножеств в РМД 80
3.4 Отображение бинарных деревьев в РМД 83
3.5 Отображение сильно ветвящихся деревьев в РМД 87
3.6 Отображение графов в РМД 90
3.7 Отображение файловой системы в РМД 91
3.8 Отображение иерархии компонентов ПО SCADA-систем в РМД 95
Выводы по главе 3 99
Глава 4. Анализ эффективности модели преобразования 101
4.1 Теоретическая эффективность операций со структурами данных 101
4.1.1 Краткое описание операций со структурами данных 103
4.1.2 Простая таблица 111
4.1.3 Односвязный список 114
4.1.4 Сводная таблица оценки эффективности операций со структурами данных 120
4.2 Программное приложение Collection Statistics 122
4.2.1 Руководство пользователя приложения Collection Statistics 125
4.2.2 Описание общего алгоритма тестирования операций со структурами данных 133
4.3 Экспериментальное подтверждение эффективности модели преобразования псевдографов в РБД 137
Выводы по главе 4 144
Заключение 146
Литература
- Анализ методов и средств хранения сложно-структурированных данных во внешней памяти
- Операция преобразования доменов псевдографа в домены РМД
- Отображение двусвязных списков в РМД
- Краткое описание операций со структурами данных
Введение к работе
За последнее время компьютерные технологии проникли практически во все области человеческой деятельности. Сегодня их можно встретить в офисе, на работе, дома, на улице. Мобильные компьютерные устройства, такие как сотовые телефоны, карманные компьютеры, МРЗ-штейеры и т.д., окружают человека повсюду, куда бы он не пошел.
Все цифровые устройства, от суперкомпьютеров до кофеварки, требуют разработки программного обеспечения (ПО). ПО сегодня применяется в АСУТП и АСУП, обработке гео-информации, аналитической обработке данных реального времени (OLAP), оперативной обработке транзакций (OLTP), поддержке принятия решений (DSS), обучающих системах [6], различной офисной финансовой и бухгалтерской деятельности, а также в развлекательной индустрии (игры, фильмы, музыка) и т.д.
Одной из проблем, которую приходится решать при разработке программного обеспечения (ПО) — это хранение и обработка информации в долговременной памяти [134]. При этом информация должна легко, быстро и в удобном для использования виде извлекаться из хранилища, обрабатываться и помещаться обратно.
Внутри программного обеспечения информация представляется в виде сложно-структурированных данных: объектов, коллекций объектов, всевозможных связей между ними, а также в виде сложных структур — массивов, списков, деревьев и т.д. Таким образом, на современном этапе развития программной индустрии, актуальной является задача обработки в долговременной памяти объектов, коллекций объектов, связей между ними и структур данных [134].
Для решения этой задачи существует несколько подходов:
- использование плоских файлов и ПО для управления ими;
- использование специализированных хранилищ, таких как Storage от Microsoft;
- использование систем управления базами данных (СУБД). Первый подход требует разработки ПО для управления плоскими файлами и данными. Второй подход также требует создания промежуточного ПО между приложением и хранилищем. Оба подхода обладают слабой интероперабильностьто к другим способам и средствам хранения данных. СУБД лишены этих недостатков, так как предоставляют готовые и универсальные интерфейсы для обработки данных.
На сегодняшний момент существует несколько типов СУБД: объектно-ориентированные, иерархические, сетевые, реляционные. Каждый из типов СУБД обладает своими достоинствами и недостатками. Объектно-ориентированные СУБД хорошо работают с объектами и коллекциями объектов, но не имеют универсальных и стандартизованных интерфейсов обработки данных. Иерархические и сетевые СУБД предназначены для обработки иерархий и сетей соответственно, но для работы с неиерархическими или несетевыми данными требуют разработки специализированных жестко определенных запросов. Реляционные СУБД (РСУБД) обладают неоспоримыми преимуществами по сравнению с другими: основаны на формальной математической модели, являются своего рода стандартом хранения данных, занимают львиную долю рынка СУБД. В то же время РСУБД, как и другие СУБД (иерархические, сетевые и объектные), непосредственно не поддерживает хранение и обработку сложных структур данных, таких как списки, массивы, деревья, графы, стеки и очереди.
Коллекции объектов и структуры данных являются подмножеством графов, которые, в свою очередь, являются подмножеством мультиграфов (графов с кратными ребрами) и псевдографов (мультиграфов с петлями).
Исследованиям мультиграфов и псевдографов посвящены работы Касьянова В.К [20], Евстигнеева В.А. [20], Акимова О.Е, [3], Харари Ф. (Harary F.) [1], Звиллингера Д. (Zwillinger D.) [2].
Указанные выше обстоятельства обуславливают выбор в качестве объекта исследования реляционных баз данных (РБД), в основе которых лежит реляционная модель данных (РМД). Данная работа направлена на решение проблемы обработки сложно-структурированных данных о предметной области, представленных в виде нагруженного псевдографа, в РБД. Нагруженный псевдограф означает, что его вершины и ребра являются объектами, имеющими собственную сложную структуру, состоящую из множества атрибутов.
Каждый атрибут характеризуется именем атрибута и доменом, к которому принадлежит атрибут. Домен - определяемый пользователем тип данных. Каждый атрибут можно определить только на одном домене. Под доменом понимаются как простые, скалярные типы данных, такие как числа, строки символов, даты и время, так и сложные типы данных (сложные домены), такие как массивы, множества, списки, деревья, которые в свою очередь содержат элементы, состоящие из множества атрибутов [15].
В качестве предмета исследования была выбрана модель преобразования сложно-структурированных данных о предметной области, представленных в виде нагруженного псевдографа, в РБД, а также методы и средства обработки сложных структур данных в рамках РБД.
Цель работы - ускорение процесса разработки программных средств, предназначенных для обработки сложно-структурированных данных о предметной области, с помощью формализации и автоматизации преобразования нагруженных псевдографов в реляционные базы данных.
Поставленная цель была решена с помощью разработки модели
преобразования структурированных данных, организованных в виде псевдографов с нагруженными вершинами и ребрами, в реляционную модель данных; разработки метода преобразования на примерах фундаментальных структур данных; разработки программных средств, предназначенных для работы с этими структурами данных.
Задачи исследования. Для достижения поставленной цели были решены следующие задачи:
1. Исследование существующих способов хранения и средств обработки информации в долговременной памяти для ускорения процесса разработки программных средств, предназначенных для работы со сложноструктурированными данными во внешней памяти.
2. Разработка метода и средств преобразования сложноструктурированных данных в РБД, позволяющих формализовать и автоматизировать разработку программных средств обработки данных во внешней памяти. 3. Разработка метода и средств преобразования в РБД фундаментальных структур данных: массивов, списков, стеков, очередей, бинарных и сильно ветвящихся деревьев, графов, — а также файловой системы и иерархии компонентов ПО SCADA-систем.
4. Разработка программных инструментальных средств для работы с фундаментальными структурами данных в РБД.
5. Оценка эффективности преобразования фундаментальных структур данных в РБД на основе соотношения количества операторов реляционной алгебры и среднего времени выполнения операций обработки данных.
Методы исследования данной работы основаны на методах формальной логики, теории множеств и теории графов. Для теоретической оценки производительности операций с отображенными в РБД структурами данных использовалась реляционная алгебра. При разработке модели преобразования нагруженных псевдографов и программного обеспечения использовался объектно-ориентированный подход.
Научная новизна работы состоит в следующем:
1. Обосновано использование РБД и РСУБД для долговременного хранения и обработки сложно-структурированных данных, которые можно представить в виде нагруженного псевдографа. Применение РБД и РСУБД позволяет ускорить разработку программных средств обработки данных во внешней памяти.
2. Разработана формальная модель преобразования сложноструктурированных данных, представленных в виде нагруженного псевдографа, которая позволяет формализовать и автоматизировать отображение данных о предметной области в РБД.
3. Разработаны правила изменения набора реляционных отношений, полученного в результате применения формальной модели преобразования, с целью повышения быстродействия операций обработки данных и уменьшения занимаемого места во внешней памяти.
4. Предложен метод и средства отображения фундаментальных структур данных в РБД, основанные на модели преобразования нагруженных псевдографов, с помощью которых было осуществлено преобразование в РБД массивов, списков, стеков, очередей, бинарных и сильно ветвящихся деревьев, графов, - а также файловой системы и иерархии компонентов ПО SCADA-систем.
5. Разработаны программные инструментальные средства, позволяющие ускорить процесс разработки программ, программных комплексов и пакетов прикладных программ, предназначенных для обработки сложноструктурированных данных о предметной области в РБД.
Практическая значимость работы заключается в следующем:
1. Для разработки систем обработки данных созданы программные инструментальные средства: набор хранимых процедур на языке Transact-SQL и программные инструментальные средства для создания программ, программных комплексов и пакетов прикладных программ в виде динамически подключаемой библиотеки прикладного программиста, - позволяющие ускорить процесс разработки программных средств, предназначенных для обработки сложно-структурированных данных в РБД.
2. Результаты теоретических исследований приведенных в работе нашли практическое применение при разработке различных систем обработки информации.
3. Разработанная модель преобразования нагруженных псевдографов в РБД, методы и программные средства могут быть использованы для создания программного обеспечения, позволяющего автоматически осуществлять преобразование заданных в виде нагруженного псевдографа данных о предметной области в РБД.
Реализация результатов работы. Основные результаты работы были
использованы при разработке следующих программных систем:
- информационная система «Приемная руководителя» внедрена и используется в приемной Губернатора Пензенской области (г. Пенза), что подтверждается соответствующим актом [149];
- «Система управления несоответствиями программного обеспечения» внедрена в ООО НПФ «КРУГ» (г. Пенза), применяется при разработке ПО АС УТЛ для предприятий нефтехимической и газовой промышленности, а также для объектов энергообеспечения, что подтверждается соответствующим актом [147, 152];
- информационная система «Формирование правил оплаты, учет и анализ платежей потребителей электроэнергии» внедрена и используется в районном электротеплосетевом предприятии Городище не кого района Пензенской области (г. Городище), что подтверждается соответствующим актом.
Содержание работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка используемой литературы и пяти приложений.
В первой главе исследуются методы и средства хранения во внешней памяти сложно-структурированных данных, накапливаемых и обрабатываемых программным приложением. Показано, что наиболее эффективным средством является РСУБД. Производится анализ существующих подходов к отображению в РБД сложно-структурированных данных. Делается вывод о недостаточной общности и формализации существующих подходов. Определяется направление исследований, задачи и пути их решения.
Во второй главе дано определение нагруженного псевдографа. Описывается формальная модель преобразования нагруженных псевдографов в РБД. Рассмотрена проблема отображения в РБД сложного домена, представляющего собой набор однотипных элементов. Приводятся правила изменения набора реляционных отношений, полученного в результате преобразования псевдографа в РБД.
В третьей главе приводятся примеры отображения в РБД фундаментальных структур данных: массивов, списков, стеков, очередей, бинарных и сильно ветвящихся деревьев, графов, - а также файловой системы и иерархии компонентов ПО SCADA-систем.
В четвертой главе производится оценка эффективности предлагаемой модели на основе производительности операций со структурами данных, отображение которых в РБД было рассмотрено в третьей главе. Производится теоретическая оценка производительности таких операций манипулирования отображенными в РБД структурами данных, как добавление, удаление, обновление и поиск элемента(ов). Выясняется на сколько больше нужно выполнить операторов реляционной алгебры, необходимых для операций работы со структурами данных, по сравнению с количеством операторов реляционной алгебры, необходимых для работы с простым отношением. Под простым отношением понимается реляционное отношение, состоящее из кортежей с такими же атрибутами, как и у элементов структуры данных, сравниваемой с этим отношением.
Далее в главе описывается программа Collection Statistics, позволяющая тестировать производительность операций обработки преобразованных в РБД структур данных и экспериментально проверять эффективность предлагаемой модели преобразования. В завершении главы приводится анализ результатов экспериментального тестирования производительности операций со структурами данных, преобразованными в РБД.
В заключении приводятся основные результаты работы.
В Приложении А приводится описание динамически подключаемой библиотеки прикладного программиста и хранимых процедур на языке Transact-SQL, разработанных для обработки фундаментальных структур данных, преобразованных в РБД, и использованных при разработке программы Collection Statistics и других информационных систем, акты, о внедрении которых приведены в Приложении Д.
В Приложениях Б и В приводятся трехмерные графики экспериментального тестирования отображенных в РБД структур данных (коллекций) размером от 500 до 100000 элементов. Каждый трехмерный график представляет собой зависимость среднего времени выполнения операции (добавления, удаления, обновления и поиска элемента(ов)) в каждой из рассмотренных структур данных от количества элементов в коллекции и размера информационных атрибутов элементов коллекции,
В Приложении Г приводятся двумерные графики зависимости среднего времени выполнения операции (добавления, удаления, обновления и поиска элемента(ов)) всех структур данных от количества элементов в коллекции и заданного размера информационных атрибутов элементов коллекции.
Теоретические исследования, изложенные в работе, доведены до практического применения. Акты о внедрении результатов диссертационной работы приведены в Приложении Д.
Апробация работы. Основные положения и результаты работы докладывались на:
- Международной научно-технической конференции «Проблемы автоматизации и управления в технических системах», г. Пенза, 2004 г.;
- Международном юбилейном симпозиуме «Актуальные проблемы науки и образования», г. Пенза, 2004 г.;
- V международной научно-технической конференции «Новые информационные технологии и системы», г. Пенза, 2002 г.;
- VII международной научно-методической конференции «Университетское образование», г. Пенза, 2003 г.;
- VI международной научно-методической конференции «Университетское образование», г, Пенза, 2002 г.;
- V международной научно-методической конференции «Университетское образование», г. Пенза, 2001 г.;
- IV международной научно-методической конференции «Университетское образование», г, Пенза, 2000 г.;
- Студенческой межвузовской научной конференции «Гуманитарные науки в системе высшего образования», г. Пенза, 2001 г.
Основные положения диссертационной работы, выносимые на защиту:
1. Формальная модель преобразования сложно-структурированных данных о предметной области, представленных в виде нагруженного псевдографа, в котором вершины и ребра являются объектами, имеющими собственную сложную структуру, в набор отношений реляционной базы данных. Данная модель позволяет формализовать и автоматизировать отображение сложно-структурированных данных о предметной области в реляционную базу данных, что существенно ускоряет разработку программных средств обработки данных во внешней памяти.
2. Правила изменения набора реляционных отношений, полученного в результате применения формальной модели преобразования, с целью повышения быстродействия операций обработки данных и уменьшению занимаемого места во внешней памяти.
3. Метод и средства преобразования фундаментальных структур данных в реляционную модель данных, позволившие преобразовать в реляционную базу данных массивы, списки, стеки, очереди, бинарные и сильно ветвящиеся деревья, графы, - а также файловую систему и иерархию компонентов программного обеспечения SCADA-систем, что ранее не было формализовано.
4. Оценка эффективности преобразования фундаментальных структур данных на основе соотношения количества операторов реляционной алгебры и среднего времени выполнения операций обработки данных в реляционных базах данных, подтверждающая эффективность предложенных модели, методов и средств.
5. Программные инструментальные средства, позволяющие ускорить процесс разработки программ, программных комплексов и пакетов прикладных программ, предназначенных для обработки сложно-структурированных данных о предметной области в реляционную базу данных.
Публикации. По теме диссертации опубликованы шестнадцать печатных работ. Список публикаций приведен в разделе Литература.
Анализ методов и средств хранения сложно-структурированных данных во внешней памяти
Для решения задачи хранения сложно-структурированных данных программных приложений существует несколько подходов. 1. использование плоских файлов и ПО для управления ими; 2. использование специализированных хранилищ; 3. использование систем управления базами данных.
Плоские файлы - это обыкновенные файлы, в которых по определенным правилам хранятся наборы записей данных. Правила, по которым хранятся данные, называются форматом файла. Формат файла разработчик ПО создает сам или пользуется уже существующими форматами, например, DBF - файлы данных dBASE, CSV - файлы данных Microsoft Excel, XML - файлы данных, используемые в Internet-приложениях.
Специализированные хранилища являются расширением плоских файлов: это уже не только формат файла, но и ПО для обработки записей в файлах с заданным форматом. Одним из примеров такого хранилища может служить Storage, разработанный корпорацией Microsoft, который представляет собой встроенный во все операционные системы Windows механизм работы со структурированными файлами. Этот механизм позволяет разработчику не задумываться о формате файла, а манипулировать потоками данных. На основе Storage Microsoft разработала формат DOC-файлов, используемый в текстовом редакторе Word.
Одной из разновидностей специализированных хранилищ являются встроенные системы баз данных, которые можно использовать в приложениях, нуждающихся в высокопроизводительном механизме хранения и извлечения пар ключ-значение, поддерживающем одновременный доступ. Одним из таких продуктов является BerkeleyDB [115], которая предоставляет механизм хранения независящий ни от одной модели баз данных, рассматриваемых ниже в этой главе. Но на основе подобного механизма можно разработать СУБД любого типа.
Использование плоских файлов требует разработки формата плоских файлов и программного обеспечения для управления этими файлами и данными, которые будут храниться в них.
Для второго подхода не нужно разрабатывать формат файлов, но требуется создание промежуточного ПО между Вашим приложением и ПО, управляющим хранилищем.
Оба подхода обладают слабой интероперабильностью к другим способам и средствам хранения данных, то есть они не предоставляют универсальных интерфейсов для доступа к хранимым с их помощью данным. Поэтому, для передачи данных другим приложениям, о которых не было известно на этапе разработки программного обеспечения, управляющего хранилищем, придется создавать программные шлюзы.
При использовании первых двух подходов возникают проблемы совместного доступа и безопасности данных. Отвечающие за это программные компоненты придется разрабатывать самому.
Все это приводит к чрезмерным затратам времени и людских ресурсов на разработку ПО. СУБД предоставляют готовые и универсальные интерфейсы для управления и обработки данных, к ним по этим интерфейсам может обратиться любое стороннее приложение. В большинстве современных СУБД уже решены проблемы совместного доступа и безопасности данных.
Недостатком СУБД является то, что, в отличие от первых двух подходов, они требуют установки на компьютеры пользователей дополнительного ПО (ядра СУБД, клиентской части СУБД и т.д.). ПО для работы с плоскими файлами обычно входит в программные приложения, работающие с ними, и поэтому не требует дополнительной установки. ПО для работы со специализированными хранилищами обычно является частью операционной системы (ОС), например, Storage от Microsoft, и поэтому также не требует установки на компьютер пользователя.
Вторым недостатком использования СУБД является необходимость изучения универсальных средств управления и обработки данных в них, например, языка SQL.
Приведенные достоинства и недостатки подходов позволяют сделать следующий вывод о том, что использование СУБД позволяет сократить время и людские ресурсы на разработку программного приложения, так как современные СУБД представляют универсальные интерфейсы доступа к данным, позволяют осуществлять совместную работу с данными, предоставляют средства управления безопасностью данных. В то же время установка большинства СУБД происходит в автоматическом режиме, не требуя больших знаний от пользователя, а знание универсальных средств управления и обработки данных, таких как язык SQL, является обязательным для большинства разработчиков ПО, связанного с хранением данных.
Операция преобразования доменов псевдографа в домены РМД
Преобразование множества типов вершин в РМД и преобразование множества типов ребер в РМД включают в себя преобразование доменов псевдографа в домены реляционной модели данных. Преобразование доменов, к которым относятся атрибуты типов вершин и типов ребер псевдографа, в домены РМД можно записать следующим образом. PD: DG - DPm (2.8) где D - множество доменов типов вершин и типов ребер псевдографа; Г/мд - множество доменов реляционной модели данных; 0D - функция преобразования DG в Г/мд.
Все простые домены из множества D отображаются в соответствующие простые домены из множества [/мд. Например, целые числа отображаются в целые числа, действительные - в действительные, строковые в строковые и т.д.
Если какие-либо простые домены из множества D отсутствуют в множестве if д (например, домен дата/время, домен деньги и т.д.), то они отображаются в наиболее подходящие для них домены из іУмд. Например, домен деньги отображается в домен действительных чисел, или в два домена целых чисел: первый отвечает за целую часть денег, а второй за дробную. Домен дата/время можно отобразить в строку, в которую разрешено записывать только дату и время, или в шесть доменов: домен лет, домен месяцев, домен дней, домен часов, домен минут, домен секунд. nG _ Прмд Г? ОЛ J- simple LJ simple v "-7)
В множестве DG могут присутствовать сложные домены, которые невозможно отобразить средствами современных СУБД в один из простых доменов РМД. Обычно это домены, где каждое значение домена само является набором (упорядоченным или неупорядоченным) элементов, где каждый элемент состоит из множества атрибутов, принадлежащих простым или сложным доменам. Например, домен, где каждое значение является списком деталей, и каждая деталь обладает несколькими свойствами или атрибутами, которые в свою очередь могут быть списками, множествами, деревьями и т.д.
Таким образом, сложные домены отображаются уже не в домены, а в наборы отношений РМД. В [72] показана принципиальная возможность разложения любого сложного объекта (в нашем случае домена) в набор отношений.
Пусть в множестве Ту некоторого псевдографа G существует некоторый тип вершины TVJ!={ AJ:DJ , A2:D2 , ... , An:Dn }, где 1 j m, m -количество типов вершин в Ту, п - количество атрибутов в Ту . Существует некоторая пара Ak:Dk \ I к п, такая, что йк Г/мд, причем Dk - один из сложных доменов, например, список или множество. Значения этого домена состоят из набора атрибутов, принадлежащих простым доменам, которые прямо отображаются в множество
В этом случае сложный домен предметной области отображается в определенный набор реляционных отношений, который будем обозначать complex- В каждом таком наборе присутствует главное отношение Rgenerai и несколько подчиненных отношений, в которые отображаются атрибуты элементов сложного домена. В отношении Rgenerai есть атрибут номер значения, обозначаемый далее JVvfl/, из домена Did, который является идентификатором конкретного значения домена Dk. Для того чтобы связать полученный набор отношений с атрибутом конкретной вершины типа Ту , необходимо во всех отношениях данного типа вершины атрибут Ak:Dk заменить на атрибут Nvai:Did и связать его как внешний ключ с атрибутом Nvai:Dici из главного отношения сложного домена. Такие рассуждения правомерны и для сложных доменов встречающихся в описаниях типов ребер. D complex— {Rgeneral{ NVai:Did , А; Dj , A2 lD2 , ..., Aj:Dnll }, R2{ A,2:D,2 , A22:D22 , ... , An22:Dn22 }, ... , (2.10) Rm{ A,m:Dr , A2m:D2m , ..., Anmm:Dnmm }} где Rgenerai — первое и одновременно главное отношение сложного домена; 2 і т; т - количество отношений, в которые отображается сложный домен; Ri - отношения, в которые отображается сложной домен; Aj:Dj - название и домен атрибута соответствующего отношения Ri-, 1 j пі; пі - количество атрибутов в отношении Rh
Задача определения, в каком наборе отношений искать значение атрибута сложного домена, целиком ложится на составителя запросов, т.е. на разработчика. Хотя можно ввести и набор отношений, хранящий метаинформацию о расположении сложных доменов.
Возможна ситуация, когда атрибуты элемента сложного домена также принадлежат сложным доменам, тогда повторяем вышеперечисленные действия для каждого из этих атрибутов, пока не дойдем до простых доменов.
Для отображения сложных доменов используются, как будет показано в главе 3, другие операции предложенной модели, что приводит к рекурсивности определения данных. Так как для представления данных более низкого уровня используются те же методы и подходы, что и для представления данных более высокого уровня. Все это приводит к мысли о фрактальной природе данных и знаний. Подобная проблема рассматривается в [153] при рассмотрении отображения фрактальной структуры электронных учебных курсов в реляционную базу данных. Преобразование множества вершин: 0v:V- Bv (2.11) где Фу— функция отображения VBRV. Преобразование множества типов вершин: ФТу:Ту- ВТу (2.12) где Фту - функция отображения Ту В RTy.
Операции преобразования множества вершин V и множества типов вершин Ту в набор реляционных отношений рассматриваются вместе, так как они очень тесно взаимосвязаны.
При выполнении данных операций считается, что все домены атрибутов уже отображены в домены РМД, так как операция преобразования доменов уже выполнена на предыдущем шаге. Для отображения вершин в РМД вводится понятие главного отношения вершин, которое обозначается как Rygenerai- Оно имеет следующую структуру: R veenerai— Номер псевдографа: D,d ,
Отображение двусвязных списков в РМД
Ассоциативный массив - это один из самых полезных и универсальных типов, определяемых пользователем. Фактически, в языках, занимающихся главным образом обработкой текстов и символов, это зачастую встроенный тип. Ассоциативный массив, часто называемый отображением (тар), а иногда словарем (dictionary), содержит пары значений. Зная одно значение, называемое ключом, мы можем получить доступ к другому, называемому отображенным значением. Ассоциативный массив можно представить как массив, для которого индекс не обязательно должен иметь целочисленный тип.[32]
Для создания ассоциативных массивов, достаточно реляционного отношения, в котором один или несколько атрибутов являются ключом, а остальные атрибуты - значением. По ключевым атрибутам нужно создать уникальный индекс, если по одному ключу может находиться только одно значение, или неуникальный индекс в случае, если один ключ может указывать на несколько значений.
Для отображения в РМД множеств не нужно никаких ухищрений, так как реляционное отношение и есть множество. В теории РМД это так и есть, но в реляционных СУБД в одной таблице допустимы повторения записей. Поэтому в РСУБД придется устанавливать уникальные индексы по какому-то подмножеству полей таблицы, чтобы хранить в ней множество. Зато таких проблем не возникает при хранении в таблицах мультимножеств. Но возникают проблемы в теории РМД, так как в ней запрещено наличие нескольких одинаковых кортежей в одном реляционном отношении. Поэтому в РМД для отображения мультимножества понадобиться ввести суррогатный атрибут (ключ), уникально определяющий каждый кортеж.
Как известно, в деревьях элементы называются вершинами или узлами. В бинарных деревьях каждый узел хранит указатели на левого и правого потомков, а также информационную часть. Если узел имеет хотя бы одного потомка, то он иногда называется «веткой». В узлах, не имеющих потомков, указатели на потомков являются нулевыми. Такие узлы называются «листьями».
Бинарное дерево (см. рисунок 3.9) отличается тем, что у каждой вершины может быть только две связи (ребра): указатель на левого потомка и указатель на правого потомка.
Так как число типов ребер равно двум, оба типа ребра не содержит информационных атрибутов и количество ребер каждого типа, начинающихся в одной вершине графа, ограничивается одним ребром, то по правилу 5 : V,E, TE- Rvgenerai{ NG:Did , Nv:Daid , Nleft:Did , Nright:Did Tun:DVtype }. В результате применения правила 5 атрибут Nend первого типа ребра был заменен на атрибут Nie/t {Указатель на левого потомка), атрибут Nend второго типа ребра был заменен на атрибут Nright {Указатель на правого потомка), а атрибут N begin был заменен на Ny:Daid.
Сильно ветвящиеся (или М-арные [20]) деревья (см. рисунок 3.11) отличаются от бинарных тем, что количество потомков у одной вершины неограниченно.
Если точно известна арность дерева, т.е. максимальное количество потомков для каждого элемента дерева, то можно по 5 правилу добавить в Rgenerai М атрибутов, указывающих на потомков данной вершины. Но это «расточительно» в случае редкого дерева. Также можно хранить указатель на предка, как описывалось выше для бинарных деревьев. Построение псевдографа для сильно ветвящегося дерева. Т (V, Е, Tv, ТЕ, О) - сильно ветвящееся дерево. V— конечное множество вершин; \Tv\=3; Ту1 - корневая вершина дерева; Ту2 - средняя вершина дерева; Ту3 - листовая вершина дерева; Е — множество ребер \Е\ = \V\ - 1; \тЕ\ = /; ТЕ = {} - предок-потомок; Ту = { Aj:D] } 1 i 3,Dj — строка символов.
Краткое описание операций со структурами данных
Для тестирования производительности операций со структурами данных, отображенными в РМД, было разработано программное обеспечение. Отображение структур данных было описано в третьей главе, операции со структурами данных были описаны в первом пункте четвертой главы, результаты тестирования будут описаны в пункте 4.3, следующим за этим. В данном же параграфе речь пойдет непосредственно о ПО.
ПО реализовано в виде клиент-серверной системы (смотрите рисунок 4.1). В качестве сервера выступает Microsoft SQL Server 2000, в качестве клиента выступает приложение, названное Collection Statistics (Статистики коллекций, далее CS).
Приложение CS разработано в Microsoft Visual Studio .NET 2003 на языке Microsoft Visual C++ с использованием WTL (Windows Template Library -библиотеки предназначенной для упрощения процесса создания графического интерфейса в программах, написанных для Windows[133]) и STL (Standard Template Library [28, 29, 32]).
CS связывается с SQL Server oM через Microsoft ADO (ActiveX Data Objects) - новейший объектно-ориентированный интерфейс для работы с базами данных и другими аналогичными источниками данных. После выхода Microsoft Visual Studio .NET все новые версии ADO называются ADO.NET. ADO содержит описание объектов, которые можно использовать для работы с данными многих различных типов приложений. ADO опирается на интерфейс Common Object Model (СОМ), содержащий объекты, доступные для широкого спектра языков программирования, включая Visual C++, Visual Basic, Visual Basic for Applications (VBA), VBScript и JavaScript. ADO также можно использовать в серверных или приложениях промежуточного типа, особенно при работе с Active Server Pages (ASP и ASP.NET) компании Microsoft. [7, 17]
CS использует для связи с SQL Server ом динамически подключаемую библиотеку Structures.dll, подробно описанную в приложении А.
При проектировании CS использовались шаблоны проектирования, описанные в [10, 12]. Информация, используемая для работы с Microsoft SQL Server 2000 и Microsoft Access, была взята из [5, 7, 8, 13, 17, 93, 112, 132, 135, 136]. При программировании на C++ использовалась следующая справочная
Но приложение Collection Statistics только половина программного обеспечения, необходимого для работы с коллекциями. Вторая часть ПО -хранимые процедуры Microsoft SQL Server а, написанные на языке Transact-SQL - внутреннем языке SQL Server a, являющегося расширением стандартного языка SQL-92. Описание хранимых процедур для работы с коллекциями приводилось в первом разделе четвертой главы, здесь же достаточно сказать, что для каждой тестируемой коллекции были написаны хранимые процедуры и скомпилированы на MS SQL Server e. Таким образом, обобщенная схема работы тестирующего ПО выглядит следующим образом: CS вызывает посредством ADO хранимую процедуру, этот запрос пересылается SQL Server y, который уже у себя запускает на выполнение эту хранимую процедуру. После выполнения хранимой процедуры SQL Server посредством ADO пересылает результат ее выполнения в CS, где он и анализируется.
CS позволяет тестировать 15 коллекций. Для каждой из них был создан на C++ класс обертка, инкапсулирующий все операции работы с соответствующей структурой. Операции превратились в функции соответствующих классов и далее слово «функция» будет использоваться в качестве синонима слова «операция». Функции этих классов, используя механизмы ADO, вызывают соответствующие хранимые процедуры на SQL Server e. Выше приводится в таблице 4.11 список коллекций, реализованных в CS и соответствующие им названия классов, так как эти имена используются в интерфейсе CS.
Для того, чтобы воспользоваться программой Collection Statistics необходимы предварительные настройки. А именно, необходимо установить Microsoft SQL Server 2000 любой редакции так, чтобы к нему можно было получить доступ с клиентского приложения, для этого он должен быть установлен либо на тот же компьютер, что и CS, или быть доступным через локальную сеть. После установки на SQL Server e необходимо запустить SQL-скрипты для создания базы данных Structures, таблиц, индексов и хранимых процедур, необходимых для работы с коллекциями (структурами данных). На машине, где Вы будете запускать Collection Statistics, нужно установить Microsoft ADO версии 2.6 и выше (В Windows ХР оно уже установлено, а также его можно установить с диска, с которого была произведена установка Microsoft SQL Server 2000). Только после этого стоит запускать CS (cs.exe -одного этого файла достаточно для работы клиента).
