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

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

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

Слайды к докладу в презентации PowerPoint: munerman20110224.ppt

Литература:

1. Codd E.F. A relational model for large shared data banks. Comm. ACM, 13:6 (1970), p. 337-387.
2. Гарсия-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс: Пер. с англ. – М. Издательский дом "Вильямс", 2003. – 1088 с.
3. Гендель Е.Г., Мунерман В.И. Применение алгебраических моделей для синтеза процессов обработки файлов //Управляющие системы и машины. - Киев: Наукова думка, 1984, 4. – с.69-72
4. Гендель Е.Г., Мунерман В.И., Шкляр Б. Ш. Оптимизация процессов обработки данных на базе алгебраических моделей //Управляющие системы и машины. - Киев: Наукова думка, 1985, 6. – с.91-95
5. Емельченков Е.П., Левин Н.А., Мунерман В.И. Математические модели для проектирования информационных систем. – Ежегодник Системы и средства информатики. Специальный выпуск. Математические модели в информационных технологиях. - М.: Наука. – с.210-225
6. Емельченков Е.П., Левин Н.А., Мунерман В.И. Алгебраический подход к оптимизации разработки и эксплуатации систем управления базами данных. Системы и средства информатики/Дополнительный выпуск. – М: Изд. ИПИ РАН, 2009. - 274 с. – с.114-137
7. Соколов Н.П. Введение в теорию многомерных матриц. – Киев: Наукова думка, 1972. – 175 с.
8. Мунерман В.И. Изоморфизм моделей обработки данных. - Системы компьютерной математики и их приложения: материалы международной конференции. - Смоленск: Изд-во СмолГУ, 2009. - Вып. 10.-303 с.-с. 143-145
9. Емельченков Е.П., Левин Н.А., Мунерман В.И. Математические модели для проектирования информационных систем. – Ежегодник Системы и средства информатики. Специальный выпуск. Математические модели в информационных технологиях. - М.: Наука, 2006. – с. 210-225
10. Емельченков Е. П., Мунерман В. И. Алгебраический подход к объектно-ориентированным базам данных – Математическая морфология. Электронный математический и медико-биологический журнал. – Т. 5. – Вып. 4. – 2006. http://www.smolensk.ru/user/sgma/MMORPH/N-12-html/borisov/munerman/munerman.htm
11. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – Киев: Наукова думка, 1989. – 376 с.
12. Бурбаки Н. Теория множеств. – М., "Мир", 1965. – 455 с.

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

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

Литература:

1. E.F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, Volume 13, Number 6, June, 1970
2. В. М. Банников, Е. Г. Гендель, В. И. Мунерман, Б. Ш. Шкляр. Оптимизация процессов обработки данных на базе алгебраических моделей. - Киев: Наукова думка.“Управляющие системы и машины” № 6, 1985
3. Е. Г. Гендель, В. И. Мунерман. Применение алгебраических моделей для синтеза процессов обработки файлов. - Киев: Наукова думка. “Управляющие системы и машины” № 4, 1984
4. Левин Н.А., Сергеев В.П. Иерархическое представление алгебры многомерных матриц. Деп. ВИНИТИ 12.09.06. №1149-В2006
5. Сергеев В.П. Векторно-матричная модель представления данных. //Вестник компьютерных и информационных технологий. - М.: Изд-во Машиностроение, 2010, 6 - С. 3-8
6. Сергеев В.П. Представление многомерных матриц в иерархических структурах для повышения эффективности хранения и процессов обработки данных // Системы и средства информатики. Стохастические технологии и системы - М: ИПИ РАН, Специальный выпуск, 2005
7. Сергеев В.П. Реализация матричной модели данных в иерархических структурах //Математическая морфология. – 2007. – Т. 6. – Вып. 2. – Рег. №042070004/0020. http://sgma.alpha-design.ru/MMORPH/N-14-html/sergeev/sergeev.htm
8. Сергеев В.П., Гайдаенко Т.И., Левин Н.А., Мунерман В.И., Оздемир С.М., Провоторова А.О., Ширай А.Е. Патент на полезную модель «Система представления данных в базе данных» № 82355. Зарегистрирован в Государственном реестре полезных моделей Российской Федерации 20.04.2009 http://www1.fips.ru/fips_servl/fips_servlet?DB=RUPM&rn=5090&DocNumber=82355&TypeFile=html
9. Соколов Н.П. Введение в теорию многомерных матриц. Киев: Наукова думка, 1972.

Известна основная реляционная модель данных E/R, отношения которой включают только простые домены. Сложные домены приводятся к простым с помощью процедуры нормализации. Элементы данных имеют идентификаторы «имя отношения – имя домена». Сами отношения представляют собой индексные массивы элементов данных. Степень кортежей постоянна и совпадает со степенью отношения. Кортежи состоят из неповторяющихся элементов данных.

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

В связи с этим предлагается использовать расширенную реляционную модель данных ERM, отличающуюся от известной модели RM/T включением в состав отношений сложных доменов, каждый из которых состоит из нескольких простых и/или сложных доменов. Сущности модели должны соответствовать информационным образам объектов предметной области. Элементы данных имеют идентификаторы «имя отношения – имя домена – уровень иерархии домена в схеме отношения – номер транзакции записи». Отношения представляют собой ассоциативные массивы элементов данных. Кортежи имеют переменную степень, в общем случае не совпадающую со степенью отношения. В состав кортежей могут включаться повторяющиеся элементы данных.

Слайды к докладу в презентации PowerPoint: vasiliev20110224.ppt

Литература:

1. E.F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, Volume 13, Number 6, June 1970
2. E.F. Codd. Extending the Data Base Relational Model to Capture More Meaning. ACM Transactions on Database Systems, Volume 4, Number 4, December 1979
3. H. Darwen, C.J. Date. The Third Manifesto. ACM SIGMOD, Record 24, Number 1, March 1995
4. М.Р. Когаловский. Энциклопедия технологий баз данных. М., Финансы и статистика. 2002. ISBN: 5-279-02276-4
5. С.Д. Кузнецов. Основы баз данных. М., Бином. 2007. ISBN: 978-5-94774-736-2