автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Векторно-матричная модель представления данных и ее реализация в иерархических структурах

Сергеев Виктор Петрович

Векторно-матричная модель представления данных и ее реализация в иерархических структурах

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

1 2 МАЙ 2011

Москва 2011

4845494

Работа выполнена в Учреждении Российской академии наук Институт проблем информатики РАН

Научный руководитель:

- доктор технических наук, профессор Левин Нисон Абрамович

Официальные оппоненты:

- доктор технических наук, профессор Дулин Сергей Константинович

- кандидат технических наук Борисов Петр Васильевич

Ведущая организация:

- Общество с ограниченной ответственностью Институт электронных управляющих машин им. И.С. Брука

Защита состоится 2011 г. в ^часов на заседании

диссертационного совета Д002.073.01 при Учреждении Российской академии наук Институт проблем информатики РАН по адресу: 119333, Москва, ул. Вавилова, д.44, корп. 2.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Институт проблем информатики РАН.

Отзывы в одном экземпляре, с заверенной подписью, просим направлять по адресу: 119333, Москва, ул. Вавилова, 44, корп.2, в диссертационный совет.

Автореферат разослан <Ы'Л> р-р^^Я 2011 г. Ученый секретарь

диссертационного совета Д002.073.01, доктор технических наук, профессор (7 С.Н. Гринченко

Общая характеристика работы

Актуальность темы. В настоящее время существует множество областей применения систем управления базами данных (СУБД), таких как: обработка экономической информации, использование информационных систем (ИС) в различных сферах деятельности человека, автоматизация работ на промышленных предприятиях. В каждой из этих областей требуется создание разнообразных баз данных (БД) для хранения и обработки большого объема различной информации.

Логической основой любой СУБД является одна или несколько моделей представления данных, наибольшее распространение из которых получила реляционная модель. Ее методы структурирования основаны на математическом аппарате теории множеств и отношений, а операции обработки структурированных данных используют теоретико-множественные операции и их комбинации.

Несмотря на все преимущества реляционной модели представления данных по сравнению с предшествующими моделями, у нее присутствует ряд недостатков, которые, со временем, привели к проблеме хранения, обработки и анализа многомерных массивов данных. Основным ее недостатком является сложность реализации в БД связей с типом связи «многие ко многим» между данными предметной области. Этот недостаток вытекает из применения к парным отношениям теоретико-множественных операций и введения в реляционной модели правил нормализации, которые приводят к необходимости бинаризации каждого из отношений. Кроме этого, нормализация ведет к разрастанию количества отношений и усложнению схемы базы данных, из-за чего возникают проблемы ее модификации в дальнейшем. Особенно это становится актуальным для динамично меняющихся БД. Как следствие, в реляционной модели данных отсутствует многомерность, а также операции многомерной обработки и анализа данных.

Одним из подходов решения данной проблемы в СУБД реляционного типа является создание всевозможных многомерных надстроек (к примеру, таких как OLAP - On-Line Analytical Processing), позволяющих создавать и обрабатывать многомерные структуры данных, дублируя при этом информацию БД, что усложняет механизмы внесения в нее изменений.

Перечисленные проблемы и пути их решения, приводят к необходимости создания новых, более совершенных моделей представления данных, в которых они были бы изначально решены на уровне самой модели, а не ее реализаций.

Еще одним фактором, влияющим на актуальность исследований, служит относительно небольшой объем публикаций и теоретических работ по решению указанных проблем. Все существующие работы можно условно разделить на две группы: работы по созданию многомерных надстроек над реляционными структурами и работы, в которых авторы пытаются реализовывать реляционные СУБД без правил нормализации, обеспечив некоторые возможности хранения и обработки многомерных массивов (и-арных отношений) на физическом уровне организации СУБД.

Исходя из вышесказанного, видно, что существует необходимость разработки теоретической базы, которая позволила бы решить перечисленные проблемы, а также устранить недостатки хранения и обработки данных, что доказывает актуальность проводимых исследований.

В предлагаемой диссертационной работе излагается новая векторно-матричная модель представления данных, а также проводится ряд исследований, направленных на практическое применение векторно-матричной модели данных для создания новых СУБД векторно-матричного типа.

Объект исследования. Модели представления данных.

Предмет исследования. Разработка модели представления данных и технического решения для построения новых СУБД.

Целью работы является разработка новой модели представления данных, позволяющей эффективно создавать, хранить и обрабатывать многомерные

массивы данных, а также создание технологии построения новых СУБД, основанных на разработанной модели представления данных.

Для достижения указанной цели в диссертации решены следующие задачи:

1) обосновано уточнение термина «модель представления данных»;

2) выполнен обзор современных моделей представления данных и указаны их основные достоинства и недостатки;

3) разработана векторно-матричная модель представления данных по уточненному определению модели представления данных;

4) выполнено сравнение операций обработки и методов структурирования векторно-матричной модели представления данных и реляционной модели представления данных;

5) разработаны способы повышения эффективности хранения и обработки разреженных данных с помощью отображения алгебры многомерных матриц в иерархических структурах;

6) разработано и запатентовано техническое решение системы представления данных в базе данных, основанное на векторно-матричной модели представления данных;

7) разработана технология построения СУБД векторно-матричного

типа.

Методы исследования. При решении поставленных в диссертации задач применялись методы теории баз данных, теории множеств и отношений, теории алгебраических систем, теории графов, теории алгебры многомерных матриц, алгоритмы и языки программирования.

На защиту выносятся следующие результаты:

1. Векторно-матричная модель представления данных.

2. Иерархическое представление многомерных матриц и их операций.

3. Технология построения СУБД векторно-матричного типа. Научная новизна полученных результатов заключается: в разработке и

формальном описании новой векторно-матричной модели представления

данных; в исследовании функциональных возможностей векторно-матричной модели представления данных и сравнении ее функциональных возможностей с возможностями существующих моделей представления данных; в разработке способов повышения эффективности хранения и обработки разреженных данных с помощью отображения алгебры многомерных матриц в иерархических структурах; в разработке технологии построения СУБД векторно-матричного типа.

При этом автором впервые получены следующие результаты:

- разработаны методы структурирования данных предметной области векторно-матричной модели представления данных;

- описаны правила ограничения целостности векторно-матричной модели представления данных;

- определен набор операций обработки структурированных данных векторно-матричной модели представления данных;

- разработаны принципы проектирования для векторно-матричной модели представления данных с использованием (ER - Entity-Relationship) диаграмм;

- разработано отображение алгебры многомерных матриц в алгебру иерархических структур;

- определены условия повышения эффективности хранения и обработки элементов разреженных многомерных матриц с помощью иерархических структур;

- предложена технология создания СУБД векторно-матричного типа;

- рассмотрена возможность использования векторно-матричной модели представления данных в СУБД иерархического и реляционного типов для повышения их функциональности.

Практическая ценность результатов диссертационного исследования заключается в создании новой модели представления данных и разработке технологии создания новых СУБД с использованием запатентованного технического решения.

Достоверность и обоснованность основных результатов и выводов

диссертации базируются на: обобщении и развитии существующего опыта хранения и обработки информации в системах управления базами данных; результатах исследований известных моделей представления данных; использовании математического аппарата теории множеств и алгебраических систем; соответствии полученных результатов сведениям, опубликованным в отечественной и зарубежной литературе по тематике проводимых исследований; результатах практического применения разработанных моделей и алгоритмов при создании баз данных.

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на следующих конференциях и семинарах: Научно-практической конференции «Информатизация общества и проблемы образования» (Смоленск-2002); Всероссийской научно-практической конференции «Методология и методика информатизации образования: концепции, программы, технологии» (Смоленск-2004); Международной конференции «Системы компьютерной математики и их приложения» (Смоленск-2006, 2007), Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (Таганрог-2007), Второй научной сессии Института проблем информатики Российской академии наук (Москва-2005).

Результаты проведенных исследований использованы при создании технического решения «Система представления данных в базе данных», что подтверждено патентом РФ на полезную модель.

Результаты диссертации отражены в инициативных проектах РФФИ (№ 07-07-00378, № 09-07-00411).

Результаты работы были применены при разработке информационной системы «Учет сбытовых расходов», реализованной в СУБД реляционного типа в ООО компании «Мир Детства», что подтверждено соответствующим актом о внедрении.

Публикация результатов работы. Основные результаты диссертации опубликованы в 12 печатных работах, в том числе одна из них в изданиях рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, списка литературы (106 наименований) и двух приложений. Объем работы 126 стр., включая 15 рисунков, 6 таблиц, 2 приложения.

Краткое содержание работы

Во введении обоснована актуальность исследований диссертационной работы, представлены положения, характеризующие новизну, практическую значимость, личный вклад автора, достоверность результатов. Кроме этого, сформулированы основные цели и задачи исследований.

В первой главе исследуется понятие и уточняется определение модели представления данных. Рассматриваются современные модели представления данных и перечисляются их основные преимущества и недостатки. Обосновывается необходимость поиска новых моделей представления данных для повышения эффективности хранения и обработки данных.

Особое внимание в первой главе уделяется понятию модели представления данных и дается ее уточненное определение, на базе которого строится изложение последующих глав диссертационной работы. Модель представления данных определяется как инструмент моделирования предметной области, включающий в себя структуры данных, методы структурирования данных предметной области, правила ограничения целостности и операции обработки структурированных данных.

Модель представления данных формализует предметную область, используя структуры данных, и предоставляет операции обработки структурированных данных.

С помощью структур данных модели представления данных систематизируется и представляется информация предметной области.

Методы структурирования являются инструментом представления информации предметной области в структурах данных, а правила ограничений целостности обеспечивают непротиворечивость представленных данных с информацией предметной области.

Операции обработки данных включают в себя операции работы со структурированными данными, которые допустимо производить над структурами данных модели представления данных.

Также в данной главе рассматриваются недостатки существующих моделей представления данных (иерархической, сетевой и реляционной).

Отмеченные недостатки известных моделей представления данных делают актуальной необходимость поиска новых, более совершенных моделей представления данных.

В качестве одной из таких моделей, в которой устраняется большая часть недостатков, рассматривается векторно-матричная модель представления данных.

Вторая глава посвящена описанию разработанной автором векторно-матричной модели представления данных.

Особенностью векторно-матричной модели представления данных является следующее:

1. Основной структурой данных для описания объектов предметной области является множество. Многомерная матрица является основной структурой данных для описания связей между объектами предметной области.

(р - мерная (многомерная) матрица Л = ||а,. , | определяется как совокупность элементов я,__ , где индексы ('„...,¡р принимают значения от 1 до па(а = 1,.../>) соответственно, р - мерная матрица содержит п1х...хпр элементов).

2. Все элементы множеств нумеруются в них по порядку. Сформированные номера являются индексом при формировании многомерных

матриц, описывающих связи между элементами различных множеств, объектов предметной области.

Методы структурирования данных векторно-матричной модели представления данных применительно к данным произвольной предметной области сводятся к последовательному выполнению следующих трех операций:

- факторизация множества объектов предметной области по указанному в диссертационной работе отношению эквивалентности - (два объекта эквивалентны, если они имеют одинаковый набор функций, значения которых характеризуют набор атрибутов соответствующих объектов);

- добавление для каждого объекта х предметной области при его представлении в структурах данных векторно-матричной модели представления данных трех дополнительных атрибутов: И(х) (идентификатор), Мит(х) (порядковый нумератор в классе эквивалентности) и Бе1есЮг(х) (представление);

- построение многомерных матриц, значениями индексов которых являются значения функций №т(х) соответствующих классов эквивалентности.

В векторно-матричной модели представления данных определяются следующие правила ограничения целостности:

- элементы каждого из множеств нумеруются в нем по порядку;

- присвоенный элементу номер не изменяется и не может быть присвоен какому-либо другому элементу даже после удаления первого элемента из множества;

- удаление элемента из множества должно повлечь за собой проверку существования индексов со значением элемента в многомерных матрицах;

- элемент множества может быть удален только после предшествующего удаления всех элементов многомерных матриц с его участием.

В векторно-матричной модели представления данных операции обработки данных включают в себя:

теоретико-множественные операции: объединение, разность, пересечение, декартово произведение, а также их комбинации;

- операции алгебры многомерных матриц: сложение, (X, р) свернутое произведение, свертка, сечение, транспонирование, а также их комбинации;

- комбинации теоретико-множественных операций и операций алгебры многомерных матриц.

На рис. 1. Схематично показан смысл взаимосвязи структур данных векторно-матричной базы данных.

В векторно-матричной базе данных все связи между объектами предметной области представляются в формате «многие ко многим», что упрощает процедуру описания схемы векторно-матричной базы данных.

В диссертационной работе рассматривается применение проектирования с помощью ЕЯ-диаграмм к методам векторно-матричного структурирования данных, а также производится описание структуры ключей и индексов для

реализации структур данных на физическом уровне при построении СУБД векторно-матричного типа.

Также во второй главе производится сравнение функциональных возможностей векторно-матричной модели представления данных с функциональными возможностями существующих моделей представления данных. Основные отличия при сравнении векторно-матричной и реляционной моделей представления данных представлены в таблице 1.

Таблица 1. Отличия при сравнении векторно-матричной и реляционной

моделей представления данных

Предмет Реляционная Векторно-матричная

сравнения

Методы 1. Домены (множества). 1. Векторы (пронумерованные

структури- множества).

рования 2. Отношения (подмножества 2. Многомерные матрицы

декартовых произведений (полные декартовы

множеств, в операциях произведения

обработки рассматриваются пронумерованных множеств).

как множества кортежей).

3. Правила нормализации,

приводящие к бинаризации

отношений.

Операции Теоретико-множественные 1. Теоретико-множественные

обработки операции. операции.

2. Операции алгебры

многомерных матриц.

Методы структурирования векторно-матричной модели представления данных позволяют представлять связи с типом «многие ко многим» между объектами предметной области. Описываемое представление упрощает

проектирование предметной области и унифицирует механизм отображения данных в векторно-матричной базе данных.

Операции обработки данных векторно-матричной модели представления данных включают в себя операции обработки данных реляционной модели представления данных (теоретико-множественные операции и их комбинации) и операции многомерной обработки и анализа данных алгебры многомерных матриц. При этом возможно построение алгебраических выражений из многомерных матриц.

Основным недостатком векторно-матричной модели представления данных является нерациональное хранение и обработка разреженных многомерных матриц. В диссертационной работе для устранения данного недостатка разрабатываются методы представления многомерных матриц и операций алгебры многомерных матриц в иерархических структурах.

Третья глава описывает способ хранения и обработки разреженных многомерных матриц. При этом используются основные понятия теории графов.

Любая многомерная матрица представима в виде связной иерархической структуры ее сечений. Рассмотрим матрицу Л = ||а,.где ¡к = 1,...,«, (к=.\,...,р соответственно). Сечением {(/„«г.-.«,)} матрицы будет множество элементов с

координатами (¡„¡2,...,1р), где = 1.....и,,;2 = 1,...,и2>.=1,...,лр, при этом один или

несколько индексов будут фиксированными. Определим сечениями / уровня сечения, полученные из матрицы Л, фиксацией значений индексов ¡1У12,...,1,.

Для произвольной многомерной матрицы, количество уровней разбиения на сечения, а также количество самих сечений будут определяться размерностью матрицы. Уровней разбиения будет столько же, сколько индексов в многомерной матрице - р. Общее количество сечений всех уровней будет равно л1+л1хл2+...+л,хл2х...хл;1. Количество сечений / уровня будет равно

Л, ХЛ, Х...ХП/.

Рассмотрим произвольную трехмерную матрицу ^ = гдс

/, =1,...,и,,12 = 1,...,л2,/э =1 ,...,я3 (рис. 2).

а,,, а211 ... °121 °221 -

«1.2 а212 - %2 0,22 "222 - ^,22

Рис. 2. Матрица Л = д

Для данной матрицы уровней разбиения будет три.

Сечений первого уровня будет и,: {(1,/2,13)}> {(2,/2,/3)},..., {(и,,г2,/3)}.

Сечений второго уровня будет «, хп2: {(1,1,¡3)}, {(1,2,/3)},..., {(п,,«2,(',)}.

Сечений третьего уровня будет л, хл2хл3: {(1,1,1)}, {(1,1.2)},..., {(п„п2,п3)}.

Сопоставим каждому сечению последнего уровня рассматриваемой многомерной матрицы значение элемента многомерной матрицы, в нем содержащееся. Все сечения всех уровней с сопоставленными значениями элементов многомерной матрицы представимы с помощью иерархической структуры (рис. 3).

1 уровень С>2 О

2 уровень О О О С^ 02 03 Ох 02 Оэ

1\ 1\ |\ 1\ 1\ |\ 1\ |\ 1\

3 уровень ООООООООООООООООО о

12 121212 12 121212 12

I I I I I I I I I I I I I I I I I I

Значение ОООООООООООООООООО Рис. 3. Иерархическая структура рассматриваемой матрицы Л = ||л.ч|| (вместо сечений записаны фиксированные индексы соответствующих уровней)

Иерархическая структура представляет собой граф. При таком представлении, иерархическая структура определяется совокупностью полных путей графа, так как два произвольных полных пути иерархической структуры не совпадают, каждый в отдельности характеризует единственный элемент многомерной матрицы, а в совокупности образуют все элементы многомерной матрицы с соответствующими индексами.

Определение 1: Элементом иерархического представления многомерной матрицы назовем полный путь иерархической структуры, и

обозначим его = (/,,/2,..., .

Определение 2: Иерархическим представлением многомерной матрицы А = |а(] , ||, индексы элементов которой принимают значения от 1 до

па(а = 1,...,р), соответственно, назовем иерархическую структуру ТРЛ =(л,,п2,...,пр), которая задается совокупностью элементов иерархического

представления Т"л = ( |.

Также в третьей главе даются определения представления основных операций алгебры многомерных матриц в иерархических структурах.

Кроме этого, в третьей главе рассматриваются условия, накладываемые на алгебру значений элементов многомерных матриц:

1. Алгебра (Л/, ф, - множество М с заданными на нем двумя бинарными операциями © и ®.

2. Закон симметричности и наличие нейтрального элемента выполняются для операций Фи®.

3. Нейтральный элемент по операции Ф является обнуляющим элементом по операции ®, т. е. существует такой элемент ееМ , при котором УаеМ,е®а-а®е = а и ЧаеМ,е®а = а®е~е.

Элемент е играет важную роль. Назовем этот элемент нулем. К примеру, для поля действительных чисел таким элементом будет являться 0. Для поля логических элементов - элемент «ложь».

При использовании указанных условий при хранении и обработке многомерных матриц в иерархических структурах достаточно хранения и обработки только элементов не равных нулю (е) соответствующих многомерных матриц, что позволяет минимизировать затраты при хранении и сократить число операций при обработке разреженных многомерных матриц.

В четвертой главе рассматривается архитектура систем управления базами данных, основанная на векторно-матричной модели представления данных.

Логический уровень организации СУБД векторно-матричного типа (ВМСУБД) разработан как техническое решение в патенте РФ на полезную модель "Система представления данных в базе данных".

Система представления данных в базе данных содержит средство управления векторно-матричными базами данных, взаимосвязанное с векторно-матричной базой данных и с блоком хранения данных предметной области. Векторно-матричная база данных включает взаимосвязанные между собой узел хранения множеств значений характеристик объектов предметной области и узел хранения многомерных матриц. Средство управления векторно-матричными базами данных включает узел структурирования данных и узел обработки структурированных данных. Векторно-матричная база данных содержит узел хранения множеств значений характеристик объектов предметной области для представления объектов предметной области и узел хранения многомерных матриц для представления связей между объектами предметной области. Средство управления векторно-матричными базами данных содержит узел структурирования данных, выполняющий операции структурирования данных предметной области, которые основываются на методах структурирования векторно-матричной модели данных, и узел обработки структурированных данных, выполняющий операции обработки данных векторно-матричной базы данных, включая теоретико-множественные операции и операции алгебры многомерных матриц и их комбинации.

Работа системы представления данных в базе данных основывается на векторно-матричной модели представления данных.

Кроме этого, в четвертой главе особое внимание уделяется рассмотрению применения векторно-матричной модели представления данных в существующих СУБД реляционного и иерархического типов для увеличения функциональности последних. Такая возможность осуществляется за счет взаимосвязи между структурами данных векторно-матричной, реляционной и иерархической моделей представления данных (рис. 4).

Рис. 4. Взаимосвязь структур представления данных

В качестве одного из примеров такого использования взаимосвязи структур данных, рассматривается применение методов структурирования данных векторно-матричной модели представления данных при создании информационной системы «Учет сбытовых расходов», реализованной в СУБД реляционного типа в ООО компании «Мир Детства», что позволило упростить схему базы данных указанной системы, и существенно ускорить получение итоговых отчетов.

В заключении делаются выводы и намечаются пути дальнейшего исследования применения векторно-матричной модели представления данных.

Дальнейшее развитие научных исследований целесообразно вести в следующих направлениях:

1. Создание и исследование систем управления базами данных векторно-матричного типа.

2. Разработка высокопроизводительных способов хранения и обработки иерархических структур для реализации физического уровня СУБД векторно-матричного типа. Использование в исследованиях способов распараллеливания процессов обработки данных и доступа к ним.

3. Исследование и стандартизация языка описания и языка манипулирования данными для работы с векторно-матричной базой данных с использованием современных принципов объектно-ориентированного программирования.

Основные результаты работы

1. Впервые в диссертационной работе предложена векторно-матричная модель представления данных и ее реализация в иерархических структурах, с помощью чего решена проблема повышения эффективности хранения и обработки данных.

2. Разработанная векторно-матричная модель представления данных обладает рядом важных свойств, необходимых для эффективного хранения и обработки данных, таких, как унифицированные методы векторно-матричного структурирования данных предметной области, расширенный, по сравнению с другими моделями представления данных, аппарат операций векторно-матричной обработки данных.

3. Проведен анализ проблем, возникающих при хранении разреженной информации, представленной с помощью многомерных матриц. Разработаны способы иерархического представления многомерных матриц и операций алгебры многомерных матриц для улучшения хранения и обработки разреженных данных.

4. Разработано и запатентовано техническое решение, которое представлено в патенте на полезную модель "Система представления данных в базе данных".

5. Предложенные методы векторно-матричного структурирования реализованы при создании информационной системы «Учет сбытовых расходов» в ООО компании «Мир Детства». Система ориентирована на конечных пользователей и обеспечивает хранение, обработку, анализ и быстрый поиск данных при решении поставленных задач.

Основные публикации по теме диссертации

1. Сергеев В.П. Векторно-матричная модель представления данных. // Вестник компьютерных и информационных технологий. - Москва: Изд-во Машиностроение. - 2010 г. №6. Стр.3-8

2. Сергеев В.П., Левин H.A., Мунерман В.И., Гайдаенко Т.А., Провоторова А.О., Ширай А.Е., Оздемир С.М. // Патент на полезную модель «Система представления данных в базе данных» № 82355. Зарегистрирован в Государственном реестре полезных моделей Российской Федерации 20.04.2009 г. Бюл. №11. МПК G06F 17/30. -

URL:http://wwwl.fips.ru/fips_servl/fips_servlet?DB=RUPM&rn=5090&DocNumbe r=82355&TypeFile=html.

Личный вклад автора: разработка и описание системы представления данных в базе данных на основе принципов векторно-матричной модели представления данных.

3. Сергеев В.П. Реализация матричной модели данных в иерархических структурах. // Математическая морфология. Электронный математический и медико-биологический журнал. - Т. 6. - Вып. 2. - 2007 г. - Per. №042070004/0020. - URL:http://sgma.alpha-design.ru/MMORPH/N-14-html/sergeev/sergeev.htm

4. Провоторова А.О., Сергеев В.П. Методы тестирования и оценки производительности вычислительной системы «ВСАРР» в составе параллельной системы баз данных. // Материалы международной научно-

технической конференции. Т.1. - Таганрог: Изд-во ТТИ ЮФУ. - 2007 г. Стр. 100-104.

Личный вклад автора: разработка принципов использования в вычислительной системе «ВСАРР» векторно-матричной модели представления данных.

5. Сергеев В.П. Гомоморфное отображение алгебры многомерных матриц в иерархические структуры. // Системы компьютерной математики и их приложения: материалы международной конференции. Мин-во образования и науки РФ; Смоленский гос. Ун-т. - Смоленск: Изд-во СмолГУ. - Вып. 8. - 2007 г. Стр. 111-113.

6. Левин H.A., Сергеев В.П. Иерархическое представление алгебры многомерных матриц. //Деп. ВИНИТИ 12.09.2006 г. №1149-В2006, 13 с.

Личный вклад автора: разработка способов иерархического представления алгебры многомерных матриц в иерархических структурах.

7. Сергеев В.П. Использование алгебры многомерных матриц для работы с данными на параллельных ЭВМ. // Системы компьютерной математики и их приложения: материалы международной конференции. -Смоленск: Изд-во СмолГУ. - Вып. 7. - 2006 г. Стр. 90-92.

8. Сергеев В.П. Представление многомерных матриц в иерархических структурах для повышения эффективности хранения и процессов обработки данных. // Системы и средства информатики. Стохастические технологии и системы. - Москва: Изд-во ИПИ РАН. - 2005 г. Стр. 297-317.

9. Левин H.A., Мунерман В.И., Сергеев В.П. Применение многомерных матриц в запросах пользователей к базам данных. /ЯГроблемы и методы информатики. II Научная сессия ИПИ РАН: Тезисы докладов. Под ред. И.А. Соколова. - Москва: Изд-во ИПИ РАН. - 2005 г. Стр. 81-86.

Личный вклад автора: описание методов построения языков манипулирования данными, использующих операции алгебры многомерных матриц.

10. Левин H.A., Мунерман В.И., Сергеев В.П. Алгебра многомерных матриц как универсальное средство моделирования данных и ее реализация в современных СУБД. // Системы и средства информатики. - Москва: Изд-во Наука. - Вып. 14. - 2004 г. Стр. 86-99.

Личный вклад автора: разработка способов реализации алгебры многомерных матриц в иерархических структурах.

11. Сергеев В.П. Оптимизация структур данных в распределенных педагогических системах. // Методология и методика информатизации образования: концепции, программы, технологии: Материалы Всероссийской научно-практической конференции (26-28 января 2004 года). - Смоленск: Изд-во СГПУ. - 2004 г. - Стр. 127-130.

12. Сергеев В.П. Матричные модели баз данных в задачах автоматизации учебного процесса. // Информатизация общества и проблемы образования: Материалы научно-практической конференции (25-27 марта 2002 года). - Москва-Смоленск: Изд-во ИПИРАН, СГПУ. - 2002 г. - Стр. 49-53.

Формат 60x90/16. Заказ 1392. Тираж 100 экз.

Печать офсетная. Бумага для множительных аппаратов.

Отпечатано в ООО "ФЭД+", Москва, ул. Кедрова, д. 15, тел. 774-26-96

ВВЕДЕНИЕ.

ГЛАВА 1. МОДЕЛИ ПРЕДСТАВЛЕНИЯ ДАННЫХ.

1.1. Понятие модели представления данных.

1.2. Существующие модели представления данных.

1.2.1. Иерархическая и сетевая модели представления данных.

1.2.2. Реляционная модель представления данных.

1.2.3. Многомерное представление данных.

1.3. Выводы.

ГЛАВА 2. ВЕКТОРНО-МАТРИЧНАЯ МОДЕЛЬ

ПРЕДСТАВЛЕНИЯ ДАННЫХ.

2.1. Векторно-матричное структурирование данных.

2.1.1. Методы структурирования данных и правила ограничения целостности.

2.1.2. ЕЯ-моделирование и многомерные матрицы.

2.1.3. Ключи и индексы.

2.2. Операции обработки данных векторно-матричной модели представления данных.

2.2.1. Теоретико-множественные операции.

2.2.2. Операции алгебры многомерных матриц.

2.3. Хранение и обработка разреженных данных.

2.4. Выводы.

ГЛАВА 3. ИЕРАРХИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

АЛГЕБРЫ МНОГОМЕРНЫХ МАТРИЦ.

3.1. Структура многомерной матрицы и ее сечений.

3.2. Представление многомерной матрицы с помощью иерархической структуры.

3.3. Реализация операций алгебры многомерных матриц в иерархических структурах.

3.3.1. Операция сложения алгебры многомерных матриц

3.3.2. Операция (X, ц) свернутого произведения алгебры многомерных матриц.

3.3.3. Сечение многомерной матрицы.

3.3.4. Свертка многомерной матрицы.

3.3.5. Транспонирование многомерной матрицы.

3.4. Влияние алгебры элементов многомерной матрицы на обработку разреженных данных.

3.5. Пример применения операций многомерных матриц и их иерархических представлений для обработки данных.

3.6. Выводы.

Глава 4. ПРИМЕНЕНИЕ ВЕКТОРНО-МАТРИЧНОЙ

МОДЕЛИ ПРЕДСТАВЛЕНИЯ ДАННЫХ.

4.1. Создание систем управления базами данных векторно-матричного типа.

4.1.1. Логический уровень ВМСУБД.

4.1.2. Концептуальный уровень ВМСУБД.

4.1.3. Физический уровень ВМСУБД.

4.2. Использование векторно-матричной модели представления данных в существующих СУБД.

4.2.1. Использование векторно-матричной модели представления данных в реляционных СУБД.

4.2.2. Использование векторно-матричной модели представления данных в иерархических СУБД.

4.3. Применение методов векторно-матричной модели представления данных при создании информационной системы

Учет сбытовых расходов» ООО компании «Мир Детства»

4.3.1. Построение информационной системы с использованием методов реляционного структурирования данных.

4.3.2. Построение информационной системы с использованием методов структурирования данных векторно-матричной модели представления данных.

4.4. Выводы.

Прежде чем переходить к описанию векторно-матричной модели представления данных, необходимо определить термин «модель представления данных», а также роль модели представления данных в теории баз данных.

В различных областях деятельности ведутся большие работы по созданию автоматизированных систем управления (АСУ), систем автоматизированного проектирования (САПР), автоматизированных информационных систем (АИС). Каждая из этих систем располагает большим объемом информации, которая используется для решения задач специализированными программами. Информационный фонд этих систем принято называть базой данных [37,42,43].

Под данными, хранящимися в базе данных, понимается информация, находящаяся в памяти ЭВМ или машинных носителях (дискете, магнитной ленте и др.).

Под обработкой данных понимается совокупность задач, осуществляющих преобразование массивов данных [56]. Обработка данных включает в себя ввод данных в ЭВМ, отбор данных по каким-либо критериям и параметрам, преобразование структуры данных, перемещение данных, вывод данных в табличном или ином удобном для пользователя виде [35,55].

Под базой данных (БД) понимается совокупность взаимосвязанных данных некоторой предметной области, хранимых в памяти ЭВМ и организованных таким образом, чтобы эти данные могли быть использованы для решения многих задач пользователями [57].

Успешное функционирование базы данных может быть осуществлено только при выполнении ряда требований к ее организации [59,62]. К таким основным требованиям можно отнести:

1. Расширяемость базы данных.

База данных должна обладать способностью к расширению, которое может быть за счет:

- увеличения числа экземпляров однотипных данных;

- введение в БД новых типов объектов или новых типов взаимосвязей.

Необходимо, чтобы введение новых типов объектов или связей не требовало каких-либо изменений в данных, уже существующих в базе данных.

2. Простота работы с базой данных.

В условиях разработки и эксплуатации крупной системы большое значение приобретает простота работы с данными базы данных, т. е. необходимо, чтобы:

- структура данных была логичной и ясной;

- операции доступа к данным обладали ясными и четко очерченными функциями;

- без больших трудозатрат выполнялись различные операции над данными.

3. Целостность базы данных.

Под целостностью базы данных в общем случае понимается ее готовность к работе. Целостность базы данных — сложное понятие, имеющее много аспектов:

- физическая целостность, т. е. сохранность информации на магнитных носителях и корректность форматов данных; логическая целостность, под которой понимается непротиворечивость данных в базе;

- актуальность данных, т. е. соответствие данных реальному положению вещей.

Потеря целостности базы данных может произойти от сбоев аппаратуры ЭВМ, ошибок в программном обеспечении, неверной технологии ввода и корректировки данных, низкой достоверности самих данных, и т. д. [66]. Поэтому обеспечить целостность базы реального объема весьма сложно. В то же время потеря целостности данных ведет к самым серьезным последствиям вплоть до полной перегрузки данных базы. Если учесть, что обычно базы данных накапливаются годами или даже десятками лет, то потеря целостности базы данных зачастую влечет очень тяжелые последствия [68].

Как видно из изложенного выше, разработка и эксплуатация базы данных сопряжена с решением целого ряда проблем. Каждая из этих проблем весьма сложная. Поэтому удовлетворительное функционирование базы данных требует выполнения весьма трудоемких организационно-технических мероприятий. В качестве своего главного инструмента база данных использует систему управления базами данных [79,80] (СУБД).

Под СУБД понимается программная система, обеспечивающая все функции управления данными со стороны базы данных и прикладных программ пользователей. Любой доступ к данным базы данных осуществляется через СУБД [21,25].

СУБД является программным обеспечением, осуществляющим функции управления данными БД [97]. Применение СУБД позволяет значительно уменьшить трудозатраты по реализации требований к БД и обеспечить более полное их выполнение.

Сама СУБД — системное программное обеспечение. Не решая непосредственно никакой прикладной задачи, СУБД является инструментом для разработки и поддержания баз данных, с помощью которого можно создавать базы данных, наполнять их и работать с ними [79,85]. В мире существует немало различных систем управления базами данных. Функции и структуру типичной СУБД уместно рассматривать вместе, так как каждой из основных функций соответствует программная компонента СУБД [28,29].

Основные функции СУБД:

1. Описание данных.

В процессе работы прикладных программ и пользователей база данных изменяется. Однако эти изменения не могут быть произвольными. Обычно в базе данных существуют довольно жесткие ограничения на возможности манипулирования данными, которые отражают закономерности предметной области. Так, в базе данных пользователь может образовать новый экземпляр объекта или исключить уже существующий экземпляр, но изменить характеристики этого объекта он, как правило, не может. Описание неизменяемых свойств данных БД получило название описание структуры данных или схема базы данных.

2. Манипулирование данными.

Современные СУБД предоставляют пользователям средства манипулирования данными, в состав которых входят операторы поиска данных в базе данных, корректировки данных в базе данных, обмена данными между базой данных прикладной программой и ряд других.

3. Загрузка базы и формирование отчетов

На универсальном языке программирования молено написать любую программу обработки данных, в том числе программу заполнения (загрузки) и корректировки базы данных или программу распечатки выходных форм. Однако указанные действия выполняются столь часто, что для их реализации большинство СУБД имеют специальные программные средства, которые носят названия: для ввода и корректировки данных — подсистема загрузки данных; для получения выходных форм — генератор отчетов [47]. Эти средства в своем составе имеют языки высокого уровня, ориентированные на описание ввода— вывода данных.

4. Язык запросов.

Часто возникает необходимость выполнить запрос из базы данных по определенным признакам объекта [58]. Для реализации такой возможности СУБД оснащаются языком запросов высокого уровня, а также интерпретатором с языка запросов. С помощью этого языка пользователи-непрограммисты могут сформулировать запрос к базе данных и тут же на дисплее получить ответ.

5. Диалоговые средства.

В целях удобства пользователей и повышения оперативности доступа к данным большинство функций СУБД может осуществляться в диалоговом режиме через дисплей [99]. Современные СУБД, как правило, обеспечивают мультидоступ к базе данных (т. е. одновременный доступ к базе нескольких терминальных пользователей или прикладных программ) [78]. При помощи дисплея удобно производить просмотр базы данных, ее корректировку, выполнение различных сервисных функций, ввод запросов и т. д.

Виды баз данных определяются моделью данных. Ядро любой базы данных - это модель данных, представляющая собой множество структур данных [76,77,98], ограничений целостности и операций манипулирования данных. В настоящее время наибольшее применение получили иерархическая, сетевая и реляционная модели данных.

Начальной стадией проектирования базы данных является разработка модели предметной области, которая базируется на анализе информационных потребностей будущих пользователей разрабатываемой базы данных. Эту стадию принято называть концептуальным проектированием, а ее результат — концептуальной моделью предметной области. (Объектом моделирования является предметная область.) Такая модель интегрирует информационные потребности пользователей создаваемой базы данных [83].

Инструментальные средства для спецификации концептуальной модели предметной области тоже принято называть моделями данных. Однако такие модели, в отличие от моделей данных, используемых в качестве инструмента моделирования баз данных, не обязательно поддерживаются механизмами используемой системы управления базами данных. Одной из моделей данных подобного рода является модель сущностей-связей (Entity-Relationship) П. Чена [3].

В процессе развития теории систем баз данных термин «модель данных» приобрел новое содержание. Этому способствовали новые потребности теории. Разработка новых архитектурных подходов, основанных на получивших признание идеях многоуровневой архитектуры СУБД, высказанных еще в раннем отчете CODASYL DBTG [4], в отчете ANSI/X3/SPARC [2] и во многих других работах начала - середины 70-х годов, а также активные исследования в области распределенных баз данных, породили проблемы отображения данных [53]. При этом, оказалось недостаточно рассматривать отображение представлений конкретной базы данных. Требовалось решение, позволяющее оперировать множествами всевозможных допустимых представлений баз данных в рамках заданной СУБД или инструментальными средствами, используемыми для спецификации совокупности баз данных [95]. В этой связи возникла потребность в термине, который обозначал бы инструмент, а не результат моделирования, и воплощал бы, таким образом, множество всевозможных баз данных некоторого класса.

Инструмент моделирования баз данных должен по необходимости включать не только средства структурирования данных, но и операционные возможности для манипулирования данными. Поэтому модель данных в инструментальном смысле стала пониматься как алгебраическая система [67]. Позднее в это понятие стали включать еще и ограничения целостности, которые могут налагаться на данные. В результате проблема отображения данных в многоуровневых СУБД и системах распределенных баз данных стала рассматриваться как проблема отображения моделей данных [103,104].

В данной работе, модель представления данных определяется как инструментальное средство моделирования предметной области, включающее в себя структуры данных, методы структурирования данных предметной области, правила ограничения целостности и операции обработки структурированных данных.

С помощью структур данных модели представления данных систематизируется и представляется информация предметной области.

Методы структурирования являются инструментом представления информации предметной области с помощью структур данных, а правила ограничений целостности обеспечивают непротиворечивость представленных данных с помощью структур данных с информацией предметной области.

Операции обработки данных включают в себя операции работы со структурированными данными, которые допустимо производить над структурами данных модели представления данных.

Модель представления данных, формализует предметную область, используя структуры данных, и предоставляет операции обработки структурированных данных.

Логической основой любой СУБД является одна или несколько моделей представления данных, наибольшее распространение из которых получила реляционная модель. Ее методы структурирования основаны на математическом аппарате теории множеств и отношений, а операции обработки структурированных данных используют теоретико-множественные операции и их комбинации.

В иерархической и сетевой моделях представления данных отсутствует декларативный язык для описания и манипулирования данными.

Несмотря на все преимущества реляционной модели представления данных по сравнению с предшествующими моделями, у нее присутствует ряд недостатков, которые, со временем, привели к проблеме хранения, обработки и анализа многомерных массивов данных.

Основным ее недостатком является сложность реализации в БД связей с типом связи «многие ко многим» между данными предметной области. Этот недостаток вытекает из применения к «-арным отношениям теоретико-множественных операций и введения в реляционной модели правил нормализации, которые приводят к необходимости бинаризации каждого из отношений. Кроме этого, нормализация ведет к разрастанию количества отношений и усложнению схемы базы данных, из-за чего возникают проблемы ее модификации в дальнейшем. Особенно это становится актуальным для динамично меняющихся БД. По имеющимся в литературе сведениям до 80% созданных корпоративных хранилищ данных не решают полностью поставленных перед ними задач, а 40% являются проваленными проектами. Около 50% запросов Пользователей являются не предусмотренными в ходе их проектирования [40]. Использование реляционных СУБД в динамически развивающихся системах становится неэффективным при количестве заложенных в них отношений (таблиц) свыше 100-300, так как усложняется модификация и хранение схемы базы данных. Причина неэффективности СУБД состоит в противоречии между результатами проектирования базы данных, отражающими статичное состояние предметной области окружающего мира и реальными взаимодействиями пользователей с базой данных, отражающими состояние предметной области в ее динамике. При превышении системой некоторого критического уровня сложности попытки внесения в нее изменений будут приводить к сбоям и ошибкам, исправление которых, в свою очередь, будет порождать новые сбои и ошибки. [61,87].

Как следствие бинаризации отношений, в реляционной модели данных отсутствует многомерность, а также операции многомерной обработки и анализа данных.

Одним из подходов решения данной проблемы в СУБД реляционного типа является создание всевозможных многомерных надстроек (к примеру, таких как OLAP - On-Line Analytical Processing), позволяющих создавать и обрабатывать многомерные структуры данных, в которых частично или полностью дублируется информация, хранящаяся в реляционной базе данных [26]. В связи с этим, модификация базы данных влечет за собой необходимость поддержания актуальности продублированной информации.

Перечисленные проблемы и пути их решения, приводят к необходимости создания новых, более совершенных моделей представления данных, в которых они были бы изначально решены на уровне самой модели, а не ее реализаций.

Еще одним фактором, влияющим на актуальность исследований, служит относительно небольшой объем публикаций и теоретических работ по решению указанных проблем. Все существующие работы можно условно разделить на две группы: работы по созданию многомерных надстроек над реляционными структурами и работы, в которых авторы пытаются реализовывать реляционные СУБД без правил нормализации, обеспечив некоторые возможности хранения и обработки многомерных массивов (и-арных отношений) на физическом уровне организации СУБД.

Исходя из вышесказанного, видно, что существует необходимость разработки теоретической базы, которая позволила бы решить перечисленные проблемы, а также устранить недостатки хранения и обработки данных, что доказывает актуальность проводимых исследований.

В предлагаемой диссертационной работе излагается новая векторно-матричная модель представления данных, а также проводится ряд исследований, направленных на практическое применение векторно-матричной модели данных для создания новых СУБД векторно-матричного типа.

Целью работы является разработка новой модели представления данных, позволяющей эффективно создавать, хранить и обрабатывать многомерные массивы данных, а также создание технологии построения новых СУБД, основанных на разработанной модели представления данных.

Для достижения указанной цели в диссертации решены следующие задачи:

1) обосновано уточнение термина «модель представления данных»;

2) выполнен обзор современных моделей представления данных и указаны их основные достоинства и недостатки;

3) разработана векторно-матричная модель представления данных по уточненному определению модели представления данных;

4) выполнено сравнение операций обработки и методов структурирования векторно-матричной модели представления данных и реляционной модели представления данных;

5) разработаны способы хранения и обработки разреженных данных с помощью отображения алгебры многомерных матриц в иерархические структуры;

6) разработано и запатентовано техническое решение системы представления данных в базе данных, основанное на векторно-матричной модели представления данных;

7) разработана технология построения СУБД векторно-матричного типа.

Научная новизна полученных результатов заключается: в разработке и формальном описании новой векторно-матричной модели представления данных; в исследовании функциональных возможностей векторно-матричной модели представления данных и сравнении ее функциональных возможностей с возможностями существующих моделей представления данных; в разработке способов хранения и обработки разреженных данных с помощью отображения алгебры многомерных матриц в иерархических структурах; в разработке технологии построения СУБД векторно-матричного типа.

При этом автором впервые получены следующие результаты:

- разработаны методы структурирования данных предметной области векторно-матричной модели представления данных;

- описаны правила ограничения целостности векторно-матричной модели представления данных;

- определен набор операций обработки структурированных данных векторно-матричной модели представления данных;

- разработаны принципы проектирования для векторно-матричной модели представления данных с использованием (ER - Entity-Relationship) диаграмм;

- разработано отображение алгебры многомерных матриц в алгебру иерархических структур;

- определены условия устранения разреженности при хранении и обработке элементов разреженных многомерных матриц с помощью иерархических структур;

- предложена технология создания СУБД векторно-матричного типа;

- рассмотрена возможность использования векторно-матричной модели представления данных в СУБД иерархического и реляционного типов для повышения их функциональности.

Практическая ценность результатов диссертационного исследования заключается в создании новой модели представления данных и разработке технологии создания новых СУБД с использованием запатентованного технического решения.

Достоверность и обоснованность основных результатов и выводов диссертации базируются на: обобщении и развитии существующего опыта хранения и обработки информации в системах управления базами данных; результатах исследований известных моделей представления данных; использовании математического аппарата теории множеств и алгебраических систем; соответствии полученных результатов сведениям, опубликованным в отечественной и зарубежной литературе по тематике проводимых исследований; результатах практического применения разработанных моделей и алгоритмов при создании баз данных.

Основные положения и результаты работы докладывались и обсуждались на следующих конференциях и семинарах: Научно-практической конференции «Информатизация общества и проблемы образования» (Смоленск-2002); Всероссийской научно-практической конференции «Методология и методика информатизации образования: концепции, программы, технологии» (Смоленск-2004); Международной конференции «Системы компьютерной математики и их приложения» (Смоленск-2006, 2007), Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (Таганрог-2007), Второй научной сессии Института проблем информатики Российской академии наук (Москва-2005).

Результаты проведенных исследований использованы при создании технического решения «Система представления данных в базе данных», что подтверждено патентом РФ на полезную модель.

Результаты диссертации отражены в инициативных проектах РФФИ (№ 07-07-00378, № 09-07-00411).

Результаты работы были применены при разработке информационной системы «Учет сбытовых расходов», реализованной в СУБД реляционного типа в ООО компании «Мир Детства», что подтверждено соответствующим актом о внедрении.

Диссертация состоит из введения, четырех глав, списка литературы (106 наименований) и двух приложений. Объем работы 126 стр., включая 15 рисунков, 6 таблиц, 2 приложения.

4.4. Выводы

1. В данной главе рассмотрена архитектура систем управления базами данных, основанная на векторно-матричной модели представления данных.

2. Рассмотрено применение векторно-матричной модели представления данных в существующих СУБД реляционного и иерархического типов.

3. Показано применение методов структурирования данных векторно-матричной модели представления данных при создании информационной системы «Учет сбытовых расходов», реализованной в СУБД реляционного типа.

ЗАКЛЮЧЕНИЕ

На защиту диссертации выносятся следующие основные результаты:

1. Впервые в диссертационной работе предложена векторно-матричная модель представления данных и ее реализация в иерархических структурах, с помощью чего решена задача многомерного хранения и обработки данных.

Предложенная векторно-матричная модель представления данных обладает рядом важных свойств, необходимых для хранения и обработки данных, таких, как унифицированные методы векторно-матричного структурирования данных предметной области, расширенный по сравнению с другими моделями представления данных аппарат операций векторно-матричной обработки данных. Проведен анализ проблем, возникающих при хранении разреженной информации, представленной с помощью многомерных матриц, и заключающихся в наличии связей между объектами с типом связи «многие ко многим» в базе данных. Предлагается для устранения указанных недостатков использовать иерархические структуры, которые упрощают хранение и обработку разреженных многомерных матриц.

2. В основе векторно-матричной модели представления данных разработаны: методы векторно-матричного структурирования данных предметной области, которые позволили упростить семантическое моделирование и унифицировать действия специалиста по созданию схемы векторно-матричной базы данных; перечень операций обработки данных, состоящий из совокупности теоретико-множественных операций и операций алгебры многомерных матриц, расширив тем самым аппарат обработки данных объединив в нем реляционные операции обработки данных и операции многомерного анализа данных.

3. Разработаны способы иерархического представления многомерных матриц и операций алгебры многомерных матриц и определено условие устранения разреженности при хранении и обработке разреженных данных.

4. Разработана система представления данных предметной области в векторно-матричной базе данных, описывающая устройство логического уровня организации СУБД векторно-матричного типа и представленная в патенте на полезную модель [94].

5. Предложенные методы векторно-матричного структурирования реализованы при создании информационной системы «Учет сбытовых расходов» в ООО компании «Мир Детства». Система ориентирована на конечных пользователей и обеспечивает хранение, обработку, анализ и быстрый поиск данных при решении поставленных задач.

Исследования, положенные в основу диссертационной работы, проводились автором в период с 2002 по 2011 г. в ИЛИ РАН, СМОЛГУ, ООО «СайнГрейн». Результаты диссертации отражены в инициативных проектах РФФИ (№ 07-07-00378, № 09-07-00411). Проведенные исследования позволяют утверждать, что предложенная векторно-матричная модель представления данных может эффективно использоваться как для создания новых СУБД векторно-матричного типа, так и в существующих СУБД для расширения их функциональности.

Научные положения, выводы и результаты диссертации теоретически обоснованы. В работе были применены следующие методы:

- исследование моделей представления данных, анализ операций языка манипулирования данными и языка описания данных, исследование семантического моделирования, методы и технологии баз данных, методы организации СУБД, методы хранения и обработки данных;

- методы исследования включают математическую логику, теорию моделей, теорию множеств и теорию алгебры многомерных матриц, теорию графов, теорию доказательств, теорию функций.

Обоснованность и достоверность полученных автором результатов базируется на том, что все выдвинутые в работе гипотезы и утверждения доказаны со строгостью, принятой в соответствующих научных дисциплинах, а главные выводы и разработанные принципы воплощены в патенте на полезную модель «Система представления данных в базе данных» и в информационной системе «Учет сбытовых расходов» в ООО компании «Мир Детства», которая внедрена и успешно эксплуатируется на СУБД реляционного типа. Учитывая данные обстоятельства, достоверность научных положений, выводов и рекомендаций является фактически установленной.

В диссертационной работе можно выделить следующие результаты:

- разработаны методы структурирования данных предметной области векторно-матричной модели представления данных;

- описаны правила ограничения целостности векторно-матричной модели представления данных;

- определен набор операций обработки структурированных данных векторно-матричной модели представления данных;

- разработаны принципы проектирования для векторно-матричной модели представления данных с использованием (ER - Entity-Relationship) диаграмм;

- разработано отображение алгебры многомерных матриц в алгебру иерархических структур;

- определены условия устранения разреженности при хранении и обработке элементов разреженных многомерных матриц с помощью иерархических структур;

- предложена технология создания СУБД векторно-матричного типа;

- рассмотрена возможность использования векторно-матричной модели представления данных в СУБД иерархического и реляционного типов для повышения их функциональности.

Полученные результаты диссертационной работы, ее выводы и рекомендации целесообразно использовать для создания высокопроизводительных СУБД векторно-матричного типа, а также в существующих СУБД реляционного и иерархического типов в организациях большинства сфер деятельности человека.

Дальнейшее развитие научных исследований целесообразно вести в следующих направлениях:

1. Создание и исследование систем управления базами данных векторно-матричного типа.

2. Разработка высокопроизводительных способов хранения и обработки иерархических структур для реализации физического уровня СУБД векторно-матричного типа. Использование в исследованиях способов распараллеливания процессов обработки данных и доступа к ним.

3. Исследование и стандартизация языка описания и языка манипулирования данными для работы с векторно-матричной базой данных с использованием современных принципов объектно-ориентированного программирования.

Основные положения и результаты диссертационной работы докладывались и обсуждались на семинарах "Системы компьютерной математики и их приложения" с международным участием [89, 90], второй научной сессии ИЛИ РАН "Проблемы и методы информатики" [64], всероссийской научно-практической конференции "Методология и методика информатизации образования: концепции, программы, технологии" [91], международной научно-технической конференции в Таганроге [82].

Результаты проведенных исследований использованы при создании технического решения «Система представления данных в базе данных», что подтверждено патентом РФ на полезную модель [94].

Результаты диссертации отражены в инициативных проектах РФФИ (№ 07-07-00378, № 09-07-00411).

Автором было опубликовано 12 научных работ, 7 из них легли в основу диссертационной работы.

1. Alalouf С. Hybrid OLAP. - St. Laurent, Canada: Speedware Corporation 1.c., 1997.

2. ANSI/X3/SPARC Study Group on Data Base Management Systems. Interim Report. FDT Bull. ASM-SIGMOD. v. 7, no. 2 (1975), p. 1140.

3. Chen P.P. The entity-relational model. Toward a unified view of data //ACM TODS, no. 1, 1976, p. 9-36. Есть русский пер.: Питер Пин-Шеи Чен. Модель «сущность-связь» — шаг к единому представлению данных//СУБД, 3/1995, с. 137-158.

4. CODASYL DBTG Report. New York: ACM, 1969. - p. 191

5. Codd E.F. A relational model of data for large shared data banks //Comm. ACM, v. 13, no. 6, 1970, p. 377-387. Есть русский пер.: Е.Ф. Кодд. Реляционная модель данных для больших совместно используемых банков данных //СУБД, 1/95, с. 145-160.

6. Codd E.F. Further Normalization of the Data base Relational Model //Data Base Systems.- N.J.: Prentice-Hall, 1972. P.33-64.

7. Codd E.F. Normalized Data Base Structure: A Brief Tutorial //Proc. of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control.- N.-Y.: ACM. 1971. - P.l-17.

8. Codd E.F. The Relational Model For Database Management Version 2. Reading, Mass.: Addison-Wesley, 1990.

9. Codd E.F., Codd S.B., Salley C.T. Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate. -N.Y.: John Wiley & Sons, 1993.

10. Fagin R.A. Normal Form for Relational Databases That is Based on Domains and Key //ACM Transactions on Database Systems. 1981. -V.6, №3. - P.387-415.

11. Gray J., Chaudhuri S., Bosworth A., etc. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals // Data Mining and Knowledge Discovery. 1997. - № 1. - P. 2953.

12. Halpin T. Using Object Role Modelling to Design Relational Databases: Interview.//DBMS, 1995. V. 8. No. 9 (September). P. 38.

13. Harinarayan V., Rajaraman A., Ullman J. D. Implementing Data Cubes Efficiently // SIGMOD Conference. Montreal, CA. -1996.

14. Krattenthaler C., Schlosser M. A new multidimensional matrix inverse with applications to multiple q-series // Discrete Mathematics. 1999. Vol.204 . P. 249-279.

15. Langefors B. Infological model and information user views //Inform. Systems, no. 5, 1980, p. 17-32.

16. Langefors B. Information systems //Information Processing-74. -Amsterdam: North-Holland. 1974, p. 937-945.

17. Mukha V.S. State model for scalar random field // Computer Data Analysis and Modeling. Robust-ness and Computer Intensive Methods / Proceeding of the Sixth International Conference. Minsk, September 10-14, 2001. Vol. 2. P. 137-141.

18. Mumick I. S., Quass D., Mumick B. S. Maintenance of Data Cubes and Summary Tables in a Warehouse. Stanford University, Database Group, 1996

19. Parsaye K. A Characterization of Data Mining Technologies and Processes // The Journal of Data Warehousing. -1998.-№ 1.

20. R. Kimball, The Data Warehouse Toolkit // Practical Techniques for Building Dimensional Data Warehouses, John Wiley & Sons, New York, 1996

21. Ramakrishnan R. Database management systems. // McGraw-Hill, 1997.

22. Sundgren B. An infological approach to data bases. Stockholm // National Central Bureau of Statistics. 1973. - 294 p.

23. Sundgren B. Data base design in theory and practice. Toward an integrated metodology // Proc.of 4th Intern. Conf. on VLDB. West Berlin, 1978, p. 3-16.

24. Ullman J.D. Principles of Database and Knowledge-Base Systems. Volume II: The New Technologies. Computer Science Press, 1989.

25. А. Горев, С. Макашарипов, P. Ахаян Эффективная работа с СУБД //СПб, «Питер», 1997, 704с.

26. Альперович М. Введение в OLAP и многомерные базы данных, http://www.cfin.ru/itm/olap/intro.shtml7printversion.

27. Амосов А. А., Колпаков В.В. Скалярно-матричное дифференцирование и его приложения к конструктивным задачам теории связи // Проблемы передачи информации. 1972. № 8. Вып. 1. С. 3-15.

28. Атре Ш. Структурный подход к организации баз данных. -М.: Финансы и статистика, 1983. 320 с.

29. Бекаревич Ю. Б., Пушкина Н. В., Смирнова Е. Ю. Управление базами данных. СПб.: Изд. СПбГУ, 1999.

30. Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем. М.: Финансы и статистика ,1989.

31. Бойко В.В., Савинков В.М. Проектирование информационной базы автоматизированной системы на основе СУБД. -М.: Финансы и статистика, 1982. 174 с.

32. Боуман Д, Эмерсон С., Дарновски М. Практическое руководство по SQL. Киев: Диалектика, 1997.

33. В. М. Банников, Е. Г. Гендель, В. И. Мунерман, Б. Ш. Шкляр. Оптимизация процессов обработки данных на базе алгебраических моделей. Киев: Наукова думка. "Управляющие системы и машины" № 6, 1985 г.

34. Виноградов М.М. Модели данных и отображения моделей данных: алгебраический подход. // Теория и приложения систем баз данных. М.: ЦЭМИ АП СССР, 1984.

35. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989.

36. Вон К. Технология объектно-ориентированных баз данных.// Открытые системы, 1994. Вып. 4 (8). Осень.Р. 14.

37. Вон Ким Технологии нишевых баз данных: ретроспективный взгляд // Открытые системы, №4, 2004 г.

38. Гарсиа-Молина, Гектор, Ульман, Джеффри, Д., Уидом, Дженнифер Системы баз данных. Полный курс. : Пер. с англ. М. : Издательский дом «Вильяме», 2004.- 1088 с.

39. Гилуа М.М. Множественная модель данных в информационных системах. М.: Наука, 1992.

40. Голосов А.О. Аномалии в реляционных базах данных // СУБД. 1986. - №3. - С.23-28.

41. Д.Цикритзис, Ф.Лоховски. Модели данных. М.: Финансы и статистика, 1985

42. Дейт К. Введение в системы баз данных //6-издание. Киев: Диалектика, 1998. - 784 с.

43. Диго С.М. Проектирование и использование баз данных. -М.: Финансы и статистика, 1995. 208 с.

44. Е. Г. Гендель, В. И. Мунерман. Применение алгебраических моделей для синтеза процессов обработки файлов. Киев: Наукова думка. "Управляющие системы и машины" № 4, 1984 г.

45. Замулин A.B. Системы программирования баз данных и знаний // Новосибирск: Наука. Сибирское отделение, 1990. 351 с.

46. Замулин A.B. Типы и модели данных //Банки данных: Материалы 3-й Всесоюзной конф. (Таллин, 24-26 сентября 1985 г.). -Таллин: ТПИ, 1985, с. 3-15.

47. Злуф М.М. Query-by-Example: язык баз данных // СУБД. -1996. №3. - С.149-160.

48. Ильин В.А., Позняк Э.Г. Линейная алгебра. М.: Наука, 1974. 296 с.

49. Как работать над терминологией. Основы и методы КНТТ АН СССР. М.: Наука, 1968. - 76 с.

50. Калло Д. Матричная производная для статистики. Тарту, 1991. 155 с.

51. Карпова Т.С. Базы данных. Модели, разработка, реализация. СПб: Питер, 2001.

52. Когаловский М.Р. Абстракции и модели в системах баз данных. // СУБД, 4-5/1998, с. 73-81.

53. Когаловский М.Р. Архитектура механизмов отображения данных в многоуровневых СУБД //Техника реализации многоуровневых систем управления базами данных. М.: ЦЭМИ АН СССР, 1982, с. 3-19.

54. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1972. 496 с.

55. Коннолли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика 3-е изд. - М.: «Вильяме», 2003.

56. Коровкин С. Д., Левенец И. А., Ратманова И. Д., Старых В. А., Щавелёв Л. В. Решение проблемы комплексного оперативного анализа информации хранилищ данных // СУБД. 1997. - № 5-6. - С. 4751.

57. Кренке Д. Теория и практика построения баз данных: (пер.с англ) // Д. Кренке. 9-е изд. - СПб.: Питер, 2005. - 858 с.

58. Кречетов Н., Иванов П. Продукты для интеллектуального анализа данных // ComputerWeek. М. - 1997. - № 14-15. - С. 32-39.

59. Кузнецов С. Д. Основы баз данных. 1-е изд. - М.: «Интернет-университет информационных технологий - ИНТУИТ.ру», 2005.

60. Кузнецов С.Д. Базы данных: языки и модели. // Издательство «Бином». М. - 2008. - С. 720.

61. Кузнецов С.Д. Дубликаты, неопределенные значения, первичные и возможные ключи и другие экзотические прелести языка SQL // СУБД. 1997. - №3. - С.77-80.

62. Ладыженский Г.М. Системы управления базами данных -коротко о главном // СУБД. 1995. - №1,2,3,4.

63. Левин H.A., Мунерман В.И., Сергеев В.П. Алгебра многомерных матриц как универсальное средство моделирования данных и ее реализация в современных СУБД // Системы и средства информатики. -М.: Наука, Вып. 14. 2004 г. С. 86-99.

64. Левин H.A., Мунерман В.И., Сергеев В.П. Применение многомерных матриц в запросах пользователей к базам данных //Проблемы и методы информатики. II Научная сессия ИЛИ РАН:

65. Тезисы докладов / Под ред. И.А. Соколова. — М.: ИЛИ РАН, 2005 г. Стр. 81-86.

66. Левин H.A., Сергеев В.П. Иерархическое представление алгебры многомерных матриц . Деп. ВИНИТИ 12.09.06. №1149-В2006, 13 с.w

67. Ленгсам И., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. М.: Мир, 1989.

68. Мальцев А.И. Алгебраические системы. М.: Наука, 1970.392 с.

69. Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир, 1980. - 662 с.

70. Мейер М. Теория реляционных баз данных. М.: Мир, 1987. - 608 с.

71. Милов Л.Т. Многомерно-матричные производные и анализ чувствительности систем автоматического управления // Автоматика и телемеханика. 1979. № 9. С. 15-25.

72. Милов Л.Т. Многомерные матрицы при обработке массивов данных // Управление. Передача, преобразование и отображение информации / Межвуз. сб. статей. Рязань, 1977. Вып. 4. С. 3-11.

73. Муха B.C. Многомерно-матричные производные и разложение функции нескольких переменных в ряд Тейлора // Автоматика и вычислительная техника. 1987. Вып. 16. С. 65-71.

74. Муха B.C. Многомерно-матричный подход к оцениванию реализаций векторных нестационарных процессов // Докл. 12-го науч.-техн. семинара "Статистический синтез и анализ информационных систем". Москва-Черкассы, 23-25 июня 1992 г. С. 137-139.

75. Муха B.C. Моделирование многомерных систем и процессов. Многомерно-матричный подход // Ме-тодическое пособие для аспирантов и научных работников. Мн.: БГУИР,1998. 40 с.

76. Муха B.C. Пакет научных программ "Анализ многомерных данных" // Тр. Всерос. научн. конф. "Проектирование научных и инженерных приложений в среде MATLAB". М.: ИПУ РАН, 2002. С. 276-284.

77. Нагао М., Катаяма Т., Уэмура С. Реализация языка SQL в СУБД MySQL. М.: Мир, 2006 г. - 350 с.

78. Нагао М., Катаяма Т., Уэмура С. Структуры и базы данных. -М.: Мир, 1986. 197 с.

79. Оззу М.Т., Валдуриз П. Распределенные и параллельные системы баз данных //СУБД. 1996. - №4. - С.4-26.

80. Озкарахан Э. Машины баз данных и управление базами данных. М.: Мир, 1989.

81. Пржиялковский В.В. Сложный анализ данных большого объема: новые перспективы компьютеризации // СУБД. 1996. - № 4. -С. 71-83.

82. Пржиялковский В.В. Абстракции в проектировании баз данных // СУБД, 1-2/98, с. 90-97.

83. Прохоров А, Определение оптимальной структуры базы данных // Informix magazine. Русское издание. 1998. - Апрель.

84. Савинков В.М., Вейнеров О.М., Казаров М.С. Основные концепции автоматизации проектирования баз данных //Прикладная информатика. Вып.1. М.: Финансы и статистика, 1982, с. 30-41.

85. Сахаров A.A. Концепция построения и реализации информационных систем, ориентированных на анализ данных // СУБД.- 1996. -№4. -С. 55-70.

86. Сахаров A.A. Принципы проектирования и использования многомерных баз данных (на примере Oracle Express Server) // СУБД. -1996.-№3.-С. 44-59.

87. Семизельникова O.A. Исследование возможностей CASE-технологии при создании интеллектуальных систем управления. // Информационные технологии. 2006. www.inftech.webservis.ru.

88. Сергеев В.П. Векторно-матричная модель представления данных. // Вестник компьютерных и информационных технологий. М.: Изд-во Машиностроение, 2010. 6. С.3-8

89. Сергеев В.П. Использование алгебры многомерных матриц для работы с данными на параллельных ЭВМ. Системы компьютерной математики и их приложения: материалы международной конференции.- Смоленск: СмолГУ, 2006.- Вып. 7. Стр. 90-92.

90. Сергеев В.П. Оптимизация структур данных в распределенных педагогических системах. // Методология и методика информатизации образования: концепции, программы, технологии:

91. Материалы Всероссийской научно-практической конференции (26-28 января 2004 года). Смоленск: изд-во СГПУ, 2004. - Стр. 127-130.

92. Сергеев В.П. Реализация матричной модели данных в иерархических структурах. Математическая морфология. Электронный математический и медико-биологический журнал. - Т. 6. - Вып. 2. -2007.

93. Скотт В. Эмблер, Прамодкумар Дж. Садаладж. Рефакторинг баз данных: эволюционное проектирование М.: «Вильяме», 2007.

94. Соколов Н.П. Введение в теорию многомерных матриц. -Киев: Наукова думка, 1972.

95. Тиори Т., Фрай Д. Проектирование структур баз данных. В 2 кн., М.: Мир, 1985. Кн. 1. - 287 е.: Кн. 2. - 320 с.

96. Трамбле Ж., Соренсон П. Введение в структуры данных. М.: Машиностроение, 1982.

97. Туо Дж. Инструменты для анализа информации на настольных ПК // ComputerWeek-Москва. 1996. - № 38. - С 34-35, 46.

98. Ф.Р. Гантмахер. Теория матриц. М.: Наука, 1988. 552 с.

99. Феденя O.A. Многомерные матрицы и некоторые экстремальные комбинаторные задачи: Дис. канд. физ.-мат. наук. 1978. 103 с.

100. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989. 656 с. 49

101. Цикритизис Д., Лоховски Ф. Модели данных. М.: Финансы и статистика, 1985. - 344 с.

102. Чамберлин Д.Д., Астрахан М.М., Эсваран К.П., Грифитс П.П., Лори P.A., Мел Д.В., Райшер П., Вейд Б.В. SEQUEL 2: унифицированный подход к определению, манипулированию и контролю данных // СУБД. 1996. - №1. - С.144-159.

103. Чаудхари С. Методы оптимизации запросов в реляционных системах // СУБД. 1998. - №3. - С.22-36.

104. Шрейдер Ю.А., Шаров A.A. Системы и модели . М.: Радио и связь. 1982. - 152 с.