Теорія програмних алгебр композиційного типу та її застосування

Об'єднання таблиць схеми # - #, #, #. Перетин # та різниця #задаються аналогічно. Селекція за предикатом # - #, #, де # - частковий предикат на множині рядків. Проекція за множиною атрибутів # - #, #, де # - скінченна множина атрибутів. З'єднання - # #. Ділення таблиць схеми # на таблиці схеми # - #, #, #, де # - схеми, #. Активне доповнення - #, #, де #; тут # - схема таблиці #, а #. Перейменування, що відповідає ін'єктивній функції перейменування атрибутів #, - #, #, #, де # #, #, #- діагональ на множині #, а # - повний образ множини # відносно функції # (змістовно кажучи, атрибути з множини # перейменовуються, а з різниці # - залишаються незмінними).

Дамо означення сигнатурних операцій SQL-орієнтованої програмної алгебри. Вони задаються на багатомісних функціях, аргументи і значення яких належать одній з множин - # (універсальний домен), # (множина рядків), # (множина таблиць). Позначимо множини сім'ї # як #, і розглянемо часткові функції вигляду #, #. Елементи множин # позначимо літерою # з індексами. Семантиками операторів DML мов є функції вигляду #, #, але в процесі побудови таких функцій треба використовувати функції з більш широкого класу. Предикатами назвемо функції вигляду #, #, де # - невизначене логічне значення.

Композиція фільтрації # (у випадку множин) предикату вигляду # ставить у відповідність функцію #, #, довільне значення якої задається узагальненою рівністю # для всіх #, #; #. Композиція взяття повного образу Im (у випадку множин) функції вигляду # ставить у відповідність функцію вигляду #, #, довільне значення якої задається узагальненою рівністю # для всіх #, #; #.

Зафіксуємо функцію вибору елемента з підмножин універсального домену. Композиція агрегування # (у випадку множин) функції вигляду #, # і елементу # ставить у відповідність функцію вигляду #, значення якої задаються індукцією за числом елементів скінченних множин:

Аналогічно вводяться композиції фільтрації, взяття повного образу та агрегування для мультимножин, які моделюють таблиці з дублікатами рядків (пп. 5.3.3, 5.3.5). Композиція агрегування дозволяє розповсюджувати багатомісні функції на множини (мультимножини); конкретні функції, необхідні для побудови агрегатних функцій мови SQL, наведені у табл. 5.3.

Основний результат розд. 5 полягає в наступній тезі, у формулюванні якої фігурує множина базових функцій та предикатів #, що містить: теоретико-множинні операції об`єднання, перетину та різниці таблиць; функцію вилучення дублікатів; функцію побудови упорядкованих таблиць; предикати та функції, потрібні для побудови агрегатних функцій композицією агрегування; функцію групування; операції внутрішнього і зовнішнього з`єднання; операції кон`юнкції, диз`юнкції та заперечення тризначної логіки; операцію об`єднання сумісних рядків, функції іменування та розіменування рядків за атрибутами; вихідні операції та предикати універсального домену (арифметика, рівність, порядок та ін.).

Теза. Замикання множини базових функцій та предикатів # композиціями фільтрації, взяття повного образу, агрегування та підстановки містить функції, які є семантиками операторів маніпулювання даними SQL-подібних мов.

ВИСНОВКИ

Основним результатом дисертації є побудова нової теорії програмних алгебр композиційного типу для розв'язання важливої наукової проблеми розробки складних програмних систем різного призначення. Це твердження, зокрема, обґрунтоване у дисертації шляхом застосування розробленої теорії до визначення повної семантики мов маніпулювання даними у SQL-подібних мовах.

Найважливіші результати роботи:

Розроблена загальна теорія розв`язування систем рівнянь, асоційованих з рекурсіями: встановлена структура множини всіх розв`язків, залежність розв`язків від початкових наближень, параметрів та функцій правих частин; отримані нижні та верхні оцінки найменших розв`язків, які узагальнюють оцінки відомих теорем теорії рекурсивних програм - теорем Парка про індукцію нерухомої точки, Кадью та Війємана про безпечні правила обчислення; обґрунтована коректність застосування методу Гаусса до розв`язування систем; встановлено, що загальнозначні перетворення систем типу підстановки зберігають найменші розв`язки (це є узагальненням важливої теореми Війємана про інваріантні перетворення нерухомої точки в теорії рекурсивних програм).

Побудована і досліджена програмна алгебра суперпозицій та рекурсій, яка виступає моделлю загальнозначних дескриптивних і декларативних структур програм. Для цієї алгебри досліджена монотонність і неперервність суперпозиції за окремими аргументами; встановлена монотонність рекурсії та неперервність обмежень рекурсії на класи неперервних функцій; доведена замкненість класів монотонних (неперервних) функцій відносно рекурсії; встановлений взаємозв`язок між сигнатурними операціями, зокрема, показана похідність багатомісної рекурсії відносно унарних рекурсій та суперпозиції.

Побудовані і досліджені програмні алгебри функцій, які зберігають денотати; функції носіїв цих алгебр виступають параметричними моделями маніпуляційних дій у різних універсумах даних, самі алгебри є інструментом розв`язання проблеми синтезу маніпуляційних дій. Вирішені проблеми повноти для програмних алгебр обчислюваних функцій, що зберігають денотати для основних оцінок універсуму іменних даних.

На основі узагальнення класичних реляційних алгебр Кодда побудована таблична алгебра, яка уточнює інформаційний та маніпуляційний аспект реляційних баз даних. Шляхом виділення специфічних характеристичних властивостей повністю розв`язана проблема взаємної похідності сигнатурних операцій табличної алгебри та окреслена виразна сила цих операцій.

Побудована SQL-орієнтована програмна алгебра іменних функцій, засобами якої адекватно задана повна формальна семантика операторів маніпулювання даними SQL-подібних мов.

З результатів дисертації випливають такі основні висновки:

для побудови загальної теорії розв`язування рівнянь, асоційованих з рекурсіями, суттєва саме монотонність функцій; їхня неперервність забезпечує спрощення устрою множини розв`язків; залежність розв`язків від початкових наближень, параметрів та монотонних (неперервних) функцій успадковує тип функцій; найменші нерухомі точки мають природні верхні та нижні оцінки, які узагальнюють оцінки Парка, Кадью, Війємана;

принципово різна інтенсіональна роль пасивності чи активності функцій-аргументів суперпозиції проявляється у властивостях монотонності (неперервності) чи не монотонності (не неперервності) цієї програмологічної операції за різними аргументами; інтенсіональні властивості структур іменування проявляються як на рівні функції іменування, так і на рівні композиції суперпозиції за значенням;

програмні алгебри функцій, що зберігають денотати, є експлікативним засобом вирішення проблеми синтезу маніпуляційних дій;

таблична алгебра адекватно уточнює основні маніпуляції коддовського типу над таблицями; разом з тим, суттєві особливості реальних СУБД не моделюються в цих алгебрах і потребують розгляду більш виразних потужних моделей;

сигнатурні операції табличних алгебр об`єднання, селекція, проекція, з`єднання, перейменування, активне доповнення мають принципові відмінності, які проявляються у непохідності цих операцій відносно решти операцій; таблична алгебра має принципові обмеження своїх виразних можливостей: зокрема, агрегатні функції та операції, пов`язані з обчислюваними атрибутами, не виражаються в збагаченнях табличної алгебри довільними константами;

SQL-орієнтована програмна алгебра іменних функцій є експлікативним засобом визначення повної семантики операторів маніпулювання даними SQL-подібних мов.

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Редько В. Н., Брона Ю. Й., Буй Д. Б., Поляков С. А. Реляційні бази даних: табличні алгебри та SQL-подібні мови. - Київ: “Академперіодика”, 2001. - 198 с.

2. Редько В. Н., Буй Д. Б., Загорский С. П. Манипуляционный аспект баз данных: композиционный подход // Кибернетика. - 1989. - № 6. - С. 105-113.

3. Буй Д. Б., Редько В. Н. Программологические аспекты метода неподвижной точки // Кибернет. и систем. анализ. - 1994. - № 5. - С. 158-167.

4. Буй Д. Б., Редько В. Н. Неподвижные точки и операторы замыкания: программологические аспекты // Кибернет. и систем. анализ. - 1995. - № 1. - С. 113_121.

5. Брона Ю. Й., Буй Д. Б. Про різні способи задання іменних даних // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - Київ: Хрещатик. - 1994. - С. 186-194.

6. Редько В. Н., Буй Д. Б. К основаниям теории реляционных баз данных // Кибернет. и систем. анализ. - 1996. - № 4. - С. 3-13.

7. Буй Д. Б., Брона Ю. Й. Теоретико-множинні конструкції в теорії реляційних баз даних // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1996. - Вип. 1. - С. 216_224.

8. Редько В. Н., Брона Ю. И., Буй Д. Б. Взаимная непроизводность и выразительная сила операций реляционных алгебр // Доповіді НАН України. Математика. Природознавство. Технічні науки. - 1996. - № 11. - С. 84-88.

9. Редько В. Н., Брона Ю. И., Буй Д. Б. Информационный аспект Case-технологий: основные соотношения в табличных алгебрах // Проблемы программирования. - 1997. - Вып. 1. - С. 5-11.

10. Редько В. Н., Брона Ю. И., Буй Д. Б. Реляционные алгебры: операции проекции и соединения // Кибернет. и систем. анализ. - 1997. - № 4. - С. 89-100.

11. Редько В. Н., Брона Ю. И., Буй Д. Б. Реляционные алгебры: операции деления и переименования // Кибернет. и систем. анализ. - 1997. - № 5. - С. 3-15.

12. Буй Д. Б. Системи рівнянь в індуктивних множинах: операція рекурсії та метод Гаусса виключення невідомих // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1997. - Вип. 4. - С.118-123.

13. Буй Д. Б. Загальні властивості операції рекурсії // Вісник Львівського ун-тету. Сер. мех.-мат. - 1998. - Вип. 50. - С. 21-23.

14. Буй Д. Б. Неперервність в індуктивних множинах: основні поняття та допоміжні результати // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1998. - Вип. 1. - С. 142-148.

15. Буй Д. Б. Неперервність в індуктивних множинах: неперервність суперпозиції та суміжні результати // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1998. - Вип. 2. - С. 187-195.

16. Буй Д. Б. Неперервність в індуктивних множинах: неперервність рекурсії та суміжні результати // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1998. - Вип. 3. - С. 128-138.

17. Буй Д. Б. Неперервність в індуктивних множинах: рекурсія, індукована системами рівнянь // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1998. - Вип. 4. - С. 85-96.

18. Буй Д. Б. Непрерывность в индуктивных множествах. Часть 1: суперпозиция // Проблемы программирования. - 1998. - Вып. 3. - С. 3-14. Часть 2: рекурсия // Там же. - 1998. - Вып. 4. - С. 3-19.

19. Буй Д. Б., Поляков С. А. Композиційна семантика SQL-подібних мов: табличні структури даних, композиції, приклади // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1999. - Вип. 1. - С. 130-140.

20. Буй Д. Б., Поляков С. А. Композиційна семантика SQL-подібних мов: мультимножини, рядки, впорядковані таблиці // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1999. - Вип. 2. - С. 183-194.

21. Буй Д. Б. Системи рівнянь в індуктивних множинах // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1999. - Вип. 3. - С. 147-171.

22. Брона Ю. Й., Буй Д. Б., Поляков С. А. Композиційна семантика SQL-подібних мов: операції з'єднання // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 1999. - Вип. 4. - С. 100-104.

23. Брона Ю. Й., Буй Д. Б., Загорський С. П., Поляков С. А. Композиційна семантика SQL-подібних мов: агрегатні функції // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 2000. - Вип. 1. - С. 178-192.

24. Брона Ю. Й., Буй Д. Б., Загорський С. П., Поляков С. А. Композиційна семантика SQL-подібних мов: групування, маніпулювання даними, приклади // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 2000. - Вип. 2. - С. 177-185.

25. Буй Д. Б. Cистеми рівнянь в індуктивних множинах: метод Гаусса, інваріантні перетворення, взаємозв`язок між рекурсією та суперпозицією, похідність багатомісної рекурсії // Проблемы программирования. - 2000. - № 1-2. - С. 63-74.

26. Буй Д. Б. Композиційна семантика маніпуляційних дій: збереження денотатів, характеристики, обчислюваність, необхідні умови повноти // Вісник Київ. ун-тету. Сер. фіз.-мат. науки. - 2002. - Вип. 1. - С. 169-188.

Размещено на Allbest.ru