60 Years of Databases

The article provides an overview of research and development of databases since their appearance in the 60s of the last century to the present time. The following stages are distinguished: the emergence formation and rapid development, the era of relational databases, extended relational databases,...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2021
Автор:	Reznichenko, V.A.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2021
Теми:	hierarchical network relational navigational temporal spatial spatio-temporal spatio-network moving objects deductive active object-oriented object-relational distributed parallel arrays statistical multidimensional database machines UDC 004.94
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/470
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-470
record_format	ojs
resource_txt_mv	ppisoftskievua/10/80823376d6bb30a2f49dd44db88ceb10.pdf
spelling	pp_isofts_kiev_ua-article-4702021-12-03T16:47:40Z 60 Years of Databases 60 років базам даних Reznichenko, V.A. hierarchical; network; relational; navigational; temporal; spatial; spatio-temporal; spatio-network; moving objects; deductive; active; object-oriented; object-relational; distributed; parallel; arrays; statistical; multidimensional; database machines UDC 004.94 ієрархічна; мережева; реляційна; навігаційна; темпоральна; просторова; просторово-темпоральна; просторово-мережева; об'єктів; що переміщуються; дедуктивна; активна; об'єктно-орієнтована; об'єктно-реляційна; розподілена; паралельна; масивів; статистична УДК 004.94 The article provides an overview of research and development of databases since their appearance in the 60s of the last century to the present time. The following stages are distinguished: the emergence formation and rapid development, the era of relational databases, extended relational databases, post-relational databases and big data. At the stage of formation, the systems IDS, IMS, Total and Adabas are described. At the stage of rapid development, issues of ANSI/X3/SPARC database architecture, CODASYL proposals, concepts and languages of conceptual modeling are highlighted. At the stage of the era of relational databases, the results of E. Codd's scientific activities, the theory of dependencies and normal forms, query languages, experimental research and development, optimization and standardization, and transaction management are revealed. The extended relational databases phase is devoted to describing temporal, spatial, deductive, active, object, distributed and statistical databases, array databases, and database machines and data warehouses. At the next stage, the problems of post-relational databases are disclosed, namely, NOSQL-, NewSQL- and ontological databases. The sixth stage is devoted to the disclosure of the causes of occurrence, characteristic properties, classification, principles of work, methods and technologies of big data. Finally, the last section provides a brief overview of database research and development in the Soviet Union.Prombles in programming 2021; 3: 40-71 Наводиться огляд досліджень і розробок баз даних з моменту їх виникнення в 60-х роках минулого століття і по сьогодні. Виділяються наступні етапи: виникнення і становлення, бурхливий розвиток, епоха реляційних баз даних, розширені реляційні бази даних, пост-реляційні бази даних і великі дані. На етапі становлення описуються системи IDS, IMS, Total і Adabas. На етапі бурхливого розвитку висвітлені питання архітектури баз даних ANSI/X3/SPARC, пропозицій КОДАСИЛ, концепції і мов концептуального моделювання. На етапі епохи реляційних баз даних наводяться результати наукової діяльності Е. Кодда, теорія залежностей і нормальних форм, мови запитів, експериментальні дослідження і розробки, оптимізація та стандар¬тизація, управління транзакціями. Етап розширених реляційних баз даних присвячений опису темпоральних, просторових, дедуктивних, активних, об'єктних, розподілених та статистичних баз даних, баз даних масивів, а також машин баз даних і сховищ даних. На наступному етапі розкрита проблематика постреляційних баз даних, а саме, NOSQL-, NewSQL- і онтологічних баз даних. Шостий етап присвячено розкриттю причин виникнення, характерних властивостей, класифікації, принципів роботи, методів і технологій великих даних. Нарешті, в останньому розділі подається короткий огляд досліджень і розробок по базах даних в Радянському Союзі.Prombles in programming 2021; 3: 40-71 Інститут програмних систем НАН України 2021-10-12 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/470 10.15407/pp2021.03.040 PROBLEMS IN PROGRAMMING; No 3 (2021); 40-71 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2021); 40-71 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2021); 40-71 1727-4907 10.15407/pp2021.03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/470/474 Copyright (c) 2021 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2021-12-03T16:47:40Z
collection	OJS
language	Ukrainian
topic	hierarchical network relational navigational temporal spatial spatio-temporal spatio-network moving objects deductive active object-oriented object-relational distributed parallel arrays statistical multidimensional database machines UDC 004.94
spellingShingle	hierarchical network relational navigational temporal spatial spatio-temporal spatio-network moving objects deductive active object-oriented object-relational distributed parallel arrays statistical multidimensional database machines UDC 004.94 Reznichenko, V.A. 60 Years of Databases
topic_facet	hierarchical network relational navigational temporal spatial spatio-temporal spatio-network moving objects deductive active object-oriented object-relational distributed parallel arrays statistical multidimensional database machines UDC 004.94 ієрархічна мережева реляційна навігаційна темпоральна просторова просторово-темпоральна просторово-мережева об'єктів що переміщуються дедуктивна активна об'єктно-орієнтована об'єктно-реляційна розподілена паралельна масивів статистична УДК 004.94
format	Article
author	Reznichenko, V.A.
author_facet	Reznichenko, V.A.
author_sort	Reznichenko, V.A.
title	60 Years of Databases
title_short	60 Years of Databases
title_full	60 Years of Databases
title_fullStr	60 Years of Databases
title_full_unstemmed	60 Years of Databases
title_sort	60 years of databases
title_alt	60 років базам даних
description	The article provides an overview of research and development of databases since their appearance in the 60s of the last century to the present time. The following stages are distinguished: the emergence formation and rapid development, the era of relational databases, extended relational databases, post-relational databases and big data. At the stage of formation, the systems IDS, IMS, Total and Adabas are described. At the stage of rapid development, issues of ANSI/X3/SPARC database architecture, CODASYL proposals, concepts and languages of conceptual modeling are highlighted. At the stage of the era of relational databases, the results of E. Codd's scientific activities, the theory of dependencies and normal forms, query languages, experimental research and development, optimization and standardization, and transaction management are revealed. The extended relational databases phase is devoted to describing temporal, spatial, deductive, active, object, distributed and statistical databases, array databases, and database machines and data warehouses. At the next stage, the problems of post-relational databases are disclosed, namely, NOSQL-, NewSQL- and ontological databases. The sixth stage is devoted to the disclosure of the causes of occurrence, characteristic properties, classification, principles of work, methods and technologies of big data. Finally, the last section provides a brief overview of database research and development in the Soviet Union.Prombles in programming 2021; 3: 40-71
publisher	Інститут програмних систем НАН України
publishDate	2021
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/470
work_keys_str_mv	AT reznichenkova 60yearsofdatabases AT reznichenkova 60rokívbazamdanih
first_indexed	2025-07-17T10:01:19Z
last_indexed	2025-07-17T10:01:19Z
_version_	1838410289906712576
fulltext	40 Моделі та засоби систем баз даних і знань Етап 1. Становлення баз даних (1960 – 1970) 60-і роки – це період усвідомлен- ня необхідності відокремлення даних від програм, кристалізації вимог до такої незалежної сукупності даних. Відтак, це період зародження й успішного станов- лення технологій баз даних, формування їхніх методологічних основ, становлення концепції моделі даних і появи перших двох класичних моделей – ієрархічної і мереже- вої, народження індустрії програмного забезпечення систем баз даних, а також – організаційного формування спільноти спеціалістів цієї галузі. На початку 60-х років комп’ютери почали впроваджуватися на виробництві. Звісно, це здійснювали великі компанії, здатні придбати таке дороге обладнання. Комп’ютери почали використовуватись для автоматизації виробничих процесів, включно з обліком отримуваної сировини і деталей, виробленої продукції, персонала, тощо. Комп’ютери ставали інструментом збереження і обробки великих обсягів да- них. До того ж стало очевидним, що техно- логія створення автоматизованих систем, за якої існував тісний звязок між даними і програмами, які їх використовують, є не- життєздатною. Адже будь – які незначні зміни в структурі баз даних призводили до необхідності переписувати програми. З по- ступовим ускладненням структури даних і зростанням їхнього об’єму, збільшенням кількості користувачів, а також – інтенсив- ності використання даних, подібний підхід призводив до краху систем. Це викликало усвідомлення того, що необхідно розірвати такий зв’язок і уможливити незалежне існування даних і програм, що й стало основою появи в ін- форматицінапрямку, який згодом отримав назву «бази даних». Аби зрозуміти, в яких умовах за- роджувалися бази даних, зазначимо, що це був час комп’ютерів фактично без опе- раційної системи, з 64 КБ оперативної пам’яті. Носіями введення даних були перфокарти і перфострічки, а відпові- дальними за зовнішню память були пе- реважно магнітні стрічки. І лише деякі компанії могли дозволити собі магнітні диски з об’ємом у 5 МБ і розмірами, що УДК 004.94 http://doi.org/10.15407/pp2021.03.040 В.А. Резніченко 60 РОКІВ БАЗАМ ДАНИХ (частина перша) Наводиться огляд досліджень і розробок баз даних з моменту їх виникнення в 60-х роках минулого століття і по теперішній час. Виділяються наступні етапи: виникнення і становлення, бурхливий роз- виток, епоха реляційних баз даних, розширені реляційні бази даних, постреляційні бази даних і великі дані. На етапі становлення описуються системи IDS, IMS, Total і Adabas. На етапі бурхливого розвитку висвітлені питання архітектури баз даних ANSI/X3/SPARC, пропозицій КОДАСИЛ, концепції і мов концептуального моделювання. На етапі епохи реляційних баз даних розкриваються результати науко- вої діяльності Е. Кодда, теорія залежностей і нормальних форм, мови запитів, експериментальні дослі- дження і розробки, оптимізація та стандар¬тизація, управління транзакціями. Етап розширених реля- ційних баз даних присвячений опису темпоральних, просторових, дедуктивних, активних, об’єктних, розподілених та статистичних баз даних, баз даних масивів, машин баз даних і сховищ даних. На наступному етапі розкрита проблематика постреляційних баз даних, а саме, NOSQL-, NewSQL- і он- тологічних баз даних. Шостий етап присвячений розкриттю причин виникнення, характерних власти- востей, класифікації, принципів роботи, методів і технологій великих даних. Нарешті, в останньому розділі дається короткий огляд досліджень і розробок по базах даних в Радянському Союзі. Ключові слова. Типи баз даних: ієрархічна, мережева, реляційна, навігаційна, темпоральна, просторо- ва, просторово-темпоральна, просторово-мережева, об’єктів, що переміщуються, дедуктивна, активна, об’єктно-орієнтована, об’єктно-реляційна, розподілена, паралельна, масивів, статистична, багатови- мірна, машина баз даних, сховища даних, NoSQL, ключ-значення, стовпчикова, документно-орієнтова- на, графова, мультимодельна, хмарна, наукова, багатозначна, XML, NewSQL, онтологічна, великі дані. © В.А.Резніченко, 2021 ISSN 1727-4907. Проблеми програмування. 2021. № 3 41 Моделі та засоби систем баз даних і знань перевищували тристулкову шафу разом із антресолями. Зрештою спілкування люди- ни з комп’ютером відбувалося через пульт управління або, в кращому випадку, через друкарську машинку. Завантаження жорсткого диску на 5МБ компанії ІВМ Системи IDS. 1960-го року невели- ка команда із General Electric, яка автома- тизувала бізнес-процеси, розпочала проєк- тування системи Integrated Data Store (IDS) – інтегроване сховище даних під керівни- цтвом Чарльза Бахмана (Charles William Bachman). Наприкінці 1962 року прототип цієї системи був завершений, а на почат- ку 1964 року випущена перша промисло- ва версія IDS [14-16]. Її поява знаменувала еру баз даних і зірковий шлях Бахмана. Чарльз Бахман В IDS було вперше втілено те, що нині вважається основними функціями системи управління базами даних. IDS ви- конувала функцію посередника між при- кладними програмами і файлами, в яких зберігалися дані. Програми не могли на- пряму маніпулювати даними. Натомість вони мали звертатися до системи IDS, аби та виконувала відповідні дії від їх імені. Як і сучасні системи управління базами даних, IDS дозволяла створювати, збе- рігати і маніпулювати метаданими, хоча робилося це занадто примітивно. В IDS у найпростішому вигляді були реалізовані функціональні можливості, котрі згодом отримали назву «незалежності даних від програм». Бахман розробив у IDS інно- ваційну на той час систему «Диспетчер проблем» (Problem Controller), що стала прообразом системи управління транзак- ціями. В IDS також була спроєктована і реалізована система резервного копію- вання і відтворення даних на магнітних стрічках. Зрештою, була передбачена функція заборони доступу до певних час- тин бази даних конкретним користувачам. IDS стала прообразом системи управління базами даних, що підтримувала мережеву модель даних. Система IDS розвивалась, удосконалювалась і використовувалась упродовж десятків років. І нині IDS вико- ристовується в деяких компаніях і демон- струє відмінні результати продуктивності на терабайтних масивах даних. 1973 року Бахман був нагородже- ний найпрестижнішою в галузі інформа- тики премією Алана Тьюрінга за видат- ний внесок у технологію баз даних. Він був першим лауреатом премії Тьюрінга без ступеню доктора філософії, першим із досвідом роботи в галузі техніки, а не на- уки, й першим, чия кар’єра була повністю пов’язана з промисловістю, а не з наукою або науковим середовищем. Він також перший, хто отримав цю премію за роботу з базами даних. Система IMS. 1965 року компанія IBM отримала замовлення на створення автоматизованої системи для обліку ве- личезної кількості виробів, деталей і ма- теріалів, що мали використовуватися під час виконання космічної програми НАСА 42 Моделі та засоби систем баз даних і знань «Аполон» - польоту людини на Місяць. Ця система попередньо отримала назву Information Control System – IMS (сис- тема управління інформацією). Відпо- відно до [1] в основу IMS було покла- дено модель даних, розроблену в серед- ині 60-х років компанією North American Rockwell. 1968 року IMS була надана за- мовнику, а вже 1969 року стала доступ- ною у сфері інформаційних технологій [17 - 19]. Відтоді й практично по сьогодні компанія IBM вдосконалює IMS, перено- сить на різні платформи і в різні опера- ційні системи, розширює функціональ- ні можливості. Це, власне, була перша успішна спроба створення промислового варіанту СУБД, хоча на той час так не називалася. Головним архітектором IMS був Верн Уоттс (Vern Watts). Він очолю- вав цю роботу з моменту її проєктування аж до своєї смерті 2009 року. Верн Уоттс IMS підтримує ієрархічну мо- дель даних. Вона складається зі схеми й екземплярів. На схемному рівні осно- вним будівельним блоком є сегмент, який складається із сукупності полів. Сегмен- ти зв’язуються направленими бінарни- ми зв’язками. Сегмент, із якого виходить зв’язок називається батьківським, а який приєднується – дочірнім. Кожен сегмент може мати не більше одного батьківського сегменту й велику кількість дочірніх. Сег- мент без батька називається кореневим, а без дочірніх сегментів – листям. На рівні екземплярів зв’язок між сегментами озна- чає, що один екземпляр батьківського сег- менту зв’язується з багатьма екземплярами дочірнього сегменту. Екземпляр ієрархіч- ної структури містить один екземпляр ко- реневого сегменту. Отже, ієрархічна мо- дель природно представляє зв’язки «один до багатьох». Слід зазначити, що жорстка формальна специфікація ієрархічної моде- лі даних відсутня, і вона, зазвичай висвіт- люється так, як це було визначено в IMS. Система Total. 1968 року Томас Ніс (Tomas Nies), Клод Богардус (Cloud Bogardus) і Том Річлі (Tom Richley) за- снували компанію Cincom Systems, а вже 1969-го було випущено першу версію СУБД Total [20]. Томас Ніс На думку багатьох користувачів і спеціалістів, система Total була серйозним конкурентом IMS на комп’ютерах IBM. На відміну від IMS і більшості інших СУБД того часу Total не обмежувалась одним ти- пом комп’ютерів. Порівняно з IMS вправля- тися з Total було доволі легко і ефективно. Базовою структурою даних Total є дворівнева ієрархія, що містить один за- пис – власника (master) і велику кількість записів – членів (details). Ці типи записів можуть бути пов′язані так, щоби створю- вати складні структури даних. Ця структу- ра нагадувала мережеву структуру перших версій IDS. У Total підтримувалося узгодження із Cobol, Fortran, PL/1 і Assembler. Мова 43 Моделі та засоби систем баз даних і знань маніпулювання нагадувала специфікацію Codasyl. Було реалізовано механізм захис- ту бази даних, який включав динамічну ре- єстрацію, періодичне резервне копіювання (дамп) і рестарт, запобігання одночасному оновленню даних. Підтримувався режим одночасної роботи багатьох прикладних програм. Було також реалізовано механізм незалежності на рівні окремих елементів даних. Для кожної програми можна було виділити доступну підчисельність бази даних з допомогою механізму, подібному підсхемам. На початок 70-х років Total мала най- більшу кількість користувачів серед усіх діючих тоді СУБД. Вважається, що на по- чатковому етапі компанія Cincom Systems зробила суттєвий внесок у розвиток СУБД. Система Adabas. Adabas ( database system – адаптивна система баз даних) – система управління базами даних компанії Software AG, Німеччина. Уперше випущена для мейнфрей- мів IBM 1971 року. Початкова модель да- них – на базі інвертованого індексу. Підхід Adabas відмінний від мережевої моделі даних, однак забезпечує можливість під- тримки повної мережевої структури за ра- хунок неявних відносин. На момент ство- рення мова маніпулювання Adabas являла собою розширення мов Cobol і PL/1. У 1980-і роки доповнена елементами реля- ційної моделі. На злеті популярності реля- ційних СУБД в середині 80-х років, вона була однією з найбільш затребуваних сис- тем управління базами даних. IDS, IMS, Total, Adabas належать до складу так зва- них навігаційних баз даних. Цей термін був введений Чарльзом Бахманом у його статті [21], присвяченій отриманню премії Тью- ринга. Суть цього классу полягає в тому, що записи даних можуть зв′язуватись між собою різними посиланнями, тим самим створюючи складну структуру даних, а мова маніпулювання дозволяє здійснювати довільну навігацію за цими посиланнями для отримання доступу до потрібних за- писів. Ідея навігаційних систем булла по- роджена появою магнітних дисків, які, на відміну від магнітних стрічок, перфострі- чок і перфокарт із послідовним доступом, надавали прямий доступ. На завершення цього розділу зазна- чимо, що сам термін «база даних» (database) з′явився на початку 60-х років. На думку Вільяма Олле (T. William Olle) [1] цей тер- мін уперше було введено у вжиток на сим- позіумах, організованих компанією System Development Corporation (SDC) у 1963 і 1965 роках, хоча спочатку сприймався у доволі вузькому сенсі. В широкий ужиток термін увійшов лише на початку 1970-х років [22]. Етап 2. Бурхливий розвиток (1970 – 1980) 70-і роки – це роки бурхливого роз- витку баз даних , створення основ тех- нології баз даних. Вони ознаменувалися передовсім дослідженнями робочої гру- пи CODASYL по базах даних (CODASYL DBTG), яка специфікувала мережеву модель, мови визначення і маніпулюван- ня даними.В цей період було визначено і вивчено значну кількість моделей даних, включно із семантичними. 1876 року Пе- тер Чен визначив ER – модель. Була спе- цифікована трирівнева архітектура баз даних ANSI/X3/SPARC, яка стала класич- ною, здійснені дослідження щодо кон- цептуального моделювання предметних галузей.Закладені основи індустріального виробництва СУБД та іншого програмно- го забезпечення баз даних. Зрештою, були реалізовані численні промислові СУБД, котрі виявилися затребуваними наступні кілька десятків років. 1973 року, як уже згадувалося вище, Чарльз Вільям Бахман був нагороджений найпрестижнішою в галузі інформатики премією Тьюрінга за видатний внесок у технологію баз даних. До кінця 60-х років наукове спів- товариство дійшло висновку, що системи управління базами даних (СУБД) стали центральною ланкою в автоматизованих інформаційних системах. Однак тоді ще не було повного усвідомлення того, що саме являє собою СУБД, які вимоги вони му- сять задовольняти, які моделі даних мають підтримувати, яким архітектурним рішен- ням мають відповідати. Але вже на початку 70-х років з′явилися перші звіти й статті, де робилися припу- щення із конкретних систем [23], а також формулювалися вимоги до СУБД [24,25]. 44 Моделі та засоби систем баз даних і знань Інфологічні й даталогічні мо- делі. Уже у 60-і роки вчені, котрі пра- цювали в галузі інформаційних систем, зрозуміли, що в комп′ютерній системі мають бути представлені не лише дані, а і їхня семантика. В середині 60-х ро- ків шведський вчений Борже Лангефорс (Borje Langefors) ввів поняття інфологіч- ної і дата логічної моделей (infological and datalogical models), які він розвивав упродовж 15 років [26 - 28]. Борже Лангефорс Даталогічні моделі – це сукупність структурованих і взаємопов’язаних даних і способи оперування ними. Інфологічні мо- делі – це моделі представлення інформації (тобто – семантики) про дані. Ці терміни використовуються й по сьогодні, хоча з ча- сом з′явився термін «семантична модель» як модель предметної галузі, призначена для представлення семантики предметної галузі на найвищому рівні абстракції. 1999 року Б. Лангефорс отримав престижну премію LEO за видатні досягнення в галузі інформаційних систем Міжнародної асоці- ації з інформаційних систем. А 2010 року шведська академія з інформаційних систем заснувала премію Б.Лангефорса за кращу докторську дисертацію Швеції в галузі ін- форматики й інформаційних систем. Ідеї Лангефорса згодом були роз- винуті й адаптовані до технологій баз да- них шведським ученим Б. Сундгреном (Bo Sundgren) [29]. Бо Сундгрен Архітектура баз даних ANSI/X3/ SPARC. Із появою СУБД виникло нове по- няття – схема даних (опис даних), яке від- сутнє у файловій організації даних. Спе- цифікація цієї схеми і маніпулювання да- ними виконуються вже мовними засобами СУБД – МОД (мова опису даних) і ММД (мова маніпулювання даними). Взаємодія СУБД із прикладною програмою здійсню- ється за допомогою розробки спеціального інтерфейсного модулю, в якому специфі- куються об’єкти бази даних, потрібні цій програмі, а також необхідні операції над цими об’єктами. Зокрема, як це робиться в СУБД Adabas. Прикладна програма звер- тається до цього модулю через відповідну точку входу і передає йому певні параме- три, що уточнюють запит. У відповідь про- грама отримує потрібні дані. Це так звана однорівнева архітектура. Цей єдиний рі- вень складає схема бази даних. Наступним кроком до вдосконалення було введення дворівневої архітектури. Суть її полягає в тому, що крім рівня схеми вводиться рівень підсхеми - фрагмента загальної схеми, який створюється для кожного додатку і описує дані, потрібні цьому додаткові. Дворівнева архітектура була прийнята в IMS. І нарешті в ANSI була визначена трирівнева архітек- тура баз даних, що стала класичною на ба- гато десятиріч і про яку мова піде далі. У листопаді 1972 року підкомітет SPARC (Standard Planning and Requirements 45 Моделі та засоби систем баз даних і знань Committee) комітету ХЗ (Committee on Computers and Information Processing) Американського Національного Інституту Стандартів (ANSI) створив робочу групу ANSI/X3/SPARC DBMS для дослідження можливостей і розробки рекомендацій по стандартизації СУБД. Спочатку групу очо- лив Томас Стіл (Tomas B. Steel, Jr), а згодом Діонісіос Цикритзис (Dionysios Tsichritzis). Діонісіос Цикритзис Початковим завданням групи було дослідження питання, чи варто взагалі ви- рішувати проблему стандартизації СУБД. Якщо так, то що саме має бути стандарти- зоване. В результаті група дійшла висно- вку, що стандартизації можуть бути підда- ні лише інтерфейсні складові СУБД [30]. У зв’язку з цим було поставлено за- вдання визначення множини компонентів, з яких має складатися СУБД, інтерфей- си, між якими могли б стати об’єктами стандартизації.В основу виявлення цих компонентів були покладені наступні кон- цептуальні положення. По-перше, існує реальний світ, інформаційна модель якого має знайти своє відображення в базі даних. По-друге, враховуючи конкретні потреби, в свідомості людей відображаються їхні осо- бисті уявлення про те, яким є реальний світ. Зрештою цей реальний світ матеріалізуєть- ся у вигляді сукупності символів, у тексто- вому або електронному вигляді. Саме ця триєдність знайшла відображення в запро- понованій групою зкомпонентної структу- ри баз даних, що була названа трирівневою архітектурою баз даних ANSI-SPARC, і яка отримала загальне визнання серед розроб- ників СУБД. Ця архітектура є актуальною й досі. Вона передбачає наявність концеп- туального, зовнішнього і внутрішнього рів- нів. Концептуальний рівень призначений для опису концептуальної інформаційної моделі предметної галузі (ПГ). Зовнішній рівень визначає представлену користувачем БД. Це та частина БД, яка відповідає потре- бам конкретного користувача. Причому ця частина подається в зручному для корис- тувача вигляді. Внутрішній рівень призна- чений для опису фізичного зберігання БД. Між цими рівнями існують відображення: концептуальний – зовнішній і концептуаль- но – внутрішній. Ця трирівнева архітектура забезпечує необхідні умови для досягнення логічної і фізичної незалежності даних від програм. У свою чергу, дієвість механізмів опису відображень визначає ступінь достат- ності досягнення вищезгаданих двох видів незалежності. Результати діяльності цієї ро- бочої групи були надані у звітах. 1977 року Томас Стіл отримав «Нагороду за видатні заслуги» (Distinguished Service Award) асо- ціації АСМ. Пропозиції КОДАСИЛ. Вне- сок CODASYL у технологію баз даних пов’язують із створенням мережевої моделі даних. 1967 року в КОДАСИЛ (CODASYL - Conference on Data Systems Languages) була створена спеціальна робоча група з питань баз даних (CODASYL Data Base Task Group — DBTG). Одним із першочергових за- вдань робочої групи було створення засобів управління базами даних для мови Кобол. Згодом ця задача була суттєво розширена і сформульована як розробка концепції, ар- хітектури і мовних специфікацій баз даних загального призначення. 1971 року, усві- домлюючи важливість досліджень зі спеці- фікації мовних засобів баз даних, було ство- рено Комітет КОДАСИЛ із мови опису да- них (CODASYL Data Description Language Committee). В результаті діяльності цих двох груп були опубліковані звіти [23, 33, 34], які викликали значний резонанс, були заслужено визнані фахівцями з баз даних і надовго стали зразком специфікації баз даних. У цих звітах, виходячи зі спільних 46 Моделі та засоби систем баз даних і знань позицій і у тісному взаємозв’язку, вперше були строго специфіковані: - мережева модель даних, ідеї якої були закладені Ч. Бахманом у системі IDS, що і отримала назву моделі даних КОДА- СИЛ (CODASYL Data Model); - трирівнева архітектура баз да- них, що згодом була прийнята і розвинута в ANSI/X3/SPARC DBMS; - мови опису даних (МОД) на всіх трьох рівнях (мова схеми, мова підсхеми, мова схеми зберігання); - включені в МОД такі функції, як функція адміністрування, перевірки досто- вірності, управління доступом, налашту- вання, розподілу ресурсів, захисту даних, цілісності даних; - відображення між схемою і під- схемою, а також схемою і схемою збере- ження; - мова маніпулювання даними, призначена для навігації мережевною структурою з метою специфікації необхід- ного запису для його оновлення, видален- ня, або ж вставки нового запису. За результатамироботи комітетів КОДАСИЛ були опубліковані численні ма- теріали, серед яких відмітимо монографію Вільяма Олле (T. William Olle) [1]. Під- креслимо, що пропозиції КОДАСИЛ були специфіковані для систем із включаючою мовою, тобто вони припускали, що робота з базою даних здійснювалась через мову програмування. Це повністю відповідало прийнятій тоді технології обробки даних і тому сприяло ефективній реалізації в існу- ючому вичислювальному середовищі. Вільям Олле Мережеві СУБД. Відповідно до специфікацій КОДАСИЛ була реалізована низка СУБД, серед яких: IDMS (Integrated Database Management System) компанії Cullinane Database Systems, що стала осно- вною мережевою СУБД для мейнфреймів і найпопулярнішою в 70 – 80 –і роки мину- лого століття DMS 1100 (UNIVAC), IDS/II (Honeywell), DBMS 10/20 (DEC). Концептуальне моделювання. У листопаді 1977 року комітет ISO з мов програмування прийняв рішення про ство- рення робочої групи з питань дослідження різних аспектів використання концепту- альних схем у системах управління базами даних з метою забезпечення основи для стандартизації в даній галузі. Спочатку цю групу очолив Т.Б.Стіл - молодший, а зго- дом Д.А.Жардін (D.A.Jardine). Результатом діяльності цієї групи став звіт, випущений 1982 року під редакцією Дж. Грийтусена (Joost J. Van Griethyusen). Дж. Грийтусен У звіті описуються роль і зміст кон- цептуальної схеми, а також визначається зв′язок концептуальної схеми з інформа- ційним моделюванням і семантикою да- них. Підкреслюється важливість точного визначення як статистичних, так і динаміч- них правил у концептуальній схемі: - це спільна основа однозначного розуміння суті предметної галузі (ПГ) всі- ма зацікавленими сторонами; - вона включає лише концепту- ально релевантні аспекти ПГ; - це спосіб визначення допусти- мої еволюції інформаційної бази даних і 47 Моделі та засоби систем баз даних і знань дозволеного маніпулювання інформацією про ПГ; - це базис для інтерпретації зо- внішніх і внутрішніх схем; - це основа відображення зовніш- ніх схем у внутрішню і навпаки. Моделі даних. Відповідно [13] тер- мін «модель даних» почав використовува- тися на початку 70-х років після публіка- ції фундаментальної роботи Едгара Кодда (E. Codd) [59]. Однак ще в другій поло- вині 60-х років почали з′являтися пер- ші моделі даних. У результаті розвитку технології баз даних було запропоновано чимало засобів і методологій концепту- ального моделювання. Зокрем, серед них наступні моделі: модель «Об′єктів – ро- лей» (OPM – Object – Role Model) Екхарда Д.Фолкенберга (Folkenberg, Eckhard D.) [36, 37], яка була розвинута іншими вчени- ми (С. Нейссен, Р.Меерсман, Д.Вермейр, Т.Халпін (Sjir Nijssen, Ro bert Meersman, Dirk Ver meir, Terry Halpin). ORM перед- бачає представлення інформаційної мо- делі у вигляді об′єктів (сутностей), котрі відіграють ту чи іншу роль (представлені у вигляді зв′язків між об′єктами). На від- міну від об′єктно-орієнтованого підходу і підходу сутність-зв′язок ORM не передба- чає існування атрибутів, вони подаються у вигляді ролей фактів, які разом із прави- лами моделюються у вигляді природних пропозицій, легких для розуміння і пере- вірки користувачами. Екхард Д.Фолкенберг Модель даних, заснована на бі- нарних зв′язках. Біля витоків походжен- ня моделі бінарних зв′язків (BR - Binary Relations) були праці таких авторів, як Абріаль [38] (семантична бінарна модель), Браччі [39], Дурхольц [40]. Суть цього підходу до моделювання в тому, що будь- який «елемент» інформації представля- ється з допомогою екземплярів бінарних асоціацій, тобто висловлювань, до скла- ду яких входять тільки два терми. Зокре- ма, М.Сенко в межах проекту DIAM (Data Independence Access Method) визначив бі- нарну мережеву модель, розробив на базі цієї моделі мову FORAL і дослідив мож- ливості користувальницького інтерфейсу, який на ній базується [41, 42, 43]. Семантичні моделі. Відзначимо роботи Дж. Сміта і Д. Сміта по моделях абстракції, агрегації і узагальнення да- них [44, 45], а також семантичну модель даних SDM Хамера і МакЛеода [46]. У статті [47] наводиться перелік близько 20 семантичних моделей баз даних. Резуль- татом розвитку моделей даних до початку 80-х років наведені в широко відомій мо- нографії Д.Цикритзиса і Фреда Лоховскі (F.Lochovsky) [2]. Фред Лоховскі ER – модель. Водночас, найбільшу популярність заслужено здобув підхід сут- ність – атрибут - зв′язок, названий як під- хід сутність - зв′язок (ER – підхід). Свій по- чаток він бере від діаграм структур даних Бахмана [48], а також моделі Інглеса [49]. 48 Моделі та засоби систем баз даних і знань Вперше найширше цю модель опи- сав П.П.Чен (Peter Pin- Shen Chen) [50]. Петер Чен ER – модель даних стала загально- визнаною в світі і є основою багатьох ме- тодик системного аналізу, концептуально- го моделювання й проєктування баз даних. Вона базується на простій ідеї, що струк- турна складова концептуальної моделі предметної галузі може бути представлена у вигляді сутностей, атрибутів і зв′язків. Сутність – це будь-який реальний або аб- страктний об′єкт довільної природи, який представляє самостійний інтерес. Атри- бут – це властивість сутності, що сприяє якісному або кількісному її опису, іденти- фікації, класифікації або відображенню її стану. Нарешті зв′язок – це певна асоціація між різними сутностями (класами сутнос- тей), що становить певний інтерес. Після публікації статті Чена з′явилося чимало статей, присвячених до- слідженню різних аспектів ER - моделю- вання предметних галузей. Наприклад, в загальному випадку припускається існу- вання n – арних зв′язків, а Річард Баркер (Barker Richard) запропонував ER модель тільки з бінарними зв′язками [51], яка має певні переваги. У зв′язку з широким використан- ням ER- моделі [3] було запропоновано багато різних її розширень і узагальнень [52 - 55], які зрештою привели до визна- чення ієрархічної ER- моделі (ER- моделі вищого порядку) [55]. У статті [56] ER- модель розширена елементами семанти- зації даних. Також була запропонована темпорально-розширена ER- модель [57], яка дає можливість включати темпораль- ну інформацію в концептуальну інформа- ційну модель і представляти її в реляцій- ній моделі. Для підтримки темпоральних запитів мова SQL була розширена можли- востями визначення, пошуку й управління історичними відносинами. Із часом було запроваджено ще кілька темпоральних er – моделей, огляд яких наведено в [58]. Зрештою, існує просторова ER - модель (див.: «Просторові бази даних»). Етап 3. Епоха реляційних баз даних (1970 - 1990+) На початку 80-х років з′явилися пер- ші промислові реляційні СУБД, які до кінця 80-х стрімко завоювали ринок і стали па- нівними практично на всіх поширених апа- ратно-програмних платформах і не втра- тили свою перевагу й по сьогодні. Попри це, основи реляційної моделі даних і реляційних СУБД були закладені в попередньому де- сятиріччі, родоначальником їх був Едгар Франк Кодд. Він визначив реляційну струк- туру даних, алгебру і обчислення, заклав основи теорії залежностей і нормальних форм, сформулював вимоги реляційності баз даних. Ці та інші дослідження кінець кінцем привели до створення теорії реля- ційних баз даних. Бази даних перетворилися з описової науки у формальну. 1981 року Едгара Франка Кодда було нагороджено премією Тьюрінга за фундаментальний і тривалий внесок в теорію і практику систем управління ба- зами даних, особливо реляційного типу. Було відкрито багато проєктів із дослі- дження і створення експериментальних СУБД, запропоновано велику кількість мов запитів реляційних баз даних, вивчено питання оптимізації виконання запитів, структури зберігання, методів доступу, захисту, збереження цілісності. 1986 року з’явився перший стан- дарт SQL і відтоді він став єдиною офі- ційною мовою зовнішнього інтерфейсу реляційних СУБД. Було проведено численні дослі- дження з управління транзакціями, за які 49 Моделі та засоби систем баз даних і знань 1998 року Джеймс Ніколас Грей отримав премію Тьюрінга. Реляційні бази даних. У 70-х ро- ках учені, які працювали у сфері баз да- них, були переконані, що майбутнє баз даних – за створенням усе складніших структур даних, які дозволяли б адекват- но представляти інформаційну модель даних довільних предметни х галузей. Висловлювалися думки, що найближчим часом структури будуть настільки склад- ними, що в базах даних співвідношення корисної інформації та тієї, що її підтри- мує, буде 1 : 30. Внесок Е.Ф.Кодда в реляційні бази даних. І ось на цьому тлі 1970 року публі- кується стаття [59] маловідомого на той час британського вченого Едгара Франка Кодда (Edgar Frank Kodd) з компанії IBM, в якій він запропонував простішу структу- ру даних. Ця структура являла собою одно- мірну, плоску, нормалізовану таблицю. Едгар Франк Кодд Одномірність означає, що існує лише одна, горизонтальна шапка і не може бути вертикальної, як, скажімо, в навчальних планах ВУЗу. Плоскість свідчить про те, що в шапці не має бути полів, що складаються з багатьох підполів. Приміром, аби поле ПІБ складалося з підполів Прізвище, Ім′я, по- Батькові. І, нарешті, нормалізованість свід- чить про те, що в осередках таблиці може бути тільки атомарне (єдине) значення. Така структура дістала назву реляційного відно- шення, бо вона нагадує математичне по- няття відношення. Також було домовлено вважати, що такі відносини існують у пер- шій нормальній формі (First Normal Form – 1NF). У цій же праці він обґрунтував іс- нування двох сімейств реляційних мов, які пізніше були названі реляційним обчислен- ням і реляційною алгеброю. 1871 року Кодд публікує статтю [60], в якій наводить приклад того, як ло- гіка обчислення предикатів може бути ви- користана для створення високорівневої мови реляційної бази даних. Описана ним мова ALPHA була пер- шою мовою класу реляційного обчислен- ня. Хоча ALPHA не була реалізована, од- нак вона мала значний вплив на створення наступних комерційних реляційних мов. 1972 року Кодд публікує наступну свою важливу статтю [61], де він: - дає формальне визначення реля- ційної алгебри і реляційного обчислення (кортежно - орієнтованого); - формулює тезу реляційної по- вноти селективних можливостей мов за- питів до реляційної бази даних на основі реляційного обчислення. Ця теза була од- ностайно сприйнята вченими світу і в по- дальшому всі створювані мови запитів пе- ревірялися на реляційну повноту; - наводить алгоритм редукції до- вільного вираження реляційного обчислен- ня в семантично еквівалентне вираження реляційної алгебри, тим самим встанов- люючи її реляційну повноту. Цей результат згодом було названо теорією Кодда. Пізні- ше – Палермо (Palermo) [62] удосконалив цей алгоритм з точки зору підвищення його ефективності. Реляційна модель відпочатку кри- тикувалася за простоту її структури. Це, зокрема, відбулося й на конференції 1974 року «SIGMOD Workshop on Data Description, Access and Control», де ви- никли дебати між прихильниками реля- ційного і мережевого підходів, головними спікерами яких виступили Кодд і Бахман. Позиція Кодда на цих дебатах відображе- на у статті [63]. Зрештою, реляційна мо- дель здобула загальне визнання. Це мож- на пояснити тим, що в ній вдалося сфор- мулювати мови високого рівня (алгебра, 50 Моделі та засоби систем баз даних і знань обчислення). А це дозволило найбільш повно вирішити ту основну проблему, яка була поставлена перед базами даних, а саме – досягнення незалежності даних від програм. У свою чергу, підвищення складності структури даних призводить до неминучого зниження рівня мови ма- ніпулювання, що знижує можливості до- сягнення такої незалежності. Намагаючись надати додаткові мож- ливості, у праці [64] Е. Кодд запропонував підвищити семантику реляційної моделі, ідеї якої використовуються й нині в комер- ційних реляційних СУБД. Теорія залежності і нормальних форм. Реляційна модель дала серйозний поштовх для розвитку проєктування баз даних. Уперше задача логічного проєк- тування БД дістала строго формальний підхід. Суть цієї теорії полягала в тому, щоб на основі аналізу різних видів за- лежностей (обмежень цілісності), які іс- нують всередині реляційних відносин і між ними, виявляти небажані ситуації та усувати їх за допомогою обгрунтовани х процедур еквівалентних перетворень. За- звичай такою процедурою є декомпозиція відносин, тобто розмежування відносин на декілька. Основоположником цієї те- орії став Е.Ф.Кодд, опублікувавши пра- ці [65 - 67]. В них він визначив поняття функціональної залежності (Functional Dependency – FD) в реляційному відно- шенні, сформулював так звані аномалії маніпулювання відношеннями, виявив два небажані різновиди FD і транзитивні FD, котрі породжують ці аномалії. А саме – неповні FDі транзитивні FD, і запропо- нував процедуру декомпозиції, що усуває ці різновиди FD у результуючих відно- шеннях. Відношення, де відсутні неповні FD, отримали назву відношень у другій нормальній формі (2NF), а там, де від- сутні неповні й транзитивні FD – у третій нормальній формі (3NF). 1981 року Кодд був нагороджений премією Тьюрінга за фундаментальний і тривалий внесок в теорію і практику сис- тем управління базами даних, особливо ре- ляційного типу. Кристофер Дейт написав книгу[68] – історичний огляд наукового внеску Кодда в реляційну технологію. З точки зору структури функціо- нальних залежностей 3NF все ж мала пев- ні аномалії. З огляду на це, 1974 року Кодд разом із Раймондом Бойсом (Raymond F. Boyce) запропонували підсилити 3NF. Ре- зультована нормальна форма дістала назву нормальної форми Бойса – Кодда (Boyce – Kodd Normal Form – BCNF) [69]. Раймонд Бойс Як слушно зазначав Дейт, спочатку цю нормальну форму визначив Ян Хіт (Ian Heath) у статті [70]. Також зазначимо, що в цій статті він довів теорему про декомпо- зицію без втрат реляційного відношення за наявності FD, тобто декомпозиції, яка є ек- вівалентною за даними. Цю теорему було названо його ім′ям (Теорема Хіта). Вона застосовується при проведенні відношень в 2NF, 3NF і BCNF. Ян Хіт 51 Моделі та засоби систем баз даних і знань 1974 року Вільям Армстронг (William Ward Armstrong) у статті [71] за- пропонував систему аксіом FD (мінімаль- но повний набір правил виводу нових FD із заданих). Вони дістали назву аксіом Арм- стронга. Ці аксіоми дозволили визначити і дослідити такі поняття з системи FD, як виводимість, повнота, замикання, (міні- мальне) покриття, еквівалентність. Отри- мані в цьому напрямку результати сприяли вирішенню задачі автоматизації проєкту- вання баз даних. Вільям Армстронг 1977 року Рональд Феджин (Ronald Fagin) у статті [72] визначив новий вид залежності – багатозначну залежність (multi va lued depen dency MVD), наявність якої у відношеннях викликає аномалії маніпулювання. Запропонована ним фор- ма, що усуває цю ситуацію, була названа четвертною нормальною формою (Forth Normal Form – 4NF), а алгоритм приве- дення в 4NF базувався на доведеній ним теоремі (теорема Феджина). В наступній статті [73] була запропонована повна сис- тема аксіом MVD, а також дві аксіоми, які пов′язують FD і MVD (виведення MVD із FD і навпаки). Зазначимо, що окрім Феджина ба- гатозначну залежність досліджував та- кож Заніоло [74]. Крім того, Делобел [75] визначив поняття «ієрархічної де- композиції першого порядку», яке також пов′язане з концепцією багатозначної за- лежності. Рональд Феджин 1978 року Йорма Ріссанен (Jorma Rissanen) визначив залежність за з′єднанням (join dependency – JD) [76], яка стала узагальненням MVD (MVD є бі- нарною JD). На її основі Феджин у стат- ті [77] визначив і дослідив проєкційно- з′єднувальну нормальну форму (Projection- Join Normal Form – PJ/NF), яка з часом діс- тала назву п′ятої нормальної форми (Fifth Normal Form – 5NF). Йорма Ріссанен 52 Моделі та засоби систем баз даних і знань Зрештою, Кристофер Дейт (Christopher Date) визначив шосту нор- мальну форму (Sixth Normal Form – 6NF) як форму, де відсутні нетривіальні залеж- ності із з′єднання. Як підкреслюють чис- ленні дослідники, ця нормальна форма ви- явилася корисною в темпоральних базах даних. За ствердженням Дейта [78], 6NF рівносильна доменно-ключовій нормаль- ній формі (DK/NF) Феджина (див. далі). Кристофер Дейт Наведені вище залежності і нор- мальні форми належать до так званих класичних. Наведемо ще кілька визна- чених і досліджених видів залежностей. Із їх докладним аналізом та структурою взаємозв′язків між ними можна ознайоми- тися в роботі [79]: - поліпшена 3NF (Improved 3NF) [80]; - нормальна форма елементарно- го ключа (Elementary Key Normal Form – EKNF) [81]; - нормальна форма суперключа (Super Key Normal Form – SKNF) [82]; - приведена форма 5NF (reduced 5NF – 5NFR) [83]; - нормальна форма без надлиш- ковості (Redundancy Free Normal Form – RFNF) [84]; - нормальна форма із суттєвими кортежами (Essential Tuple Norm Form – ETNF) [85]; - доменно-ключова нормальна форма Феджина (Domain – Key Normal Form – DK/NF) [86]; - ієрархічна залежність [87] та її зв′язок із ієрархічною структурою даних [88]; - залежність по включенню і нор- мальні форми по включенню (Inclusion Normal Forms) [90 - 92]. Насамкінець зазначимо, що ми на- вели лише незначну кількість досліджених залежностей. У книзі [93] наведений пере- лік понад 600 статей, присвячених теорії залежностей і нормальних форм, а в моно- графії [94] аналізується близько 90 залеж- ностей. Мова запитів реляційної моделі. Реляційна модель дала суттєвий поштовх дослідженням зі створення мов запитів. У своєму огляді [95] Дональд Чемберлен (Donald D. Chemberlin) запропонував на- ступну класифікацію мов реляційних баз даних: мови реляційної алгебри, мови ре- ляційних обчислень, графічні мови і мови, орієнтовані на відображення. Даємо корот- кий огляд мов цих класів. Дональд Чемберлен Мови реляційної алгебри. Були запропоновані й експериментально опро- бовані наступні мови/системи, що ба- зуються на реляційній алгебрі: система VACAIMS [96] розроблена в МІТ, сис- теми IS/1 PRTV (Peterlee Relational Test Vehicle) [98], розроблені в науковому цен- трі ІВМ в Пітерлі (Англія), система RDMS [99] створена в дослідницькій лабораторіі General Motors. В багатьох системах роз- ширюється набір операцій реляційної 53 Моделі та засоби систем баз даних і знань алгебри шляхом введення специфічних. Паралельно проводились дослідження з оптимізації виконання виражень реляцій- ної алгебри [101 - 104]. В [105] наводить- ся широкий огляд досліджень з аналізу складності операцій та оптимізації запи- сів у реляційних базах даних. Мови реляційного обчислення. Як ми вже зазначали вище, першою мо- вою запитів реляційної моделі була мова ALPHA Кодда [60], яка безпосередньо базується на реляційному обчисленні. ALPHA дозволяє користувачеві, засто- совуючи такі поняття, як змінюваність і квантори, формувати непроцедурні запи- ти. Згодом були запропоновані інші мови, що, як і ALPHA, базувалися на реляцій- ному обчисленні. До них належать QUEL [106], створена в рамках науково-дослід- ницького проєкту Ingres в Каліфорній- ському університеті в Берклі, COLARD (Calculus Oriented Language for Rational Data) [107], RIL [108]. Графічні мови. В мовах, котрі від- носяться до графічних, формулювання запитів відбувається не з використанням традиційного лінійного синтаксису, а із заповненням осередків (ячеєк) у блан- ках таблиць.Мова CUPID (Casual User Pictorial Interface Design – робота з гра- фічним інтерфейсом непрофесійного ко- ристувача) [109 - 112] надає користува- чеві графічну мову запитів. CUPID має високорівневу меню – образну підмову, яка є зовнішнім інтерфейсом до системи INGRES. Ідея мови QBE (Query by Example – запит за зразком) [113 - 117], розробле- на Моше М. Злуфом (Moshe M/ Zloof), полягає в наступному. Користувачеві надаються чисті бланки таблиць бази даних. Формулювання запиту – це запо- внення бланків однією правильною від- повіддю, а задача системи – на підставі цього прикладу – вивести всі можливі правильні рядки таблиць. Попри оче- видну простоту, було доведено [113], що QBE є реляційно повною мовою. Різно- види цієї мови були реалізовані в СУБД PARADOX, DBASE IV, ACCESS. Остан- ня входить до складу Microsoft Office. М.М.Злуф розробив також мову ОВЕ (Office-by-Example – офіс за зразком) [118], яка стала розширенням QBE для офісних пропозицій. Моше М. Злуф Мови, орієнтовані на відображен- ня. !973 року колеги Кодда з лабораторії ІВМ у Сан Хосе Раймонд Бойс, Дональд Чемберлін і Вільям Кінг (Wil liam F. King) розробили мову SQUARE (Specifying Queries As Relational Express ions - специфі- кація запитів у вигляді реляційних виразів) [119, 120]. Використання SQUARE – подібної мови для опису численних уявлень (погля- дів), а також керування цілісністю даних та їх автоматизацією описане в статті [121]. На відміну від реляційного обчислення, SQUARE не використовує кванторів та зв′язаних змінних і тому не потребує від- повідної математичної підготовки. В мові запити висловлюються у вигляді природ- ніх примітивних операцій, якими люди користуються під час пошуку інформації в таблицях. Більшість семантичних простих запитів відображаються в мові просто й ла- конічно. Разом з тим SQUARE є реляційно повною мовою [120]. У 1974 році Бойс і Чемберлін пред- ставили мову SEQUEL (Structured English QUEry Language – структурована англій- ська мова запитів) [122], яка стала удо- сконаленим варіантом мови SQUARE. Змішаний синтаксис мови було названо 54 Моделі та засоби систем баз даних і знань блочно – структурованим синтаксисом ключових слів англійської мови. SQUARE і SEQUEL були декларативними мовами. Тобто, в них формулюється «що» треба знайти, а не «як» це зробити, характер- не для процедурних мов. 1975 року було реалізовано експерементальний варіант SEQUEL на базі розробленого інтерпре- татора [123]. Завдання інтерпретатора – мінімізувати виконання операцій досту- пу до даних під час виконання запитів за рахунок звуження простору пошуку. Задля цього були досліджені спеціальні оптимізуючи алгоритми. Сам інтерпрета- тор SEQUEL базується на XRM (Extended n-ary Relational Memory [124, 125]) – сис- темі, яка надає ефективний асоціатив- ний доступ до бінарних відношень. На- решті 1976 року було представлено мову SEQUEL2 [128], в якій уже були включе- ні всі основні засоби для оперування ба- зами даних: визначення, маніпулювання і керування. Оригінальний підхід був запропоно- ваний у мові APPLE (Access Path Producing Language – мова, яка породжує шлях до- ступу) [129], одним з авторів якого був Карл Роберт Карлсон (Carl Robert Carlson). Мова передбачає використання в запиті тільки імена атрибутів відношень бази да- них. Задача системи – на основі структури бази даних визначити численні відношен- ня, необхідні для виконання запиту, і ви- значити шлях доступу до них. Карл Роберт Карлсон Експерементальні дослідження і розробки. Вже на початку 70-х років було реалізовано низку ранніх реляційних сис- тем - MacAIMS (1970 р.), IS/1 (1972 р.) и PRTV, RENDEZVOUS (1974 р.) тощо. IS/1і PRTV. IS/1 була першою в світі експериментальною реляційною системою баз даних з обмеженими можливостями, реалізованою в науковому центрі ІВМ у Пі- терлі, Великобританія в 1970 – 1972 роках [130]. Із урахуванням результатів, отрима- них під час реалізації IS/1, була розроблена СУБД PRTV (Peterlee Relational Test Vehicle) [131], що дозволяла оперувати великими обсягами даних, мала свою власну мову за- писів ISBL рівня реляційної алгебри і була призначена для одного користувача. System/R і DB2. 1974 року в дослід- ницькій лабораторії в Сан Хосе компанії ІВМ був ініційований проєкт System/R зі створення експериментальної СУБД. Його задачею було продемонструвати можливість створення високопродуктивних промисло- вих реляційних СУБД. За основу було взято мову SEQUEL, яка в процесі обробки була перейменована на SQL, виходячи з юридич- них міркувань. До 1975 року було реалізо- вано повнофункціональну версію System/R для багатьох користувачів [132]. Зрештою, протягом 1978-79 років System/R витрима- ла всебічну практичну апробацію [133, 134], результати якої продемонстрували, що реля- ційні СУБД здатні забезпечити високу про- дуктивність. 1979 року проект System/R було завершено. Пізніше коротка історія експери- ментальних досліджень проекту System/R була викладена Чемберліном і його колегами в статті [135]. Враховуючи отриманий досвід, компанія ІВМ 1980 року почала, а 1982 року випустила промислову реляційну СУБД під назвою SQL/DS, яка згодом була переймено- вана на DB2 і підтримується на сьогодні на різних платформах і в різних конфігураціях. Вона стала стратегічним програмним про- дуктом компанії ІВМ. Oracle. 1974 року троє молодих про- грамістів із американської електронної ком- панії Ampex Corporation Ларрі Еллісон (Larry Ellison), Боб Майнер (Bob Miner) та Ед Оутс (Ed Oats), окрилені ідеями Кодда, заснували компанію Software Development Laboratories (SDL) для створення реляційного СУБД і взя- 55 Моделі та засоби систем баз даних і знань лися за розробку і маркетинг програми. 1979 року компанія дістала нову назву – Relational Software Inc. Того ж року компанія випустила Oracle, першу комерційну реляційну СУБД, де використовувалася мова SQL. Програ- ма дуже швидко набула популярності. 1982 року компанія знову була перейменована на Oracle Systems Corporation. Відтоді Oracle є найбільшим постачальником реляційних СУБД на базі SQL. Ingress. 1973 року двоє вчених дослідницької лабораторії Каліфорній-ського університету в Берклі Майкл Сто-унбрейкер (Michael Ralph Stonebraker) і Юджин Вонг (Eugene Wong), зацікавив-шись дослідженнями Кодда і резуль-татами своїх колег із ІВМ зі створення System R, вирішили почати власний про-ект зі створення реляційної СУБД. Майкл Стоунбрейкер Юджин Вонг Розроблювану експериментальну СУБД було названо INGRES (Interactive Graphics and REtrieval System). За наступні два роки були проведені експериментальні дослідження і розробки. Було прийнято проєктні рішення [136, 137], розроблені структури зберігання і методи доступу [138]. Також було розроблено опти- мізаційний алгоритм виконання операцій поєднання відношень, який отримав назву алгоритм Вонга – Юсефі (Wong – Youssefi algorithm) [139], досліджено механізм на- дання альтернативних поглядів через під- становку в запити користувачів їхніх визна- чень поглядів [140]. Авторизація і контроль цілісності забезпечувався використанням додаткових предикативів до запиту корис- тувача [141]. Реалізовано механізм безпеч- ного одночасного оновлення бази даних [142], а також система захисту [143]. До 1976 року була реалізована експеримен- тальна версія Ingress [144]Яка підтримува- ла мову QUEL. 1980 року частина співро- бітників цієї лабораторії заснували фірму Relational Technology, яка 1981 року ви- пустила промислову СУБД INGRESS. 1986 року INGRESS було переведено на SQL. Кілька ключових ідей з INGRESS досі ши- роко використовуються в реляційних систе- мах. Наприклад, в Non Stop SQL, Sybase і Microsoft SQL Server. Postgres. Після створення Relational Technology Стоунбрейкер разом із Лоурен- сом А. Роу (Lowrence A. Rowe) почали до- сліджувати можливості усунення обмежень реляційної моделі. Лоуренс А. Роу 56 Моделі та засоби систем баз даних і знань Новий проект дістав назву Postgres (POST inGRES). Були розроблені концеп- туальні проєктні рішення [145], запропо- нована об’єктивно – реляційна модель зі складними типами даних [146], розроблені структура збереження даних [147] і система правил [148] (тригерів), яка дозволяє визна- чати додаткові дії, ініційовані під час вико- нання операцій вставки, оновлення або ви- далення в таблицях бази даних. Попервах мовою запитів Postgres була PostQUEL. Мова була розроблена 1985 року в Каліфорнійському універси- теті в Берклі під керівництвом М. Стоунб- рейкера. PostQUEL базувалася на мові за- питів QUEL. 1987 року була реалізована перша версія СУБД Postgres, яка протягом наступних кількох років удосконалюва- лась [149]. Postgres почала широко вико- ристовуватись в економіці, промисловос- ті, медицині, фінансовій справі, астроно- мії і в багатьох інших галузях. А також використовувалася в навчальному проце- сі. 1991 року було додано інтерпретатор мови SQL, а 1996 – програмний продукт було перейменовано на PostgreSQL. 2014 року Майкл Стоунбрейкер став лауреа- том премії Тьюринга за фундаментальний внесок у концепції і методи, що лежать в основі сучасних систем баз даних [150]. СУБД для ПК. До 1980 року до- слідження, експериментальні й промис- лові розробки СУБД проводилися для великих і середніх комп′ютерів. На почат- ку 80-х з′явилися ІВМ РС і сумісні з ним ПК, оснащені ОС MS-DOS, що привело до появи СУБД для ПК. 1981 року ком- панія Ashton-Tale випустила dBase II для ПК. ЇЇ не можна було назвати справжньою СУБД, бо чимало важливих функцій не підтримувались, однак для ПК того часу це було значною подією. Dbase II здобула велику популярність. 1984 року було ви- пущено досконалішу версію dBase ІІІ, в 1986 – її розширений варіант dBase ІІІ+, а 1998 - dBase ІV. Вони стали доміную- чими СУБД для ІВМ РС. Успіх dBase ІІІ+ обумовив появу на ринку числених ана- логів, сумісних за мовою і структурою файлів бази даних. До них відносяться FoxBASE (1984), FoxPro (1990) компа- нії Fox Software, Clipper (1985) компанії Nantucker Corporation. Згодом вони були об′єднані популярним серед професіо- налів поняттям “xBase”. Тенденція ство- рення продуктів – аналогів і велика по- пулярність xBase активізувала діяльність зі створення стандарту. Було зроблено дві спроби стандартизації мови xBase у 1987 – 1988 і 1992 роках, але вони не мали успі- ху. Тож у 80-х роках домінуючу роль на ринку СУБД для ІВМ РС мало сімейство СУВД xBase. 1985 року компанія Ansa Software випустила СУБД Paradox. Цей високое- фективний продукт для створення реля- ційних баз даних був примітний своєю мовою QBE (Query By Example) і мовою розробки додатків. Він був популярний у кінці 80-х – початку 90-х років і конкуру- вав із сімейством xBase. Оптимізація. Реляційні системи базуються на високорівневому непро- цедурному інтерфейсі, їхні мови записів декларативні. Через це в таких системах принципово важливим є питання оптимі- зації виконання запитів. У 70 – 80 роки минулого століття були проведені числен- ні дослідження і опублікована величезна кількість статей із цього питання. Ми не зупиняємося в цій статті на даній про- блемі і посилаємо читача до змістовного огляду С.Д.Кузнєцова [151]. Стандартизація. У травні 1979 року була створена робоча група із реля- ційних баз даних (RTG) ANSI/X3/SPARC DBS-SG під керівництвом Майкла Бро- уді (Michael L.Brodie) для проведення досліджень з обґрунтування можливості створення стандарту по реляційних ба- зах даних. 1981 року ця група склала звіт [152], де підтверджувалась така необхід- ність. Для наступного сприяння в роботі зі створення такого стандарту було роз- роблено «Каталог функцій реляційних концепцій, мов і систем», який мав би допомогти виявити і встановити ті ас- пекти, як самої реляційної моделі, так і реляційних баз даних, які можуть розгля- датися кандидатами для стандартизації. До початку 80-х років у зв’язку із широ- ким розповсюдженням реляційних СУБД виникла необхідність аналізу можливос- ті стандартизації мови для управління 57 Моделі та засоби систем баз даних і знань реляційними базами даних і розробки такого стандарту, якщо це буде визнано доцільним. Майкл Броуді У зв’язку з цим 1982 року Амери- канський національний інститут стан- дартів (American National Standards Institute – ANSI) створив комітет X3H2, перед яким було поставлене це завдан- ня. Впродовж 11 років комітет очолю- вав Дональд Р. Дойч (Donald R.Deutsch). Комітет мав розглянути різні реляційні мови, описані і реалізовані на той час. Однак, враховуючи широку розповсю- дженість SQL у промислових СУБД і той факт, що тоді він фактично вже став стандартом, комітет зупинив свій вибір саме на цій мові. Узявши за основу її діа- лект, реалізований в СУБД DB2, комітет прагнув його узагальнити, враховуючи реалізовані в інших реляційних СУБД можливості. Після чотирьох років робо- ти, 1986 року запропонований комітетом варіант SQL, було офіційно затверджено як стандарт ANSI, а 1987 року він був узятий за стандарт Міжнародної органі- зації стандартів (International Standards Organization – ISO). Згодом стандарт ANSI/ISO взяв уряд США за федераль- ний стандарт в галузі обробки інфор- мації (Federal Information Processing Standard – FIPS). 1989 року стандарт був дещо змінений і дістав назву SQL – 89 ( або SQL1). Відтоді SQL було визнано єдиною мовою зовнішніх інтерфейсів реляційних баз даних. ANSI/ISO постійно працює над її удосконаленням і випуском нових вер- сій. За 35 років було випущено 10 версій SQL (1986, 1989, 1999, 2003, 2006, 2008, 2011, 2016, 2019). Дональд Р. Дойч На завершення цього розділу зазна- чимо, що до початку 80-х років на ринку з′явилися дві промислові реляційні СУБД: Oracle і DB2. Згодом з′явилися Postgress, Informix тощо. Почалася ера реляційних СУБД, які й по сьогодні є найбільш попу- лярними на ринку баз даних. Управління транзакціями. Важливою функцією використання БД є управління транзакціями. Транзак- ція (Transaction) – це логічна одиниця ро- боти, що являє собою групу послідовних операцій над даними БД, яка може бути або використана повністю й успішно, до- тримуючись цілісності даних і незалежно від інших паралельно працюючих транзак- цій, або не використана зовсім. Тоді вона не матиме ніякого ефекту. Поняття тран- закції вперше було введене й обговорене Джимом Греєм (Jim Grey) і його колегами в працях [153, 155, 158]. Правила ACID. Одним із найпоши- реніших наборів вимог до транзакцій і тран- закційних систем є набір ACID (Atomicity, Consistency, Isolation, Durability). - Atomicity – атомарність. Тран- закція або виконується повністю, або не виконується взагалі. З точки зору зовніш- 58 Моделі та засоби систем баз даних і знань нього сприйняття, вона не має ніяких про- міжних станів. - Consistency – узгодженість. Транзакція зберігає обмеження цілісності бази даних. По завершенні роботи транзак- ція залишає базу даних у цілісному стані. - Isolation – ізольованість. Тран- закція працює так, ніби не було ніяких од- ночасно працюючих транзакцій. - Durability –довготривалість. По закінченні роботи всі зроблені транзакці- єю зміни зберігаються в базі даних на дов- готривалій основі. Вимоги ACID були сформульовані переважно на початку 80-х років Джимом Греєм [153]. Водночас існують спеціальні системи з послабленими транзакцій ними властивостями [154]. Ізольованість транзакції – ситуація, в якій транзакція захищена (за ізольована) від дії інших одночасно з нею виконува- них транзакцій. Іншими словами, ізоляція гарантує, що проміжні стани транзакції є невидимими іншим одночасно працюючим транзакціям. Ступінь ізоляції транзакції визначається рівнями ізоляції. Аби до- сягти ізольованості транзакції, слід вико- ристовувати методи управління спільним виконанням транзакцій. План виконання набору транзакцій називається серіальним у разі, якщо результат спільного виконан- ня транзакцій еквівалентний результату певного послідовного виконання цих таки транзакцій. Серіалізація. Серіалізація транзак- цій – це механізм такого спільного виконан- ня транзакцій, коли результат еквівалент- ний результату певного послідовного вико- нання цих транзакцій. Забезпечення такого механізму є основною функцією управлін- ня транзакціями. Система, в якій підтриму- ється серіалізація транзакцій, забезпечує реальну ізольованість користувачів. Концепція серіалізації була сформу- льована і досліджена Греєм і його колега- ми в працях [155, 158]. Окрім цього, в пра- ці [6] було визначено двофазний протокол блокування, а також досліджена техніка предикатного блокування. Питання межі дії блокування (гранулярності) обговорені в статтях [155, 156]. Моделі транзакцій. Варто зазначи- ти, що всі моделі транзакцій визначалися, як правило, з урахуванням класів приклад- них систем, де вони застосовуються [11]. Було запропоновано дві фундаментальні моделі транзакцій – модель сторінки і мо- дель об′єкту. Перша з них – виконавча мо- дель, а друга – концептуальна. Модель сторінок (модель Read/ Write). Базується на припущенні, що осно- вні операції бази даних – це запис і читання сторінки, котрі передаються між зовніш- ньою і оперативною пам′яттю. Сторінко- ва модель транзакції бере свій початок у другій половині 70-х років зі статей Джи- ма Грея [153, 157] і Капалі Есваран (Kapali Eswaran) [158]. Одночасно виникло спо- ріднене поняття – атомарна дія [159, 160]. Концепція сторінкової моделі транзакції стала предметом інтенсивних теоретичних досліджень 80-х років [161 - 164] і дієва дотепер, хоча й набула кількох розширень і варіацій [165]. Із оглядом досліджень і роз- робок цієї моделі можна ознайомитися в працях [11, 166]. Усі наведені далі моделі належать до класу так званих моделей об′єктів. Плоскі транзакції (Flat Transactions) мають єдиний рівень управляння для до- вільної кількості елементарних дій. Вони не мають внутрішньої структури. Плос- кі транзакції – основні будівельні блоки для реалізації принципу атомарності. В плоских транзакціях атомарність і довго- тривалість підтримуються механізмом від- новлення, який зазвичай забезпечується веденням журналів операцій оновлення, через що операції типу «відмінити», «по- вторити» можна виконувати за потреби. Ізольованість забезпечується механізмом управління паралелізмом (concurrency control), який реалізується з допомогою блокувань. Огляд досліджень з управління паралелізмом наведено в праці [167]. Узгодженість забезпечується механіз- мом управління цілісністю. Було запро- поновано два підходи до управління ці- лісністю в транзакціях: включення цього механізму в СУБД [168] і підтримання цілісності за рахунок зусиль розробників додатків [11]. 59 Моделі та засоби систем баз даних і знань Плоскі транзакції повністю дотри- муються всіх принципів ACID і є цілком достатніми для багатьох традиційних до- датків баз даних, у яких час виконання транзакції відносно нетривалий, кількість паралельних транзакцій досить невелика, і база даних не розподілена. Однак такі ACID-транзакції не взмозі підтримува- ти довгочасні транзакції та транзакції зі складною внутрішньою структурою і роз- поділеними базами даних. Точки збереження. Це такі момен- ти в обчислювальному процесі, починаю- чи з яких можливий перезапуск обчислень у разі виникнення будь-яких проблем. Вони вперше були визначені 1976 року в SystemR [132]. У разі виникнення збою відбувається відкат до останньої збереже- ної точки з вивільненням усіх зроблених після цієї точки блокувань. Хоча механізм точок збереження широко використовуєть- ся в плоских транзакціях, однак він набув нового звучання в розширених моделях транзакцій, які з′явилися у 80-х роках. Усі наведені далі розширені моделі транзакцій призводять до ослаблення тих чи інших складових ACID. Модель багатоланкових транзак- цій (Chained Transactions) подібна до моде- лі плоскої транзакції з точки збереження, але вона не лише дає можливість позначи- ти будь-яку точку для можливого повтор- ного виконання, а й фіксацію тієї частини роботи, яка була виконана в момент досяг- нення цієї точки. Втім відкат може бути виконаний лише до останньої контроль- ної точки. В цьому підході було закладено ідею декомпозиції великих транзакцій на дрібніші послідовно виконувані субтран- закції, які відповідають інтервалам між точками. У разі збою поточної субтранзак- ції, попередня вже була зафіксована і її ре- зультати були збережені в базі даних, тому відкат проводиться до цієї точки збережен- ня. Зазначимо, що в цій моделі атомарність і ізольованість не гарантуються для всієї транзакції. Згідно [11] ідея багатоланкової транзакції вперше реалізована в системі IMS компанії IBM. Вкладені транзакції (Nested Transactions). Важливим кроком у розви- тку базової моделі транзакції було роз- ширення плоскої (однорівневої) моде- лі в багаторівневу структуру. Вкладена транзакція вперше була визначена 1981 року Моссом (Moss) [169], а потім [170]. Її концепція базувалася на понятті сфер контролю (spheres of control) [171]. Вкла- дена транзакція – це численні субтранзак- ції, що здатні містити інші субтранзакції, таким чином утворюючи транзакційне дерево. Дочірні транзакція запускається після батьківської, а батьківська транзак- ція завершується лише після завершення роботи всіх її дочірніх транзакцій. У разі аварійного завершення батьківської тран- закції, всі її дочірні транакції також за- вершуються аварійно. У разі аварійного завершення дочірньої транзакції її бать- ко може обрати альтернативний варіант (contingency subtransaction – транзакція на непередбачуваний випадок). Вкладе- ні транзакції забезпечують повну ізоля- цію на глобальному рівні. Для вкладених транзакцій послаблена здатність довго- тривалості ACID. Модель вкладених транзакцій по- вністю відповідає активним базам даних, оскільки ієрархічна структура моделі до- зволяє легко погоджувати зв′язок між основною трансакцією і запущеною з до- помогою тригера. В статті [172] запропо- новані наступні варіанти синхронізації за- пуску субтранзакції тригеру і щодо осно- вної транзакції: - негайний (immediate) - транзак- ція запускається одразу після настання по- дії тригера; - відкладається (deff ered) - запуск субтранзакції відкладається до завершення основної транзакції; - причинно-незалежна (causally independent) – субтранзакція тригера запу- сається як цілком самостійна транзакція; - причинно-залежна (causally dependent) – субтранзакція тригера запус- кається як самостійна транзакція, однак її успішне завершення залежить від успіш- ного завершення основної транзакції. Відкриті вкладені транзакції (Open Nested Transactions) [173] послаблю- ють вимогу ізольованості через те, що ре- зультати зафіксованих субтранзакцій ста- ють видимими іншим одночасно працю- 60 Моделі та засоби систем баз даних і знань ючим вкладеним транзакціям. При цьому досягається високий рівень паралельності. Багаторівневі транзакції є найза- гальнішим варіантом вкладених транзак- цій [173, 174]. Субтранзакції багаторівне- вої транзакції здатні провести фіксацію і звільнення своїх ресурсів до завершення роботи глобальної транзакції. Якщо гло- бальна транзакція завершується аварій- но, то для підтримки атомарності слід зробити відкат субтранзакції запуском їх компенсуючи субтранзакцій. Однак все ж можливе порушення цілісності в зв′язку з тим, що певна інша транзакція мала до- ступ до результатів завершених субтран- закцій, які потім були відкатані компен- суючими субтранзакціями. Було запропо- новано вирішення цієї ситуації. Зокрема, введенням горизонтальних компенсаторів [175]. У монографії [176] наводяться роз- пізнавальні ознаки багаторівневих і вкла- дених транзакцій. Розподільні транзакції (Distributed Transactions). Це сукупність субтранзак- цій, прив′язаних до локальних баз даних і загальної глобальної транзакції. У статті [177] подається огляд розподілених тран- закцій, а також розглянута «модель базис- ної транзакції» (Base Transaction Model) і її розширення. 1996 року було запропоно- вано модель x/Open Distributed Transaction Processing (x/Open DTP) [178]. Ця модель є стандартом для протоколу двофазної фіксації (2РС – Two Phase Commit). Гнучкі транзакції (Flexible Transactions) [179, 180] – були запропоно- вані для розподілених баз даних. У цьому випадку глобальна транзакція є набором субтранзакцій, кожна з яких здійснює до- ступ до даних на одному локальному вуз- лі. Модель гнучкої транзакції підтримує гнучке управління обчисленням шляхом специфікації залежностей двох типів між субтранзакціями: 1) залежності порядку обчислень між двома субтранзакціями; 2) залежності альтернатив між двома підна- борами субтранзакцій. Було розроблено кілька конкретних моделей гнучких тран- закцій: Con Tracts, Flex Transaction, Split Transaction, S-transaction та інші [179 - 183]. Була також запропонована мова ІРL [184] для специфікації гнучких транзакцій із атомарністю й ізольованістю, які визна- чаються користувачем. Тривалі транзакції, компенса- тори і модель Saga. Ідея компенсуючих транзакцій (Compensation Transactions) вперше була висловлена Греєм у праці [157], згодом вона була формалізована в [185, 186] і, зрештою, використана в моделі Saga [187]. Ця модель належить- до тривалих транзакцій (Long – Running Transactions) [188]. Моделі розподільних транзакцій вдало справляються з коротко- часними транзакціями, однак, водночас є неприйнятними для тривалих транзакцій. В моделі Saga пропонується розподіляти тривалі транзакції на коротші. Saga скла- дається із сукупності впорядкованих ACID субтранзакцій і сукупності компенсуючих субтранзакцій, по одній на кожну з осно- вних субтранзакцій. Координація всього процесу здійснюється за допомогою по- відомлень і тимчасових поміток. Saga завершується успішно за умови успіш- ної фіксації всіх субтранзакцій. Якщо ж котрась із субтранзакцій завершується аварійно, то всі попередньо завершені субтранзакції відкочуються виконанням так званих компенсуючи субтранзакцій. Saga послаблює вимоги до ізольованості і збільшує міжтранзакційний паралелізм. У праці [189] запропонована вдосконале- на модель – вкладена Saga, яка дозволяє представляти лінійну структуру тривалих транзакцій у вигляді ієрархічної транзак- ційної структури. Транзакції Split/Joint (розділи- ти/об′єднати). Концепція роз′єднання/ об′єднання транзакцій вперше була описа- на в [190], а відтак ретельно пропрацьова- но в [191] для таких тривалих видів діяль- ності, як автоматизоване проєктування, інженерне проєктування, проєктування і розробка програмного забезпечення тощо. Операція Split розділяє транзакцію на дві серіалізовані транзакції, які фіксуються або завершуються аварійно незалежно одна від одної. Операція Joint об′єднує дві транзакції в одну. Split використовується, наприклад, щоб якнайшвидше зафіксува- ти результати роботи частини транзакцій, або щоб розподілити роботу між кількома виконавцями. Зі свого боку Joint рівно- 61 Моделі та засоби систем баз даних і знань сильний передачі всієї роботи одному ви- конавцеві [191]. Згодом операції Split та Joint було включено до вкладених тран- закцій для створення комбінованих моде- лей транзакцій [192]. Кооперативні транзакції були за- пропоновані в [193] для використання в системах, де яскраво виражена потреба у взаємодії між транзакціями, в кооператив- ному інтерактивному робочому середови- щі. Фундаментальна проблема, пов′язана з кооперативними транзакціями – це від- сутність для них чітких критеріїв узго- джуваності. Для кооперативних транзак- цій було запропоновано їхню структури- зацію у вигляді дерева, названого ієрархі- єю кооперативних транзакцій (Cooperative Transaction Hierarchy). В окремому випад- ку ієрархія обмежена трьома рівнями: ко- рінь, одна або більше транзакційних груп і кілька кооперативних транзакцій. Ко- оперативні транзакції утворюють листя ієрархії, яке об′єднується в групи. Члени групи транзакцій працюють разом, ви- конуючи певну логічну одиницю роботи, названу задачею, котра може бути роз- бита на підзадачі. Кожна кооперативна транзакція відповідальна за конкретну підзадачу. Оскільки вимога атомарності послаблена, кооперативна транзакція не зобов′язана зберігати глобальне непроти- річчя бази даних, тобто зміни, зробилені кооперативною транзакцією, одразу ста- ють видимими іншими кооперативними транзакціями цієї групи. Щоб результати були видимі поза групою, використову- ються точки збереження. В ієрархії може існувати більше трьох рівнів, тобто до- пускається кілька рівнів вкладення груп. Кооперативні транзакції не обов′язково мають бути серіалізованими. Через свою інтерактивну природу, кооперативні тран- закції тривають значно довше звичайних. Згодом, на відміну від традиційних тран- закцій, кооперативні не обов′язково ма- ють бути повністю ізольованими. ACTA і її похідні. ACTA [192, 194, 195] – це мета модель, яка полегшує спе- цифікацію, аналіз і синтез розширених моделей транзакції. Формалізм ACTA має за основу логіку першого порядку з відношенням перебування, яке дозволяє розробнику транзакцій специфікувати як високорівневі властивості (вимоги) мо- делі, так і низькорівневі аспекти поведін- ки в термінах аксіом. Окрім підтримки специфікації і аналізу існуючих моделей транзакцій, ACTA дає можливість специ- фікувати вимоги нових транзакцій них додатків та синтезувати моделі, що задо- вольняють ці вимоги. В роботі [42] авто- ри запропонували спрощений спосіб роз- робки розширених транзакцій, названий ASSET. Він базується на транзактивних примітивах, запозичених у ASTA і може використовуватися на рівні програмуван- ня для специфікації спеціалізованих для конкретних додатків моделей транзакцій, які дозволяють підтримувати кооперацію і взаємодію. У 90-і роки велика увага при- ділялася транзакціям в системах реально- го часу [197, 198, 199] і в мобільних сис- темах баз даних [200, 201]. Транзакції веб – сервісів. Із почат- ком 2000-их років усе більша увага при- діляється використанню транзакцій для слабопов′язаних веб-сервісів із метою за- безпечення погоджуваності й надійності веб-сервісних додатків. Наразі розробле- но три стандарти, що мають відношення до транзакцій веб-сервісів. Business Transaction Protocol (BTP) [202, 203]. Перша версія розроблена 2004 року в OASIS. Вона стосується як веб-сервісів, так і довільних бізнес про- цесів. Це протокол, що базується на мові XML, для опису і управління складни- ми багатокроковими B2B-транзакціями (business-to-business) в Інтернеті. Він дає можливість координувати транзакції між багатьма автономними сервісами, а ви- користання XML робить його придатним для веб-сервісних архітектур [204]. Web Services Transactions (WS – Tx) [205, 206]. Специфікація, схвалена 2007 року, складається з WS – Coordination (WS-C), WS-Atomic Transaction (WS – AT), WS-Business Activity (WS – BA) та розроблена в Microsoft, IBM і BEA. WS – Tx визначає механізми транзакційної інтероперабельності між веб-сервісами та забезпечує впровадження якісних тран- закцій них сервісів до веб=сервісних до- датків. WS – Tx визначає послідовність 62 Моделі та засоби систем баз даних і знань повідомлень, що передаються сторонами – учасниками в короткострокових атомар- них транзакціях (WS – AT) і (тривалих) бізнес – транзакціях (WS – BA). WS – C визначає координаційні протоколи пові- домлень, якими обмінюються сторони – учасники транзакцій. WS – C підтримує різні координаційні моделі [2007]. WS Composite Application Framework (WS – CAF) [2008]. Стандарт розроблено в OASIS за участі компа- ній SUN, Oracle, Arijuna та інших. Мета стандарту – розробка інтероперабельних і простих у використанні складових веб- сервісних додатків. Було здійснено порівняльні дослі- дження наведених вище трьох стандартів, з результатами яких можна ознайомитися в статтях [209, 211]. 1998 року Джеймс Ніколас Грей (James Nicholas Gray) був нагороджений премією Тьюрінга за основоположні ідеї в галузі баз даних, за дослідження з об- робки транзакцій і технічне лідерство в реалізації систем. Джеймс Ніколас Грей ( Далі буде) References 1. Olle T. William. The CODASYL Approach to Data Base Management. Chichester, Eng- land: Wiley-Inter sci ence; 1978: 287p. 2. Tsichritzis D.C., Lochovsky F.H., Data mod- els, Prentice-Hall, Englewood Cliff s, N.J., 1982, 381 p. 3. Embley D., Thalheim B., editors. Hand book of conceptual modelling: its usage and its challenges. Springer; Berlin 2011 4. Date C.J. An Introduction to Database Sys- tems, 8th Edition. Addison-Wesley Long- man Publishing Co., Inc.75 Arlington Street, Suite 300 Boston, MA United States 5. Gallaire H., Minker J., eds. Logic and Data- bases. New York: Plenum. 1978. 6. Ullman J.D. Principles of Database and Knowledge-Based Systems.Maryland: Com- puter Sciences Press Inc., 1989 7. Maier D., Warren D.S. 1988. Computing with Logic: Logic Programming with Pro- log. Benjamin-Cummings Publishing Co., Inc.Subs. of Addison-Wesley Longman Publ. Co390 Bridge Pkwy. Redwood City, CA United States. 535 p. 8. Ozkarahan E.A. Database Machines And Database Management. Prentice Hall, 1986, 636 p. 9. Kalinichenko L.A., Ryvkin V.M. Database and Knowledge base Machines (Rus). Mos- cow, Nauka, 1990, 296 p. 10. Özsu M.T., Valduriez P. Principles of Dis- tributed Database Systems, Fourth Edition, Springer, 2020 11. Gray J., Reuter A. Transaction Proce- ssing: Concepts and Techniques. Mor gan Kaufmann, San Francisco. 1993 12. Harrison G. Next Generation Databases: NoSQL, NewSQL and Big Data, Apress, 2015, 235 p. 13. Kogalovsky M. R. Encyclopedia of databas- es technologies (Rus). Moscow, Finance and Statistics,.2005. — 800 с. 14. Bachman Charles W. Integrated Data Store - The Information Processing Machine That We Need! General Electric Computer Us- ers Symposium. Kiamesha Lake. New York May 17-18, 1962 15. IDS Reference Manual GE 625/635, GE In- form. Sys. Div., Pheonix, Ariz., CPB 1093B, Feb. 1968. 16. Bachman Charles W. “The Origin of the In- tegrated Data Store (IDS): The First Direct- Access DBMS,” IEEE Annals of the History of Computing, Vol. 31, Num. 4, Oct-Dec 2009, pp. 42-54. 63 Моделі та засоби систем баз даних і знань 17. History of IMS: Beginnings at NASA. - https://www.ibm.com/support/knowl- e d g e c e n t e r / z o s b a s i c s / c o m . i b m . i m - s i n t r o . d o c . i n t r o / i p 0 i n d 0 0 11 0 0 3 7 1 0 . htm#ip0ind0011003710 18. Long R., Harrington M., Hain R., Nicholls G. IMS Primer. - http://www.redbooks.ibm. com/redbooks/pdfs/sg245352.pdf 19. Information Management System/360, Ap- plication Description Manual H20-0524-1. IBM Corp., White plains, N.Y., July 1968. 20. Nies T. Cincom Systems’ Total. Annals of the History of Computing, IEEE. 2009, vol. 31, No 4, pp. 55-61. 21. Bachman Charles W. “The program- mer as navigator”. Communications of the ACM, November 1973, Vol. 16 No. 11, Pages 653-658 https://dl.acm.org/ doi/10.1145/355611.362534 22. Haigh T. How Data Got its Base: Information Storage Software in the 1950s and 1960s // IEEE Annals of the History of Computing (Volume: 31, Issue: 4, Oct.-Dec. 2009) pp. 6-25 23. CODASYL: “Data Base Task Group Re- port”, ACM (New York 1971). 24. GUIDE-SHARE: “Data Base Management System Requirements”, SHARE Inc. (New York 1970) 25. CMSAG Joint Utilities Project: “Data Man- agement System Requirements”, CMSAG (Orlando, FL 1971) 26. Langefors B. Theoretical Analysis of In- formation Systems. 402 S. m. Fig. Lund/ Kopenhagen/Oslo 1966. Akademisk Forlag/ Universitetsforlaget 27. Langefors B. Information systems theory. Inf. Syst. 2(4): 207-219 (1977) 28. Langefors B. Infological models and infor- mation user views. Information Systems Volume 5, Issue 1, 1980, Pages 17-32 29. Sungren Bo. An Infological Approach to Data Bases. National Central Bureau of Sta- tistics, Sweden, Stokholm, 1973. 294 p. 30. SPARC: “Outline for Preparation of Pro- posals for Standardization”, Document SPARC/90, CBEMA (Washington, DC 1974). 31. ANSI/X3/SPARC, ‘Study Group on Data Base Management Systems: Interim Report 75-02-08’ // Newsletter ACM SIGMOD Re- cord, FDT, Vol 7, No. 2, 1975. – P. 1-140 32. Tsichritzis D.C., Klug A. “The ANSI/X3/ SPARC DBMS Framework”. Report of the Study Group on a Database Management System”. Information Systems, Vol. 3, No. 4, 1978. 33. CODASYL/Data Description Language Committee (DDLC), “June 73 Report”. CO- DASYL Data Description Language Com- mittee Journal of Development, June 1973 34. “CODASYL Data Description Language Committee Journal of Development”, 1978. 35. Concepts and Terminology for the Concep- tual Schema and the Information Base, van Griethauzen, J.J., Ed., ISO TC97/SC5/WG3, 1982, Publ. 695. 36) Falkenberg E,D. Structuring and Representa- tion of Information at the Interface Between Data Base User and Data Base Management System. Diss. Univ. Stuttgart (1975). 37. Falkenberg E., Concepts of Modelling Infor- mation, Proc. of the IFIP Working Conf. on Modelling in Data Base Management Sys- tems, Nijssen, G.M., Ed., North-Holland, 1976, p. 95-109. 38. Abrial Jean-Raymond, Data Semantics, In: J. W. Klimbie, K. L. Koff eman (eds.), Da- tabase Management, Proceedings IFIP TC2 Conference. Grgese, 1974., North-Holland Publishing Company, pp.1-60. 39. Bracchi G., Paolini P., Pelagatti G. “Binary Logical Associations in Data Modelling,” in J. M. Nijssen (ed.), Modelling in Database Management Systems (Proc. IFIP TC2 Con- ference, Freudenstadt), North-Holland Pub- lishing Company, Amsterdam, The Nether- lands, 1976. 40. Durchholz R. and Richter G., “Concepts for data base management systems”. In: Data Base Management, J. W. Klimbie and K. L. Koff eman, (eds.), 41. Senko, M.E., Conceptual Schemas, Abstract Data Structures, Enterprise Descriptions, In: International Computing Symposium, Liege, Belgium, 1977, North-Holland Publishing Company. 42. Senko M.E., Altman E.B., Astrahan MM., Fehder P.L. Data Structures and Accessing in Data-Base Systems. IBM System J., v. 12, no. 1 (1973). 43. Senko M.E., “The DDL in the Context of Multilevel Structured Description: DIAM II with FORAL”. Proc. of the IFIP TC-2 Spe- 64 Моделі та засоби систем баз даних і знань cial Working Conference on Data Base De- scription, pp.239-257, Jan. 1975 44. Smith J.M. and Smith D.C.P. Databas e Ab- stractions : Aggregation and Generalization. ACM Trans, on Database Syst, v. 2, no. 2, 1977, pp. 105133 45. Smith J.M. and Smith D.C.P. Databas e Ab- stractions: Aggregation. Comm. of the ACM, v. 20, no. 6, 1977, pp. 405-413 46. Hammer, M. and McLeod, D., Database De- scription with SDM: A Semantic Database Model, ACM Transactions on Database Sys- tems,1981, Vol. 6, No. 3, pp. 351-386. 47. Abiteboul, S., Hull, R., IFO: A Formal Se- mantic Database Model, ACM Trans. Data- base Syst. 12, 4 (1987), 525-565. 48. Bachman, C. W., “Data Structure Diagrams”, Data Base, 1969, No 1, 2, pp. 4-10. 49. Engles R.W. A Tutorial on Data-base Orga- nization, Annual review in automatic pro- gramming, Vol 7. Part I, Pergamon Press, 1972, 93 p. 50. Chen P.P. The Entity-Relationship Model — Toward a Unifi ed View of Data // ACM Transactions on Database Systems (TODS), 1976. — Vol. 1, No. 1. — P. 9–36. 51. Barker R. Case*Method: Entity Relation- ship Modelling Publisher: Addison-Wesley, 1990, 240 p. 52. Gogolla M. An extended entity-relation- ship model – fundamentals and pragmatics. LNCS, vol. 767. Berlin: Springer; 1994. 53. Hartmann S. Reasoning about participation constraints and Chen’s constraints. In: The Fourteenth Australian Database Conference, Adelaide, Australia. Conferences in Re- search and Practice in Information Technol- ogy; 2003. p. 105–113. 54. Hohenstein U. Formale Semantik eines er- weiterten Entity-Relationship-Modells. Stuttgart: Teubner; 1993. 55. Thalheim B. Entity-relationship modeling – foundations of database technology. Berlin: Springer; 2000. 56. Teorey, T.J., Yang, D. and Fry, J.P. A Logi- cal Design Methodology for Relational Da- tabases Using the Extended Entity-Relation- ship Model, ACM Computer Surveys, 1986, Vol.18, No. 2. pp. 197-222 57. Vincent S. Lai, Jean Pierre Kuilboer, Jan Lu- cille Guynes. Temporal databases: model de- sign and commercialization prospects. ACM SIGMIS Database: the DATABASE for Ad- vances in Information Systems, 1994, Vol. 25, No 3, pp. 6-18 58. Gregersen H., Jense C.S. Temporal Enti- ty-Relationship Models—a Survey. IEEE Transactions on Knowledge and Data Engi- neering, 1999, Vol. 11, No. 3, pp. 464 - 497 59. Codd E.F. “A Relational Model of Data for Large Shared Data Banks,” Communications of the ACM, Vol. 13, No. 6 (June 1970), pp 377-397 60. Codd E.F. “A data base sublanguage found- ed on the relational calculus,” Proc. 1971 ACM-SIGFIDET Workshop on Data De- scription, Access, and Control, Nov. 1971. ACM. New York, 1971, DP. 35-68 61. Codd E. F. “Relational Completeness of Data Base Sublanguages” (presented at Cou- rant Computer Science Symposia Series 6, “Data Base Systems.” New York City, N.Y. May 24th-25th. 1971), IBM Research Re- port RJ987 62. Palermo F.P. “A data base search problem”, Proceedings 4th Computer and Information Science Symposium (COINS IV), Miami Beach, Dec. 1972, Plenum Press, New York, 1972. pp. 67–101 63. Codd E.F. “Interactive Support for Non- programmers: The Relational and Network Approaches,”Proceedings of the ACM SIG- MOD Workshop on Data Description, Ac- cess, and Control, Vol. II, Ann Arbor, Michi- gan, May 1974. 64. Codd E.F. Extending the database relational model to capture more meaning. ACM Trans. on Database Syst., vol. 4, No. 4, 1979, pp. 397-434 65. Codd E. F. “The Second and Third Normal Forms for the Relational Model”, IBM tech- nical memo (October 6th. 1970). 66. Codd E.F. “Further Normalization of the Da- tabase Relational Model”, in Data Base Sys- tems, Courant Inst. Comput.Sci. Symp. Se- ries 6 (New York, 1971), Englewood Cliff s, N.J.: Prentice Hall, 1972, pp. 33-64. 67. Codd E.F. “Normalized Data Base Structure: A Brief Tutorial”, Proc. 1971 ACM SIGFI- DET Workshop on Data Description, Ac- cess. and Control. San Diego. Calif. 1971, p. 1-17 68. Date C. J. The database relational model : a retrospective review and analysisю - Ad- 65 Моделі та засоби систем баз даних і знань dison-Wesley Educational Publishers Inc., 2000, 152 p. 69. Codd E.F. “Recent Investigations in Rela- tional Database Systems,” Information Pro- cessing 74, pp.1017–1021. 70. Heath I.J. Unacceptable File Operations in a Relational Data Base. Conference: Proceed- ings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California, November 11-12, 1971, pp. 19–33 71. Armstrong William Ward. “Dependency structures of data base relationships”. In Jack L. Rosenfeld and Herbert Freeman, editors, Proceedings of IFIP Congress 74, pp.580-583, North Holland, 1974 72. Fagin R. Multivalued Dependencies and a New Normal Form for Relational Databas- es / R. Fagin // ACM Transactions on Da- tabase Systems. – 1977. – Vol. 2, № 1. – P. 262-278. 73. Beeri C., Fagin R., Howard J.H. A com- plete axiomatization for functional and multivalued dependencies in database rela- tions. Proc. ACM SIGMOD Conf., D.C.P. Smith, Ed., Toronto, Canada, August 1977, pp. 47-61. 74. Zaniolo C. Analysis and design of relational schemata for database systems. Ph.D. Diss., Tech. Rep. UCLA-ENG-7669, U. of Califor- nia, Los Angeles, Calif., July 1976. 75. Delobel C., Leonard M. The decomposi- tion process in a relational model. Proc. Int. Workshop on Data Structure Models for In- formation Systems, Presses U. de Namur, Namur, Belgium, May 1974, pp. 57-80. 76. Rissanen J. Theory of relations for databas- es--A tutorial survey, in “Proc. 7th Sym- pos. on Math. Found. of Computer Sci- ence,” 1978, pp. 537-551, Lecture Notes in Computer Science No. 64, Springer- Verlag, Berlin 77. Fagin R. Normal Forms and Relational Da- tabase Operators / R. Fagin // Proceedings of the ACM SIGMOD International Con- ference on Management of Data (Boston, Mass., May 30-June 1), ACM, New York, 1979, p. 153-160 78. Date Chris J. “On DK/NF nor- mal form”. - https://web.archive.org/ web/20120406123712/http://www.dbde- bunk.com/page/page/621935.htm 79. Buy B., Puzikova A. V. Some nonclassical normal forms in relational databases (Rus) // Bulletin of Taras Shevchenko National Uni- versity of Kyiv. Series Physics & Mathemat- ics, 2015, No 1, pp. 65-74 80. Ling T. W. An Improved Third Normal Form for Relational Databases / T. W. Ling, F. W. Tompa, T. Kameda // ACM Transactions on Database Systems. – 1981. – Vol. 6, № 2. – P. 329-346. 81. Zaniolo C. A New Normal Form for the De- sign of Relational Database Schemata / C. Zaniolo // ACM Transactions on Database Systems. – 1982. – Vol. 7, № 3. – P. 489-499 82. Normann R. Minimal lossless decomposi- tions and some normal forms between 4NF and PJ/NF / R. Normann // Information Systems. – 1998. – Vol. 23, № 7. – P. 509- 516. 83. Vincent M. W. A corrected 5NF defi nition for relational database design / M. W. Vin- cent // Theoretical Computer Science (TCS). – 1997. – Vol. 185, № 2. – P. 379-391. 84. Vincent M.W. Redundancy Elimination and a New Normal Form for Relational Database Design / M. W. Vincent // In Semantics in Databases (Libkin, L., Thalheim, B., eds.), vol. 1358 of LNCS. – 1998. – P. 247-264. 85. Darwen H. A Normal Form for Preventing Redundant Tuples in Relational Databases / H. Darwen, C. Date, R. Fagin // Proceedings of the 15th International Conference on Da- tabase Theory – ICDT’2012, March 26– 30, 2012, Berlin, Germany. – P. 114-126. 86. Fagin R. A Normal Form for Relational Da- tabases That Is Based on Domains and Keys / R. Fagin // Communications of the ACM. – 1981. – Vol. 6. – P. 387-415. 87. Delobel C. Normalization and hierarchical dependencies in the relational data model. ACM TODS 1978, 3, 3, 201-222. 88. Pasichnik V.V., Stogniy A. A. Relational models of data bases (Rus). - М.: CNI- IATOMINFORM, 1983, 268 p. 89. Casanova M.A. Inclusion dependencies and their interaction with functional dependen- cies / M. A. Casanova, R. Fagin, C. H. Pa- padimitriou // Journal of Computer and Sys- tem Sciences. – 1984. – № 28. – P. 29-59. 90. Nicolas J.M. Mutual dependencies and same results on indecomposable relations / J. M. Nicolas // Proceedings of the fourth interna- 66 Моделі та засоби систем баз даних і знань tional conference on Very Large Data Bases, 1978. – Vol. 4. – P. 360-367. 91. Ling T.W. Logical Database Design with Inclusion Dependencies / T. W. Ling, C. H. Goh // In Proceedings of the Eighth Inter- national Conference on Data Engineering, Tempe, Arizona, 1992. – P. 642-649. 92. Levene M. Justifi cation for Inclusion De- pendency Normal Form / M. Levene, M. W. Vincent // IEEE Transactions on Knowledge and Data Engineering, 2000. – Vol. 12, № 2. – P. 281-291. 93. Thalheim B. Bibliographie zur Theorie der Abhangigkeiten in relationalen Datenban- ken, 1970-1984, TU Dresden 566/85, Dres- den 1985. 94. Thalheim B. Dependencies in Relational Da- tabases, 1991, Teubner-Texte zur Mathema- tik, 214 Pages 95. Chamberlin D.D. “Relational Data-Base Management Systems,” Computing Sur- veys, Vol. 8, No. 1, p. 43-66, March 1976 96. Goldstein R.C., Strnad A.L. “The MACAI- MS Data Management System,” Proceed- ings of t he ACM-SIGFIDST Workshop on Data Description, Acess and Control, Nov. 1970. ACM, New York, 1970, pp. 201-229. 97. Notley M.G. “The Peterlee IS/1 system,” IBM UK Scientifi c Centre Report UKSC- 0018, March 1972. 98. Todd S.J.P. “Peterlee relational test vehicle PRTV, a technical overview,” IBM Scientifi c Centre Report UKSC 0075, Peterlee, Eng- land, July 1975. 99. Whitney V.K.M. “RDMS: A Relational Data Management System,” Proceedings of the Fourth International Svmposium on Com- puter and Information Sciences (COINS IV), Dec. 1972, Plenum Press, New York, 1972. 100. Pecherer R.M. “ Effi cient evaluation of expressions in a relational algebra,” Proc. ACM Pacifi c 76 Regional Conf., April 1975, ACM, New York, 1975, pp. 44-49. 101. Gotlieb L.R. “Computing joins of relations, Proc. ACM-SIGMOD International Con- ference on Management of Data (San Jose, Calif., May 14-16, 1975), ACM. New York, 1975, pp. 55-63 102. Smith J.M., Chang P. “Optimizing the per- formance of a relational algebra data base interface,” Comm. ACM 18, 10 (Oct. 1975), pp. 568-579. 103. Hall P. A. V. Optimisation of a single re- lational expression in a relational data base system, IBM Scientifi c Centre Renort UKSC 0076. Peterlee, England, July 1975. 104. Palermo F.P. An APL environment for test- ing relational operators and data base search algorithms. Proc. APL 75 Conf., June 1975, ACM. New York, 1975, pp. 249-256 105. Bui D.B., Skobelev V.G. Complexity of op- erations in database systems (a survey), Ra- dioelectronic and computer systems, 2014, No 6(70). pp. 53-59 106. Held G.D., Stonebraker M.R., Wong E. “IN- GRES: a relational data base system,” Proc. AFZPS h’ational Computer Conf., May 1975, Vol. 44, AFIPS Press, Montvale, N.J., 1975, pp 409-416. 107. Bracchi G., Fedeli A., Paolini P. A lan- guage for a relational data base manage- ment system. Proc. Sixth Annual Princeton Conf. on Information Science and Systems, March 1972, Princeton Univ., N.J., 1972. pp. 84-92. 108. Fehder P.L. The representation-independent language. Res. Rep. RJ 1121, IBM Research Laboratory, San Jose, Calif., Nov. 1972 109. McDonald N.,Stonebraker M. “CU- PID — The Friendly Query Language,” University of California, Berkeley, Techni- cal Report No. UCB/ERL M487, October 1974. http://www2.eecs.berkeley.edu/Pubs/ TechRpts/1974/ERL-m-487.pdf 110. McDonald N.,Stonebraker M Cupid--The friendly query language. Proc. ACM- Pacif- ic-75, San Francisco, Calif., April 1975, pp. 127-131. 111. McDonald N. “Cupid: A Graphics Oriented Facility for Support of Non-Programmer In- teractions with a Data Base,” University of California, Berkeley, Technical Report No. UCB/ERL M563, November 1975. 112. McDonald N., Stonebraker M. “CUPID: the friendly query language,” Proc. ACM Pa- cifi c 75 Regional Conf., Auril 1975. ACM. New York. 1975, pp, 127-131. 113. Zloof M.M.“Query by example ” RC4917, IBM T. J. Watson Research Center. York- town Heights, N. Y., July 1974. 114. Zloof M.M. “Query by Example,” Proc. AFIPS National Computer Conf., May 1975, Vol. 44, AFIPS Press, Montvale, N.J., 1975, pp 431-438. 67 Моделі та засоби систем баз даних і знань 115. Zloof M.M. “Query by Example: the invo- cation and defi nition of tables and forms,” Proc. Internatl. Conf. on Very Large Data Bases, Sept. 1975, ACM, New York, 1975, pp. 1-24. 116. Zloof M.M. Query-by-Example: a data base language. IBM System J., 16:4, 1977, pp. 324–343 117. Thomas J. C., Gould J.D. “A psychologi- cal study of Query by Example,” Proc. AFIPS National Computer Conf., May 1975, Vol. 44, AFIPS Press, Montvale, N.J., p 439-445. 118. Zloof M.M. Offi ce-by-Example: A busi- ness language that unifi es data and word pro-cessing and electronic mail. IBM Sys- tems Journal (Volume: 21, Issue: 3, 1982). Page(s): 272 - 304 119. Boyce R.F., Chamberlin D.D., King W.F., Hammer M.M. Specifying queries as rela- tional expressions. Proc. ACM SIGPLAN/ SIGIR Interface Meeting, Gaithersburg, Md., Nov. 1973. 120. Boyce R.F., Chamberlin D.D., King W.F., Hammer M.M. Specifying queries as rela- tional expressions: the SQUARE data sub- language. Communications of the ACM, 1975, Volume 18, No 11, p. 621-628 121. Boyce, R.F., Chamberlin D.D. Using a structured English query language as a data defi nition facility. Res. Report RJ 1318, IBM Res. Lab., San Jose, Calif., Dec. 1973. 122. Chamberlin D D., Boyce R.F. SEQUEL: A structured English query language. SIG- FIDET ‘74: Proceedings of the 1974 ACM SIGFIDET (now SIGMOD. workshop on Data description, access and control. May 1974 Pages 249–264. 123. Astrahan M.M., Chamberlin D.D. Imple- mentation of a structured English query lan- guage. Communications of the ACM, 1975, Volume 18, No 10 pp. 580-588 124. Lorie R.A. XRM-an extended (n-ary. re- lational memory. Tech. Report G320-2096, IBM Scientifi c Center, Cambridge, Mass., Jan. 1974. 125. Astrahan M.M., Lorie R.A. “SEQUEL- XRM: a relational system,” Proc. ACM Pa- cifi c 76 Regional Conf., April 1975, ACM, New York, 1975, pp. 34-38. 126. Symonds A.J., Lorie, R. A. “A schema for describing a relational data base,” Proc. ACM-SIGFIDET Workshop on Data De- scription and Access, Nov. 1970, ACM, New York, 1970, pp. 230-245. 127. Lorie R.A., Symonds,A.J. “A relational ac- cess method for interactive applications,” Courant Computer Science Symposia, 6, Data Base Systems, Prentice-Hall, New York, 1971, pp 99-124. 128. Chamberlin D D., Astrahan M.M., Eswaran K.P., Griffi ths P.P., Lorie R.A., Mehl J.W., Reisner Ph., Wade B.W. SEQUEL 2: A Uni- fi ed Approach to Data Defi nition, Manipula- tion, and Control. IBM Journal of Research and Development 20(6): 560-575 (1976) 129. Carlson C.R., Kaplan R.S. A Generalized Access Path Model and Its Application to a Relational Data Base System. SIGMOD ‘76: Proceedings of the 1976 ACM SIGMOD in- ternational conference on Management of data. June 1976, Pages 143–154 130. Notley M, “Peterlee IS/1 System”, UKSC Report 18, 1972 131. Todd S. “The Peterlee Relational Test Ve- hicle - A System Overview”. IBM Systems Journal. 1976, 15 (4): 285–308. 132. Astrahan M.M., et al. System R: A relation- al approach to database management. ACM Trans. Database Syst. Vol. 1, No 2 (June 1976), 97-137 133. Chamberlin D.D. A summary of user expe- rience with the SQL data sublanguage. Proc. Internat. Conf. Data Bases, Aberdeen, Scot- land, July 1980, pp. 181-203 134. Chamberlin D.D., et al. Support for repeti- tive transactions and ad-hoc queries in Sys- tem R. ACM Trans. Database Syst. Vol. 6, No 1 (March 1981), 70-94. 135. Chamberlin D.D., Gilbert, A.M., Yost, R.A. A history of System R and SQL/data system. VLDB ‘81: Proceedings of the seventh international conference on Very Large Data Bases - Volume 7, September 1981, pp. 456–464 136. McDonald N., Stonebraker M., Wong E. “Preliminary design of INGRES: Part I,” Electronics Research Lab. Report ERL- M435, Univ. of California, Berkeley, April 1974. http://www2.eecs.berkeley.edu/Pubs/ TechRpts/1974/ERL-m-435.pdf 137. McDonald N., Stonebraker M., Wong E. “Preliminary design of INGRES: Part II,” Electronics Research Lab. Report ERL- 68 Моделі та засоби систем баз даних і знань M436, Univ. of California, Berkeley, April 1974. http://www2.eecs.berkeley.edu/Pubs/ TechRpts/1974/ERL-m-436.pdf 138. Held G., Stonebraker M. “Storage struc- tures and access methods in the raational data base management system INGRES,” Proc. ACM Pacifi c 75 Regional Conf., April 1975, ACM, New York, 1975, pp 26-33. 139. Wong E., Youssefi K. Decomposition--A strategy for query processing. ACM Trans. on Database Systems I, 3 (Sept. 1976), 223- 241 140. Stonebraker M. “Implementation of integ- rity constraints and views by query modi- fi cation,” Proc. ACM-SIGMOD Conf. May 1975, ACM, New York, 1975, pp 65-78. 141. Stonebraker M., Wong E. Access control in a relational data base management sys- tem by query modifi cation. Proc. 1974 ACM Nat. Conf., San Diego, Calif., Nov. 1974, pp. 180-187. 142. Stonebraker M. “High level integrity as- surance in relational data base management systems,” Electronics Research Lab. Report ERL-M473, Univ. of Calif. at Berkeley, Au- gust 1974. 143. Stonebraker M., Rubinstein P. The INGRES protection system. Proc. 1976 ACM Nation- al Conf., Houston, Tex., Oct. 1976 144. Stonebraker M., Held G., Wong E., Kreps P. “The Design and Implementa- tion of INGRES”. ACM Transactions on Database Systems. Vol.1, No 3. 1976 pp.189–222. 145. Stonebraker M., Rowe L. “The design of POSTGRES,” in Proc. 1986 ACM-SIGMOD Conf., Washington, DC, June 1986. 146. Rowe L.A., Stonebraker M. “The POST- GRES data model,” in Proc. 13th Intl. Conf. on Very Large Data Bases, P. M. Stocker, W. Kent, P. Hammersley, Eds., San Francisco, CA: Morgan Kaufmann Publishers Inc., 1987, pp. 83-96. 147. Stonebraker M. “ The design of the POST- GRES storage system “, in Proc. 1987 VLDB Conf:, Brighton, England, Sept. 1987. 148. Stonebraker M., Hanson E., Hong C. H. “The design of the POSTGRES rules sys- tem”, Proc. IEEE Conference on Data Engi- neering, Feb. 1987. 149. Stonebraker M., Rowe L.A., Hirohama M. The Implementation Of Postgres IEEE Transactions on Knowledge and Data Engi- neering, 1990, Vol. 2, No 1, pp. 125 - 142 150. ACM Turing Award Goes to Pioneer in Da- tabase Systems Architecture: MIT’s Michael Stonebraker Brought Relational Database Systems from Concept to Commercial Suc- cess. - https://www.prweb.com/pdfdown- load/12607207.pdf 151. Kuznetsov S.D. Methods for optimization of query execution in relational DBMS (Rus) // “Vychislitelnye nauki. Vol. 1 (Itogi nauki i tekhniki VINITI AN USSR” M.; VINITI AN USSR, 1989.- 76-153. - http://masters. donntu.org/2002/foreign/aswad/lib/mpbd. htm или http://citforum.ru/database/articles/ art_26.shtml 152. Brodie M.L., Schmidt J.W. Final Report of the ANSI/X3/SPARC DBS-SG Relational Database Task Group. SIGMOD Record 12(4): i-62 (1982). Литература по транзакциям 153. Gray J. The Transaction Concept: Virtues and Limitations. In: Proceedings of the 7th International Conference on Very Large Da- tabases, 1981. pp. 144—154, IEEE, Cannes, France, 154. Advanced Transaction Models and Archi- tectures. Sushil Jajodia and Larry Kersch- berg (eds.) Springer Scienee+Business Me- dia New York. 1997 155. Gray J., Lorie R., Putzulo G. “Granularity of Locks and Degrees of Consistency in a Shared Data Base,” In Modelling in Data Base Management Systems. G.M. Ni]ssen, (ed.) North Holland Publishing Company, 1976, pp.365-394 156. Reis D.R., Stonebraker M. Eff ect of locking granularity in a database management sys- tems. ACM Trans. on Database Syst., 2:3, 1977, pp. 233-246. 157. Gray J.N. Notes on data base operating systems. In: Bayer R., Graham R.M., Seeg- müller G. (eds) Operating Systems. Lecture Notes in Computer Science, vol 60. Spring- er, Berlin, Heidelberg. 1978. p. 393–481. 158. Eswaran K.P, Gray J, Lorie R.A, Traiger I.L. The notions of consistency and predi- cate locks in a database system. Commun ACM. 1976;19(11):624–633. 159. Lampson B.W. Atomic transactions. In: Lampson B.W, Paul M, Siegert H.J, edi- tors. Distributed systems – architecture and 69 Моделі та засоби систем баз даних і знань implementation: an advanced course, LNCS, vol. 105. Berlin: Springer; 1981. p. 246–285. 160. Lomet D.B. Process structuring, synchroni- zation, recovery using atomic actions. ACM SIGPLAN Not. 1977; 12(3):128–137. 161. Bernstein P.A, Shipman D.W, Wong W.S. Formal aspects of serializability in database concurrency control. IEEE Trans Software Eng. 1979;SE-5(3): 203–216. 162. Bernstein P.A, Hadzilacos V, Goodman N. Concurrency control and recovery in data- base systems. Reading: Addison-Wesley; 1987. 163. Papadimitriou C.H. The serializability of concurrent database updates. J ACM. 1979;26(4):631–653. 164. Papadimitriou C.H. The theory of database concurrency control. Rockville: Computer Science; 1986. 165. Weikum G, Vossen G. Transactional in- formation systems – theory, algorithms, the practice of concurrency control and re- covery. San Francisco: Morgan Kaufmann; 2002. 166. Shasha D, Bonnet P. Database tuning – principles, experiments, and troubleshoot- ing techniques. San Francisco: Morgan Kaufmann; 2003. 167. Ramamritham, K., Chrysanthis, P. K., (1997). Advances in Concurrency Control and Transaction Processing. IEEE Com- puter Society Press, Los Alamitos, Cali- fornia. 168. Grefen P., Apers P. (1993). Integrity Control in Relational Database Systems - An Over- view. Journal of Data & Knowledge Engi- neering (10)2: 187-223. 169. Moss J.E.B. Nested transactions: an ap- proach to reliable distributed computing. Technical Report. PhD Thesis. UMI Order Number: TR-260: Massachusetts Institute of Technology; 1981. p. 178. 170. Been C, Bernstein P.A., Goodman N, Lai M.Y., Shasha D.E. A concurrency control theory for nested transactions. Proc. of Second ACM Symposium on Principles of Database Systems (PODS), 1983, pp. 45-62 171. Davies C.T. Data processing spheres of con- trol. IBM Syst J. 1978;17(2):179–198. 172. Dayal U., Hsu M., Ladin R. A generalized transaction model for long-running activi- ties and active databases. IEEE Data Engi- neering Bulletin, March 1991, vol. 14, No 1,. pp 4-8 173. Weikum G. and Schek H. Concepts and applications of multilevel transactions and open-nested transactions. In Elmagarmid A., editor. Database Transaction Mod- els for Advanced Applications. Morgan Kaufmann Publishers. San Mateo. CA., 1992, pp. 515–553. 174. Weikum G. Principles and realization strat- egies of multilevel transaction ma nagement. ACM Transactions on Database Systems. 1991;16(1):132–180. 175. Krychniak P., Rusinkiewicz M., Chichocki A., Sheth A., Thomas G. Bounding the Efects of Compensation under Relaxed Multi-Lev- el Seria lizability. Distributed and Parallel Database Systems, 1996, 4(4), pp. 355-374 176. Lewis, P. M., Bernstein A. J., Kifer M. (2002). Databases and Transaction Process- ing: An Application-Oriented Ap p roach. Ad- dison-Wesley, United States 177. Breitbart Y., Garcia-Molina H., Silberschatz A. Overview of multi da ta base transaction management. VLDB Jour nal, 1992, vol. 1, No 2, pp. 181-240. 178. X/Open Company Ltd., (1996). Distributed Transaction Processing: Reference Model, version 3. X/Open Company Ltd., U.K. 179. Elmagarmid A.K., Leu Y., Litwin W.,Rusinkiewicz M. (1990) A Multidata- base Transaction Model for InterBase. In Proc. of the 16th. Intl. Conference on Very Large Data Bases, pp. 507-518, Brisbane. Australia 180. Zhang A., Nodine M., Bhargava B., Bukhres O. Ensuring Relaxed Atomicity for Flexible Transactions in Multidatabase Systems. In Proc/ 1994 SIGMOD Interna- tional Conference on Management of Data, 1994, pp. 67-78 181. Zhang A, Nodine M, Bhargava B. Glob- al scheduling for flexible transactions in heterogeneous distributed database systems. IEEE Trans Knowl Data Eng. 2001;13(3):439–450. 182. Wächter H, Reuter A. The ConTract mod- el. In: Elmagarmid A.K., editor. Database transaction models for advanced applica- tions. Los Altos: Morgan Kaufmann; 1992. pp 39-43 70 Моделі та засоби систем баз даних і знань 183. Veijalainen J., Eliassen F. The S—transac- tion Model. In: Elmagarmid A.K., editor. Database transaction models for advanced applications. Los Altos: Morgan Kaufmann, 1992, pp. 55-59 184. Chen J., Bukhres O., Elmagarmid A. K. (1993). IPL: A Multidatabase Transaction Specifi cation Language. In Proc. of the 13th Intl. Conference on Distributed Computing Systems - ICDCS ‘93. 1993, pp. 439-448 185. Garcia-Molina H. Using Semantic Knowl- edge for Transaction Processing in a Distrib- uted Database. ACM Transactions on Data- base Systems, 8(2):186-213, June 1983. 186. Korth H., Levy E., Silberschatz A. A For- mal Approach to Recovery by Compensat- ing Transactions. In Proceedings of the 16th International Conference on Very Large Data Bases, Brisbane, Australia, 1990, pp. 95–106 187. Garcia-Molina H., Salem K. Sagas. In Proc. of ACM SIGMOD International Conference on Management of Data, 1987, pp 249-259 San Francisco, CA. 188. Bancilhon F., Kim W., Korth H. A model of CAD Transactions. VLDB ‘85: Proceed- ings of the 11th international conference on Very Large Data Bases - Volume 11, 1985, pp. 25–33 189. Garcia-Molina. H., Salem K., Gawlick D., Klein J., Kleissner K., Modeling Long- Running Activities as Nested Sagas, IEEE Data Engineering Bulletin, 1991, 14(1) pp 14-18 190. Pu C., Kaiser G.E., Hutchinson N.C. Split- transactions for open-ended activities. In: Proceedings of the 14th International Con- ference on Very Large Data Bases; 1988. p. 26–37. 191. Kaiser G.E., Pu C. Dynamic restructuring of transactions. In: Elmagarmid AK, editor. Database transaction models for advanced applications. Burlington: Morgan Kaufmann Publishers; 1992. p. 265–295. 192. Chrysanthis P.K, Ramamritham K. Syn- thesis of extended transaction models us- ing ACTA. ACM Trans. Database Syst. 1994;19(3):450–491. 193. Nodine M.H., Zdonik S.B. Cooperative transaction hierarchies: Transaction sup- port for design applications. VLDB Journal, 1(1):41–80, 1992. 194. Chrysanthis P.K., Ramamritham, K., (1990). ACTA: A Framework for Specifying and Reasoning about Transaction Structure and Behavior. Proceedings of the ACM SIG- MOD International Conference on Manage- ment of Data: 194-203. 195. Chrysanthis P.K., Ramamritham K. (1992). ACTA: The SAGA Continues. In Elmagar- mid A., editor. Database Transaction Mod- els for Advanced Applications. Morgan Kaufmann Publishers. San Mateo. CA., 1992, pp. 349-397 196. Biliris A., Dar S., Gehani N., Jagadish H., Ramamritham K. (1994). ASSET: A Sys- tem for Supporting Extended Transactions. In Proc. of ACM SIGMOD Conference on Management of Data, pages 44-54, Minne- apolis, M.N. 197. Abbott R., Garsia-Molina Н. Scheduling real-time transactions: a performance evalu- ation. ACM Trans, on Database Syst, 17(3), September 1992, pp. 513-560 198. Agrawal D., El Abbadi A., Jeff ers R. Using Delayed Commitment in Locking Protocols for Real-Time Databases. SIGMOD Confer- ence 1992: 104-113 199. Hong D., Johnson Т., Chakravarthy S. Real-Time Transaction Scheduling: A Cost Conscious Approach. SIGMOD Conference 1993: 197-206. 200. Alonso R., Korth H. Database System Is- sues in Nomadic Computing. SIGMOD Re- cord, Vol. 22, No 2,1993, pp.388-392. 201. Imelinski Т., Badrinath B.R. Data Manage- ment for Mobile Computing. SIGMOD Re- cord, Vol. 22, No. 1, 1993 202. Ceponkus A., Dalal S., Fletcher T., Furniss P., Green A., Pope B. Business transaction protocol, Version 1.1, 2002 203. Business transaction protocol. - http:// www.oasis-open.org/committees/tc_home. php?wg_abbrev=businesstransaction [2004] 204. Stevens M., Mathew S., McGovern J., Ty- agi S. Java Web Services Architecture. San Francisco: Morgan Kaufmann Publishers, 2003. 205. WSTx (Web Services Transactions). - https://searchapparchitecture.techtarget. com/defi nition/WSTx-Web-Services-Trans- actions 206. IBM, BEA Systems, Microsoft, Arjuna, Hi- tachi, IONA, \Web Services Transactions 71 Моделі та засоби систем баз даних і знань specifations,” IBM Developer Works, IBM, 2004. 207. Curbera F., Khalaf R., Mukhi N., Tai S.,Weerawarana S. The Next Step in Web Services,” Communications of the ACM, October 2003, Vol. 46, No. 10, Pages 29-34 208. OASIS Web Services Composite Applica- tion Framework (WS-CAF), OASIS, 2006. - http://www.oasis-open.org/committees/ tc_home.php?wg_abbrev=ws-caf 209. Little M., Freund Th. J.. A comparison of web services transaction protocols: A com- parative analysis of WS-C/WS-Tx and OA- SIS BTP,” IBM, 2003. Available: http:// www-128.ibm.com/developerworks/web- services/library/ws-comproto/. [Accessed May 2008]. 210. Kratz B., Protocols For Long Running Busi- ness Transactions. Technical Report 17, In- folab Technical Report Series, 2004, 48 p. 211. Jin T., Goschnick S. (2004) Utilizing Web Services in an Agent Based Transaction Model. In: Cavedon L., Maamar Z., Mar- tin D., Benatallah B. (eds) Extending Web Services Technologies. Multiagent Systems, Artifi cial Societies, and Simulated Organi- zations (International Book Series), vol 13. Springer, Boston, MA. pp 273-291 Одержано 24.06.2021 Про автора: Резніченко Валерий Анатолієвич, кандидат фізико-математичних наук, заступник завідувача відділом. Кількість публікацій в українських виданнях – 61. Кількість зарубіжнихих публікацій – 4. Індекс Хірша – 12. http://orcid.org/0000-0002-4451-8931. Місце роботи автора: Інститут програмних систем НАН України, 03187, м. Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 3559. E-mail: reznich@isofts.kiev.ua

60 Years of Databases

Репозитарії

Схожі ресурси