Композиційна семантика ядра SQL-подібних мов - Автореферат

Зростаючі вимоги до сучасних СУБД ініціюють процес швидкого розвитку мови SQL (Structured Query Language), яка є фактичним стандартом для реляційних баз даних. Така модель повинна мати порівняно невелику кількість базових функцій та розвинуті засоби конструювання нових на базі існуючих функцій. Семантична модель дозволить суттєво спростити розробку крос-процесорів нового типу, котрі будуть відображати синтаксичні конструкції вхідного/початкового діалекту мови в функції семантичної моделі, а потім виконувати протилежне перетворення в синтаксичні конструкції вихідного/кінцевого діалекту мови. Реляційна алгебра Кодда, яка претендує на роль семантичного базису SQL, насправді таку роль не може виконувати, хоча б тому, що визначає таблиці даних через множини, а не мультимножини (сукупності з повтореннями), як це має місце в SQL, не підтримує невизначені значення та трьохзначну логіку, не говорячи про те, що структура її операцій не відповідає логічній структурі SQL. Така модель повинна мати порівняно невелику кількість базових функцій та розвинуті засоби конструювання нових функцій на базі існуючих, базуватися на наявних в мові операторах та операціях, а також враховувати вказані вище властивості SQL.Описуються оператори створення таблиць, атомарні типи даних, предикати на атомарних даних та на множинах, оператори трьохзначної логіки, функції на атомарних даних, визначаються агрегатні функції, задається оператор групування. Носій алгебри складається з функцій маніпулювання таблицями, рядками та атомарними даними, сигнатура - з композицій фільтрації, взяття повного образу, агрегації та суперпозиції. Множину всіх рядків (таблиць) схеми R позначимо S(R) (відповідно T()), а множину всіх рядків (таблиць) - S (відповідно T). Але в процесі побудови таких функцій будуть використовуватись функції, що визначені на універсальному домені, рядках, таблицях. семантика рекурсивний денотаційний фільтрація З огляду на зазначену вище характеристичну властивість функцій-семантик агрегатних функцій до них також віднесені функції EXISTS - перевірка множини (таблиці) на непорожність; IN - перевірка належності елемента (рядка) множині (таблиці); ALL - аналог квантору загальності за скінченною множиною (мультимножиною); ANY - аналог квантору існування за скінченною множиною (мультимножиною).Головним результатом дисертації є побудова семантичної моделі (програмної алгебри) композиційного типу, яка задає множину семантичних функцій інваріантних відносно різних діалектів мови SQL. Ця модель розвязує важливу задачу розробки адекватної семантики операторів маніпулювання даними мови SQL та уніфікації роботи з різними діалектами мови, що має істотне значення для теорії та практики побудови сучасних систем керування базами даних. Побудована нова семантична модель таблиць, завдяки чому функції та оператори семантичної моделі мають таку ж семантику для випадку порожніх таблиць, як і в SQL. Розроблена класифікаційна схема для моделей даних на базі поняття колекції (включає множини, мультимножини, послідовності), яка дозволила знайти нові моделі даних, такі як рекурсивні таблиці, багаторівневі таблиці, таблиці на рядках з варіантами.

ОСНОВНИЙ ЗМІСТ

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

Основні результати включають в себе : 1. Побудована нова семантична модель таблиць, завдяки чому функції та оператори семантичної моделі мають таку ж семантику для випадку порожніх таблиць, як і в SQL. Для нової семантики таблиць визначені і математично обґрунтовані композиції фільтрації, взяття повного образу та функції групування, а також операції внутрішнього та зовнішнього зєднання;

2. Для агрегатних функцій побудована нова композиція агрегації та множина базових функцій, семантика роботи яких з NULL значеннями, як показало тестування, співпадає з SQL;

3. Вперше надана операційна та денотаційна семантика рекурсивних запитів в SQL;

4. Доведена еквівалентність операційної та денотаційної семантик рекурсивних запитів;

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

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

З результатів роботи випливають наступні висновки. а) Агрегатні функції та предикати на множинах SQL-подібних мов задаються за однією логічною схемою. б) Ординарні багатомісні функції по-різному розширюються на рядки та стовпчики таблиць (в першому випадку вони зберігають невизначене значення, в другому - ні), при з‘єднанні таблиць невизначені значення інтерпретуються як різні, при групування рядків - як рівні. в) Збагачення композицією рекурсії програмної алгебри, орієнтованої на визначення семантики операторів маніпулювання даними SQL-подібних мов, дає змогу задати семантику CTE-виразів в рекурсивній формі. г) Спираючись на поняття колекцій рядків та звязків між рядками, можна побудувати класифікаційну схему, в яку вкладаються широко відомі моделі даних, такі, як реляційна, ієрархічна, квазіреляційна та мережева. Крім того, ця схема надає опис нових моделей даних, наприклад, рекурсивні таблиці та таблиці з варіантними рядками. д) Для класифікації моделей даних недостатньо використовувати тільки бінарні звязки між колекціями, а необхідно розглядати композиції обєднання бінарних звязків у більш складні структури, які, по суті, є n-арними звязками спеціального вигляду. е) Розширення реляційних даних новими структурами, виявленими в процесі аналізу та класифікації моделей даних, здатне значно підняти рівень абстракції даних, які задаються в сучасних базах даних.

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

2. Поляков С.А. Алгебра табличних функцій / С.А. Поляков // Вісник Київського університету. Сер.: фіз.-мат. науки. - 1996. - Вип. 2. - С. 150-155.

3. Поляков С.А. Композиційна семантика SQL-подібних мов / С.А. Поляков // Вісник Київського університету. Сер.: фіз.-мат. науки. - 1997. - Вип. 3. - С. 205-211.

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

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

6. Поляков С.А. Композиційні структури SQL-подібних мов: фільтрація та повний образ / Д.Б. Буй, С.А. Поляков // Вісник Львівського університету. Сер.: механіко-математична. - 1998. - Вип. 50. - "Задачі та методи прикладної математики". - С. 24-26.

7. Поляков С.А. Огляд стандартів мови SQL / С.А. Поляков // Вісник Київського університету. Сер.: фіз.-мат. науки. - 2008. - Вип. 1. - С. 132-137.

8. Поляков С.А. Композиційна семантика рекурсивних запитів в SQL-подібних мовах / Д.Б. Буй, С.А. Поляков // Вісник Київського університету. Сер. фіз.-мат. науки. - 2010. - Вип. 1. - С. 45-50.

9. Поляков С.А. Композиційна семантика рекурсивних виразів та їхніх узагальнень в SQL-подібних мовах / С.А. Поляков, Д.Б. Буй // Наукові записки НАУКМА. Сер.: Компютерні науки. - 2010. - Том 112. - С. 21-25.

10. Поляков С.А. Рекурсивні запити в SQL-подібних мовах: приклади, змістовна і формальна семантика / С.А. Поляков, Д.Б. Буй // Проблеми програмування. - 2010. - №2-3 (Спеціальний випуск). - С. 434-439.

11. Поляков С.А. Три замечания о трехзначной логике Клини / Д.Б. Буй, С.А. Поляков, Е.В. Шишацкая // The Fourth International Conference "Theoretical and Applied Aspects of Program Systems Development" (TAAPSD’2007). Abstracts (Ukraine, Berdynsk, 4-9 September 2007). - Київ: Пульсари, 2007. - С. 47-51.

12. Поляков С.А. Типи даних в стандарті SQL: 2003 / С.А. Поляков, Д.Б. Буй // International Conference "Theoretical and Applied Aspects of Program Systems Development (TAAPSD’2008)". Abstracts (Ukraine, Chernihiv, Kyiv, 22-26 September 2008). Volume 2. - Київ: Пульсари, 2008. - С. 53-57.

13. Поляков С.А. Побудова рекурсивних запитів в SQL / С.А. Поляков // International Conference "Theoretical and Applied Aspects of Program Systems Development (TAAPSD’2009)". Abstracts (Ukraine, Chernihiv, Kyiv, September 2009). Volume 2. - Київ: Пульсари, 2009. - С. 204-209.

14. Поляков С.А. Ієрархічні дані в SQL / С.А. Поляков // Современные направления теоретических и прикладных исследований: международная конференция SWORD, 16-27 марта 2009 г., Одесса: Черноморье. - 2009. - Т.2. - С. 52-59.

15. Polyakov S. Recursive queries in SQL and their generalization - systems of recursive queries / S. Polyakov, D. Buy //Proceeding of CSE 2010 International Scientific Conference on Computer Science and Engineering, September 20-22, 2010, Kosice - Stara Lubova, Slovakia, P. 252-257.