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

Российская Академия наук

Институт теоретической астрономии

1Г» Он

На правах рукописи

КРАШЕНИННИКОВ Сергей Вениаминович

Управление данными в системе Таблично-ориентированного программирования

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

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

Санкт-Петербург 1996

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

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

кандидат физико-математических наук Ф. А. Новиков. Официальные оппоненты:

доктор физико-математических наук А. Н. Томилин доктор технических наук С. Д. Кузнецов.

Ведущая организация — Санкт-Петербургский государственный технический университет.

Защита диссертации состоится " ^ " А^/^ _ 1996 г.

в ^_ часов на заседании Диссертационного совета К 200.45.01

по присуждению ученой степени кандидата физико-математических наук при Институте высокопроизводительных вычислительных систем Российской Академии наук по адресу: 117312, Москва, ул. Вавилова, д. 37.

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

Автореферат разослан "__"__1996 г.

Ученый секретарь

Диссертационного совета К 200.45.01

кандидат физико-математических наук

Миронов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

вательно, не жизнеспособных) универсальных инструментальных систем программирования.

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

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

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

1 Разработка была поддержана РФФИ: проект "АстроТОП" (грант № 94-02-05296)

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

Научная новизна работы заключается в следующем:

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

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

— получено строгое соотношение ТОП-модели и классических моделей данных; доказана реляционная полнота ТОП-модели как модели данных;

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

— построена операционная семантика операций ТОП-алгебры, позволяющая теоретически промоделировать функционирование ТОП-модели;

— разработана и реализована инструментальная интегрированная программная оболочка, настраиваемая на предметную область пользователя.

Научная и практическая ценность. Научное значение работы со-

эит в том, что впервые удалось построить строгую математическую

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

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

1. новая концепция управления данными в информационных системах сбора, хранения и обработки наблюдательной (экспериментальной) информации — модель Таблично-ориентированного программирования (ТОП-модель);

2. формальное описание ТОП-модели;

3. доказательство реляционной полноты ТОП-модели (как модели данных);

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

5. операционная семантика ТОП-алгебры;

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

— XI научной школе по ППП "Программное обеспечение математического моделирования, управления и искусственного интеллекта", Адлер, 1991.

— Всесоюзном совещании "Компьютерные методы небесной механики", С.-Петербург, 1991.

— Всероссийском совещании "Компьютерные методы небесной механики", С.-Петербург, 1992.

— Международной конференции "Современные проблемы теоретической астрономии", С.-Петербург, 1994.

— Конференции "Информационные системы в науке — 95", Москва, 1995.

— Всероссийской конференции с международным участием "Компьютерные методы небесной механики — 95", С.-Петербург, 1995.

— Семинаре Института высокопроизводительных вычислительных систем РАН, Москва, 1995.

— Семинаре отдела компьютеризации астрономических исследований Института теоретической астрономии РАН, С.-Петербург, 1995.

— Семинаре кафедры Прикладной математики Санкт-Петербургского государственного технического университета, С,-Петербург, 1995.

Структура и объём диссертации. Диссертация состоит из введе-шя, трёх глав, заключения, списка литературы из 104 наименований. Гекст диссертации изложен на 121 странице, включая список литературы на 13 страницах. Диссертация подготовлена средствами системы сомпьютерной верстки 1АТ]т;Х.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В этой главе проведено условное разбиение информационных систем 1С) на системы, ориентированные, главным образом, на организацию груктур хранения данных и доступа к ним (классические БД, инстру-ентальные СУБД) и системы, предназначенные для алгоритмической 5работки различных наборов данных (ППП, инструментальные ППП,

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

Среди классических БД и инструментальных СУБД рассматривались, в частности, системы КОМПАС, Advanced Revelation, Data Flex, FoxPro, Clarion Database Developer, MS Access, Paradox и др. Данные системы демонстрируют классический подход для коммерческих ИС, а именно:

• гибкие средства для организации хранения сложных структур данных и доступа к ним;

• интенсивное обновление БД и порожденные этим проблемы сохранения целостности БД (в частпости, при коллективном доступе);

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

• мощные средства организации интерфейса.

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

• импорт наблюдений из ASCII формата в формат используемой СУБД;

• подготовка набора данных (в рамках инструментария СУБД) для вычислений (т.е. формулировка и выполнение запроса);

• экспорт подготовленных данных в ASCII формат;

• проведение вычислений над подготовленными данными (в ASCII формате) с помощью существующих комплексов программ (в подавляющем большинстве — Фортран-программ).

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

В отношении ИС, ориентированных на алгоритмическую обработкз данных, нужно заметить, что это либо системы, создающие ППП, кото рые в последствии функционируют самостоятельно (ВИЛЬНЮС-2), либ(

интегрированные управляющие оболочки, обладающие средствами создания ППП (или адаптации уже существующих ППП) (ИСПАК, САТУРН, СПОРА). Данные системы, приобретая черты универсальных систем программирования, вместе с тем становятся чрезмерно переусложненными как внутренне, со стороны организации вычислительного процесса в целом, так и внешне, со стороны пользователя. Кроме того, каждая такая система имеет свой особый способ организации структурного хранения данных и доступа к ним, что рождает проблемы при развитии и распространении системы, а также при использовании альтернативного инструментария.

Наибольший интерес для анализа представляли системы класса СПБ-ДиЗ. Это направление возникло на стыке направлений развития систем программирования и систем управления базами данных и знаний, и, по всей вероятности, именно оно определяет на сегодняшний день критерии для создаваемых инструментальных систем программирования. Общая идея систем данного класса сводится к попытке органически соединить возможности алгоритмических языков и средства работы с БД. Все эти системы (БОЯЗ, ДПБЛ, PLAIN, TAXIS, ADAPLEX, GALILEO, Ирис, ATJIAHT и др.) представляют собой среду программирования, ориентированную, прежде всего, на профессиональных программистов, которые с помощью системных средств создают уже конкретную ИС для конечных пользователей. Данные системы содержат много интересных концептуальных идей (например: сканирующий оператор, просматривающий все или выделенные компоненты указанного набора данных (БОЯЗ, GALILEO, ADAPLEX, ОРИОН, АТЛАНТ); сопряжение реляционной и объектно-ориентированной моделей данных (TAXIS, Ирис); введение операций над типами записей (АТЛАНТ) и др.), но, к сожалению, при разработке этих СПБДиЗ авторы стремились создать максимально универсальные ИС, и, видимо, не имели в виду применение систем в таких предметных областях (или преимущественно в таких) как астрономия, и это существенно сказалось на некоторой усложненности используемых моделей данных.

Далее в первой главе рассматриваются некоторые астрономические шформационные проекты, которые представляют собой либо замкнутые 1ПП (если речь идет о вычислительной обработке наблюдательной информации — STAMP, CERES и др.), либо просто хранилища данных SIMBAD). Кроме того, приводится краткая история создания и развития концепции Таблично-ориентированного программирования.

В заключительной части главы формулируются критерии, которым

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

Во второй главе дается формальное описание модели Таблично-

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

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

• сложение таблиц: Я + Б (заголовок суммы является пересечением заголовков слагаемых. В сумму сначала входят все "усеченные" новым заголовком кортежи первого слагаемого, а затем все (также, возможно, "усеченные") кортежи второго слагаемого);

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

• выборка из таблицы по условию: ЮР (в итоговую таблицу входит часть кортежей исходной таблицы, а именно те, которые удовлетворяют заданному условию. Заголовок таблицы не меняется);

• разность таблиц: Я — Б (заголовок разности таблиц Л и 5 остается таким же как у таблицы Я. В итоговую таблицу входят те кортежи из таблицы К, которые не совпадают ни с одним кортежем таблицы 5 по общим для Я в 5 атрибутам);

• соединение таблиц: Я* Б (заголовок соединения таблиц Я и 5 является объединением заголовков таблиц Я и 5. Кортежи соединения образуются следующим образом: для каждого кортежа г таблицы Я из таблицы 5 (при последовательном порядке просмотра кортежей) выбираются те кортежи в, значения в которых совпадают со значениями кортежа г по пересекающимся атрибутам. Для каждого такого кортежа в в итоговую таблицу записывается кортеж г, дополненный значениями из й в соответствии с заголовком итоговой таблицы);

• склейка таблиц: Я | 5 (заголовок склейки таблиц Я и Б является объединением заголовков таблиц Я и 5. Кортежи склейки образуются следующим образом: г-тый кортеж итоговой таблицы является

объединением г-тых кортежей таблиц Я и Б (при последовательном порядке просмотра кортежей). В том случае, если одна таблица оказывается короче — оставшиеся кортежи более длинной исходной таблицы не входят в итоговую таблицу);

в применение действия: Я/ (в итоговую таблицу входят кортежи, полученные применением действия к исходным кортежам);

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

• итерация таблицы: N ■ Я (итерация — это просто ЛГ-кратное повторение (сложение) кортежей исходной таблицы. Заголовок таблицы не меняется);

5десь И,Б — таблицы модели; X — множество атрибутов (переменных гредметной области); Р — предикат; { — функциональный модуль, реа-шзующий действие; N — натуральное число.

В работе приводится полное построение алгебраической системы ТОП-годели: детальное рассмотрение основ носителя алгебраической системы; ассмотрение отношений на таблицах; построение сигнатуры и аксиом одели.

Далее разбираются взаимоотношения ТОП-модели (как модели дан-ых) и классических моделей данных (в частности, рассматривается ре-яционная модель и реляционная алгебра Кодда). Анализ алгебраических 1стсм реляционной модели и ТОП-модели приводит к следующим резуль-1там:

• на уровне сигнатур алгебр: сигнатура реляционной алгебры £яе( является редуктом сигнатуры ТОП-алгебры Егор (т.е. С Егор);

• на уровне носителей алгебр: для данной предметной области К (предметная область определяет конечное множество переменных, описывающих ее состояние, а следовательно, конечное множество атрибутов (имен столбцов) для таблиц данных) пространство Е всех реляционных отношений является фактормножеством для пространства А всех ТОП-таблиц по ядру функционального отображения Сдд: А —> К;

• общий вывод: реляционная алгебра Кодда является редуктом ТОП-алгебры. А это означает, что ТОП-модель (как модель данных) реляционно полна.

Для вывода свойств рассматриваемой модели использовалась абстракция пространства актуальных (реальных) таблиц. В частности, были получены канонические формы представления ТОП-таблицы: горизонтальная каноническая форма и вертикальная каноническая форма. Кроме того, данные свойства позволили формально определить место операции сортировки в ТОП-модели.

Далее вводится в рассмотрение основная абстракция модели Таблично-ориентированного программирования — виртуальная таблица. Виртуальная ТОП-таблица есть терм в алгебре слов теории 0хОр - В работе даются еще два определения ТОП-таблицы как ссылочной таблицы, организованной операциями ТОП-алгебры, и как произвольного поддерева дерева задания. Аналогично случаю с актуальными таблицами для определения свойств исследуемой модели проводится построение и анализ пространства виртуальных таблиц.

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

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

Далее проводится построение операционной семантики операций ТОП-алгебры: строится абстрактный итератор, последовательно перебирающий кортежи таблицы и обладающий тремя базовыми логическими операторами:

• 11еас1Р1^ — извлечение первого кортежа таблицы;

• 11еас1Кех1 — извлечение следующего кортежа таблицы;

• Ео£ — определение достижения конца таблицы.

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

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

Далее в данной главе описывается архитектура инструментальной программной системы АстроТОП, построенной на основе концепции Таблично-ориентированного программирования и реализующей описанную выше ТОП-модель; приводится синтаксическое описание языка Таблично-ориентированного программирования и примеры решения некоторых задач, связанных с традиционной и нетрадиционной обработкой наборов данных.

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

ПЕЧАТНЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Крашенинников С. В., Новиков Ф. А., Скрипниченко В. И., Юдо-вин Г. Г. Система таблично-ориентированного программирования. //IX научная школа по ППП "Программное обеспечение математического моделирования, управления и искусственного интеллекта." Тезисы докладов. — Адлер, 1991.

2. Крашенинников С. В. Управление данными в системе таблично-эриентированного программирования. // Всесоюзное совещание "Компьютерные методы небесной механики." Тезисы докладов. — С.-Петербург, 1991. — с. 50-51.

3. Крашенинников С. В. Положение алгебры таблиц системы таб-гачно-ориентированного программирования относительно реляционной шгебры Кодда. // Всероссийское совещание "Компьютерные методы неясной механики." Тезисы докладов. — С.-Петербург, 1992. — с. 30-31.

4. Крашенинников С. В. Сравнительный анализ алгоритмов интер-[ретации табличных выражений. // Препринт ИТА РАН № 30, 1993. — 8 с.

5. Крашенинников С. В. ТОП технология. Некоторые теоретические аспекты. // Международная конференция "Современные проблемы теоретической астрономии." Тезисы докладов. — С.-Петербург, ИТА РАН, 1994. — Том 1. — с. 82-83.

6. Крашенинников С. В., Назаров А. А., Нецветаева Г. А., Новиков Ф. А., Парийская Е. Ю., Скрипниченко В. И. Таблично ориентированное программирование — методология создания информационно-алгоритмического пространства. // Международная конференция "Современные проблемы теоретической астрономии." Тезисы докладов. — С.-Петербург, ИТА РАН, 1994. — Том 1. — с. 84-85.

7. Крашенинников С. В. ТОП технология: формальное описание. // Препринт ИТА РАН № 45, С.-Петербург, 1995. — 35 с.

8. Крашенинников С. В., Новиков Ф. А. АстроТОП — технология сбора, хранения и обработки астрономической информации. // Информационные системы в науке — 95. — М.: Фазис, 1995. — с. 63-64.

9. Крашенинников С. В. АстроТОП: возможный подход к динамическому представлению наборов данных // Компьютерные методы небесной механики — 95. — С.-Петербург, ИТА РАН, 1995. — с. 133-135.

10. Крашенинников С. В., Назаров А. А., Новиков Ф. А., Скрипниченко В. И. АстроТОП: Таблично-ориентированное программирование астрономических задач. // Компьютерные методы небесной механики — 95. — С.-Петербург, ИТА РАН, 1995. — с. 135-137.

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

Подписано к печати

Заказ 52. Тираж 100 экз. Объем 0.7 печ.л. Отпечатано в типографии ИТА РАН. 191187, Санкт-Петербург, наб. Кутузова, 10.