Взаємозв’язок між розширеною табличною алгеброю нескінченних таблиць та розширеною мультимножинною табличною алгеброю

Abstract

Розглянуто деякі теоретичні питання табличних баз даних. Методологічну основу дослідження складає композиційний підхід до програмування, суть якого полягає у розгляді спеціальних алгебр. У статті розглянуто два математичні формалізми, такі як розширена таблична алгебра нескінченних таблиць та розширена мультимножинна таблична алгебра, сигнатури операцій яких поповнені додатковими операціями внутрішніх і зовнішніх з’єднань, агрегатними операціями та операцією напівз’єднання. Подано основні визначення, що стосуються цих формалізмів: означення схеми, таблиці та відповідної алгебри. Основу статті складає розгляд питання про взаємозв’язок між розширеною табличною алгеброю нескінченних таблиць та розширеною мультимножинною табличною алгеброю. Враховуючи той факт, що перша компонента таблиці розширеної табличної алгебри нескінченних таблиць — це множина рядків, а отже 1-мультимножина, постає питання про те чи є розширена таблична алгебра нескінченних таблиць підалгеброю розширеної мультимножинної табличної алгебри. Саме цьому питанню і приділено увагу в статті. Спочатку встановлено, що множина всіх таблиць розширеної табличної алгебри нескінченних таблиць є підмножиною множини всіх таблиць розширеної мультимножинної табличної алгебри. Потім, використовуючи теоретико-множинні та логіко-алгебраїчні методи, доведено, що розширена таблична алгебра нескінченних таблиць не замкнена відносно деяких сигнатурних операцій розширеної мультимножинної табличної алгебри. До цих операцій належать об’єднання, проекція та активне доповнення. Таким чином, розширена таблична алгебра нескінченних таблиць не утворює підалгебру розширеної мультимножинної табличної алгебри. Отримані результати можуть бути використані для розробки мов запитів до табличних баз даних та для розробки програмного забезпечення з табличними базами даних.

The paper is focused on some theoretical questions of the table databases. The methodological basis of the research is a compositional approach to programming, the core of which is to consider special algebras. Two mathematical formalisms such as extended table algebra of infinite tables and extended multiset table algebra are considered. Their signatures are supplemented by additional operations such as inner and outer joins, semijoin and aggregate operations. Basic definitions referring to these formalisms are given. This article deals with the topic of the relationship between extended table algebra of infinite tables and extended multiset table algebra. Taking into consideration the fact that the first component of a table of extended table algebra of infinite tables is a set of tuples, and therefore a 1-multiset, the question arises whether the extended table algebra of infinite tables is subalgebra of extended multiset table algebra. This research is devoted to this question. The first thing that needed to be established is that the set of all tables of extended table algebra of infinite tables is a subset of the set of all tables of extended multiset table algebra. Then, applying the set-theoretic and logical-algebraic methods, it is proved that the extended table algebra of infinite tables is not closed with respect to some signature operations of the extended multiset table algebra. Thus, table algebra of infinite tables does not form subalgebra of multiset table algebra since it is not closed with respect to the union, projection and active complement. So multiset table algebra is not a wider formalism then table algebra of infinite tables. The obtained results can be applied to the development of query languages for table databases and software with table databases.

Рассмотрены некоторые теоретические вопросы табличных баз данных. Методологическую основу иссле- дования составляет композиционный подход к программированию, суть которого заключается в рассмотрении специальных алгебр. В статье рассмотрены два математических формализма, такие как расширенная таб- личная алгебра бесконечных таблиц и расширенная мультимножественная табличная алгебра, сигнатуры опе- раций которых пополнены дополнительными операциями внутренних и внешних соединений, агрегатными опе- рациями и операцией полусоединения. Представлены основные определения, касающиеся этих формализмов: определение схемы, таблицы и соответствующих алгебр. Основу статьи составляет рассмотрение вопроса о взаимосвязи между расширенной табличной алгеброй бесконечных таблиц и расширенной мультимножественной табличной алгеброй. Учитывая тот факт, что первая компонента таблицы расширенной табличной алгебры бесконечных таблиц — это множество строк, а значит 1-мультимножество, возникает вопрос о том является ли расширенная табличная алгебра бесконечных таблиц подалгеброй расширенной мультимножественной табличной алгебры. Именно этому вопросу и уделено внимание в статье. Сначала установлено, что множество всех таблиц расширенной табличной алгебры бесконечных таблиц является подмножеством множества всех таблиц расширенной мультимножественной табличной алгебры. Затем, используя теоретико-множественные и логико-алгебраические методы, доказано, что расширенная табличная алгебра бесконечных таблиц не замкнута относительно некоторых сигнатурных операций расши- ренной мультимножественной табличной алгебры. К этим операциям относятся операции объединения, проек- ции и активного дополнения. Таким образом, расширенная табличная алгебра бесконечных таблиц не образует подалгебру расширенной мультимножественной табличной алгебры. Полученные результаты могут быть использованы при разработке языков запросов к табличным базам данных и при разработке программного обеспечения с табличными базами данных.