Буй Дмитро Борисович. Теорія програмних алгебр композиційного типу та її застосування: Дис... д- ра фіз.-мат. наук: 01.05.03 / Київський національний ун-т ім. Тараса Шевченка. - К., 2002. - 364арк. - Бібліогр.: арк. 313-329.
Анотація до роботи:
БУЙ Д. Б. Теорія програмних алгебр композиційного типу та її застосування. – Рукопис.
Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.03 – математичне та програмне забезпечення обчислювальних машин і систем. – Київський національний університет імені Тараса Шевченка, Київ, 2002.
Мета – побудова формальних моделей програм на основі програмних алгебр композиційного типу. Об‘єкт дослідження – загальнозначні дескриптивні та декларативні структури програм, маніпуляційні дії в базах даних, мови маніпулювання даними SQL-подібних мов (DML-мови). Метод – побудова і дослідження програмних алгебр суперпозицій та рекурсій; програмних алгебр функцій, що зберігають денотати; табличних алгебр і SQL-орієнтованих програмних алгебр. Основні результати: створення загальної теорії розв‘язування систем рівнянь, асоційованих з рекурсіями; дослідження монотонності та неперервності суперпозицій і рекурсій, взаємозв‘язку між ними; вирішення проблем повноти для функцій, що зберігають денотати; дослідження взаємної похідності табличних операцій; визначення повної семантики операторів DML-мов.
Основним результатом дисертації є побудова нової теорії програмних алгебр композиційного типу для розв’язання важливої наукової проблеми розробки складних програмних систем різного призначення. Це твердження, зокрема, обґрунтоване у дисертації шляхом застосування розробленої теорії до визначення повної семантики мов маніпулювання даними у SQL-подібних мовах.
Найважливіші результати роботи:
Розроблена загальна теорія розв‘язування систем рівнянь, асоційованих з рекурсіями: встановлена структура множини всіх розв‘язків, залежність розв‘язків від початкових наближень, параметрів та функцій правих частин; отримані нижні та верхні оцінки найменших розв‘язків, які узагальнюють оцінки відомих теорем теорії рекурсивних програм – теорем Парка про індукцію нерухомої точки, Кадью та Війємана про безпечні правила обчислення; обґрунтована коректність застосування методу Гаусса до розв‘язування систем; встановлено, що загальнозначні перетворення систем типу підстановки зберігають найменші розв‘язки (це є узагальненням важливої теореми Війємана про інваріантні перетворення нерухомої точки в теорії рекурсивних програм).
Побудована і досліджена програмна алгебра суперпозицій та рекурсій, яка виступає моделлю загальнозначних дескриптивних і декларативних структур програм. Для цієї алгебри досліджена монотонність і неперервність суперпозиції за окремими аргументами; встановлена монотонність рекурсії та неперервність обмежень рекурсії на класи неперервних функцій; доведена замкненість класів монотонних (неперервних) функцій відносно рекурсії; встановлений взаємозв‘язок між сигнатурними операціями, зокрема, показана похідність багатомісної рекурсії відносно унарних рекурсій та суперпозиції.
Побудовані і досліджені програмні алгебри функцій, які зберігають денотати; функції носіїв цих алгебр виступають параметричними моделями маніпуляційних дій у різних універсумах даних, самі алгебри є інструментом розв‘язання проблеми синтезу маніпуляційних дій. Вирішені проблеми повноти для програмних алгебр обчислюваних функцій, що зберігають денотати для основних оцінок універсуму іменних даних.
На основі узагальнення класичних реляційних алгебр Кодда побудована таблична алгебра, яка уточнює інформаційний та маніпуляційний аспект реляційних баз даних. Шляхом виділення специфічних характеристичних властивостей повністю розв‘язана проблема взаємної похідності сигнатурних операцій табличної алгебри та окреслена виразна сила цих операцій.
Побудована SQL-орієнтована програмна алгебра іменних функцій, засобами якої адекватно задана повна формальна семантика операторів маніпулювання даними SQL-подібних мов.
З результатів дисертації випливають такі основні висновки:
для побудови загальної теорії розв‘язування рівнянь, асоційованих з рекурсіями, суттєва саме монотонність функцій; їхня неперервність забезпечує спрощення устрою множини розв‘язків; залежність розв‘язків від початкових наближень, параметрів та монотонних (неперервних) функцій успадковує тип функцій; найменші нерухомі точки мають природні верхні та нижні оцінки, які узагальнюють оцінки Парка, Кадью, Війємана;
принципово різна інтенсіональна роль пасивності чи активності функцій-аргументів суперпозиції проявляється у властивостях монотонності (неперервності) чи не монотонності (не неперервності) цієї програмологічної операції за різними аргументами; інтенсіональні властивості структур іменування проявляються як на рівні функції іменування, так і на рівні композиції суперпозиції за значенням;
програмні алгебри функцій, що зберігають денотати, є експлікативним засобом вирішення проблеми синтезу маніпуляційних дій;
таблична алгебра адекватно уточнює основні маніпуляції коддовського типу над таблицями; разом з тим, суттєві особливості реальних СУБД не моделюються в цих алгебрах і потребують розгляду більш виразних потужних моделей;
сигнатурні операції табличних алгебр об‘єднання, селекція, проекція, з‘єднання, перейменування, активне доповнення мають принципові відмінності, які проявляються у непохідності цих операцій відносно решти операцій; таблична алгебра має принципові обмеження своїх виразних можливостей: зокрема, агрегатні функції та операції, пов‘язані з обчислюваними атрибутами, не виражаються в збагаченнях табличної алгебри довільними константами;
SQL-орієнтована програмна алгебра іменних функцій є експлікативним засобом визначення повної семантики операторів маніпулювання даними SQL-подібних мов.
Таким чином, можна стверджувати, що побудовані в дисертаційній праці програмні алгебри композиційного типу абстрактного та іменного рівнів абстракції утворюють багату змістовну теорію, яка природно застосовується для визначення повної та формальної семантики мов реляційних СУБД та інших складних програмних систем.
Публікації автора:
Редько В. Н., Брона Ю. Й., Буй Д. Б., Поляков С. А. Реляційні бази даних: табличні алгебри та SQL-подібні мови. – Київ: “Академперіодика”, 2001. – 198 с.
Редько В. Н., Буй Д. Б., Загорский С. П. Манипуляционный аспект баз данных: композиционный подход // Кибернетика. – 1989. – № 6. – С. 105-113.
Буй Д. Б., Редько В. Н. Программологические аспекты метода неподвижной точки // Кибернет. и систем. анализ. – 1994. – № 5. – С. 158-167.
Буй Д. Б., Редько В. Н. Неподвижные точки и операторы замыкания: программологические аспекты // Кибернет. и систем. анализ. – 1995. – № 1. – С. 113-121.
Брона Ю. Й., Буй Д. Б. Про різні способи задання іменних даних // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – Київ: Хрещатик. – 1994. – С. 186-194.
Редько В. Н., Буй Д. Б. К основаниям теории реляционных баз данных // Кибернет. и систем. анализ. – 1996. – № 4. – С. 3-13.
Буй Д. Б., Брона Ю. Й. Теоретико-множинні конструкції в теорії реляційних баз даних // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1996. – Вип. 1. – С. 216-224.
Редько В. Н., Брона Ю. И., Буй Д. Б. Взаимная непроизводность и выразительная сила операций реляционных алгебр // Доповіді НАН України. Математика. Природознавство. Технічні науки. – 1996. – № 11. – С. 84-88.
Редько В. Н., Брона Ю. И., Буй Д. Б. Информационный аспект Case-технологий: основные соотношения в табличных алгебрах // Проблемы программирования. – 1997. – Вып. 1. – С. 5-11.
Редько В. Н., Брона Ю. И., Буй Д. Б. Реляционные алгебры: операции проекции и соединения // Кибернет. и систем. анализ. – 1997. – № 4. – С. 89-100.
Редько В. Н., Брона Ю. И., Буй Д. Б. Реляционные алгебры: операции деления и переименования // Кибернет. и систем. анализ. – 1997. – № 5. – С. 3-15.
Буй Д. Б. Системи рівнянь в індуктивних множинах: операція рекурсії та метод Гаусса виключення невідомих // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1997. – Вип. 4. – С.118-123.
Буй Д. Б. Загальні властивості операції рекурсії // Вісник Львівського ун-тету. Сер. мех.-мат. – 1998. – Вип. 50. – С. 21-23.
Буй Д. Б. Неперервність в індуктивних множинах: основні поняття та допоміжні результати // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1998. – Вип. 1. – С. 142-148.
Буй Д. Б. Неперервність в індуктивних множинах: неперервність суперпозиції та суміжні результати // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1998. – Вип. 2. – С. 187-195.
Буй Д. Б. Неперервність в індуктивних множинах: неперервність рекурсії та суміжні результати // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1998. – Вип. 3. – С. 128-138.
Буй Д. Б. Неперервність в індуктивних множинах: рекурсія, індукована системами рівнянь // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1998. – Вип. 4. – С. 85-96.
Буй Д. Б. Непрерывность в индуктивных множествах. Часть 1: суперпозиция // Проблемы программирования. – 1998. – Вып. 3. – С. 3-14. Часть 2: рекурсия // Там же. – 1998. – Вып. 4. – С. 3-19.
Буй Д. Б., Поляков С. А. Композиційна семантика SQL-подібних мов: табличні структури даних, композиції, приклади // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1999. – Вип. 1. – С. 130-140.
Буй Д. Б., Поляков С. А. Композиційна семантика SQL-подібних мов: мультимножини, рядки, впорядковані таблиці // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1999. – Вип. 2. – С. 183-194.
Буй Д. Б. Системи рівнянь в індуктивних множинах // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1999. – Вип. 3. – С. 147-171.
Брона Ю. Й., Буй Д. Б., Поляков С. А. Композиційна семантика SQL-подібних мов: операції з’єднання // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 1999. – Вип. 4. – С. 100-104.
Брона Ю. Й., Буй Д. Б., Загорський С. П., Поляков С. А. Композиційна семантика SQL-подібних мов: агрегатні функції // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 2000. – Вип. 1. – С. 178-192.
Брона Ю. Й., Буй Д. Б., Загорський С. П., Поляков С. А. Композиційна семантика SQL-подібних мов: групування, маніпулювання даними, приклади // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 2000. – Вип. 2. – С. 177-185.
Буй Д. Б. Cистеми рівнянь в індуктивних множинах: метод Гаусса, інваріантні перетворення, взаємозв‘язок між рекурсією та суперпозицією, похідність багатомісної рекурсії // Проблемы программирования. – 2000. – № 1-2. – С. 63-74.
Буй Д. Б. Композиційна семантика маніпуляційних дій: збереження денотатів, характеристики, обчислюваність, необхідні умови повноти // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. – 2002. – Вип. 1. – С. 169-188.
Буй Д. Б. Решение систем уравнений методом Гаусса // Проблемы теоретической кибернетики. Тезисы докладов XII Международ. конф. (Нижний Новгород, 17 - 22 мая 1999 г.). Ч. 1. – Москва: Изд-во мех.-мат. ф-тета МГУ. – 1999. – С. 28.
Brona J., Buy D., Zagorsky S., Poliakov S. Compositional semantics of SQL // Proc. of the Fourth Int. Scientific Conf. “Electronic Computers and Informatics’2000” (September 28 - 29, 2000, Kosice – Herlany, Slovakia). – Kosice. – 2000.– P. 287-292.
Buy D. The decision of equation systems in inductive sets // Proceedings of the Fourth Int. Scientific Conf. “Electronic Computers and Informatics’2000” (September 28 - 29, 2000, Kosice – Herlany, Slovakia). – Kosice. – 2000.– P. 44-49.
Brona J., Buy D., Zagorsky S., Poliakov S. Compositional approach of the semantics of SQL // Fifth Int. Conf. “Information Theories & Applications” (September, 1 - 15, 2000, Varna, Bulgaria). Abstracts. – Sofia: FOI-COMMERE. – 2000. – P. 33-34.
У спільно виконаних роботах науковому консультанту В. Н. Редьку належить загальна постановка проблеми побудови і дослідження програмних алгебр різних рівнів абстракції [1-4, 6, 8-11], обговорення та інтерпретація результатів; С. П. Загорському – встановлення нескорочуваності систем породжуючих програмних алгебр іменних функцій [2]; Ю. Й. Броні – проведення доведень еквівалентності різних означень іменних даних [5], дослідження властивостей сигнатурних операцій табличних алгебр [1, 7-11]; С. А. Полякову, С. П. Загорському та Ю. Й. Броні – опис змістовної семантики операторів маніпулювання даними мови SQL, опрацювання промислових версій СУБД MS SQL Server, Informix, Oracle, Sybase SQL Server, еталонування операторів цієї мови засобами SQL-орієнтованої програмної алгебри [1, 19, 20, 22-24, 28, 30].
