Мета-теория связей 0.0.3 / Хабр

В прошлое первое апреля, как вы могли догадаться, мы пошутили. Пора это исправить, и теперь $100\%$ всё серьёзно.

TL;DR (too long; didn't read)

В этой статье много букв, но её можно записать всего 4-мя символами теории множеств:

$R \to R^2$

Всё остальное следствие из них.

Обзор

Эта статья в первую очередь ориентирована на программистов и математиков, но мы постарались сделать её доступной для всех, кому интересны представленные идеи. Мы убеждены, что обсуждаемые здесь концепции могут послужить источником вдохновения для самых разных научных дисциплин.

Нашей целью было создать самодостаточный текст, который проведёт вас через каждую тему в ясном, логическом порядке. В статье вы найдёте ссылки на Википедию для тех, кто захочет подробнее изучить конкретные термины или понятия — но это совершенно необязательно. Текст рассчитан на последовательное чтение от начала до конца.

Каждый символ и формула объяснены по отдельности, с краткими определениями там, где это необходимо. Мы также добавили иллюстрации для наглядного представления ключевых идей. Если что-то останется непонятным, пожалуйста, сообщите нам, чтобы мы могли это улучшить.

Сравнение теорий

Для быстрого погружения мы начнём со сравнения математических основ двух самых популярных моделей данных: графовой и реляционной, c ассоциативной моделью данных, концепцию которой ещё в прошлом веке представил англичанин Саймон Вильямс.

В ходе нашего исследования мы обнаружили, что традиционные теории иногда оказывались чрезмерно сложными или избыточными, а иногда накладывали слишком много искусственных ограничений.

Этот общий недостаток гибкости, адаптивности и универсальности побудил нас искать более простую, но всеобъемлющую информационную теорию и модель хранения данных, которую будущий искусственный интеллект сможет легко понять и эффективно использовать. По пути мы черпали вдохновение из работы нашей собственной ассоциативной памяти и ассоциативных мыслительных процессов. Саймон Вильямс также отмечал, что ассоциативная модель «воспринимает информацию так же, как это делает мозг: в виде вещей и ассоциаций между ними» (“The associative model sees information in the same way as the brain does: as things and associations between them.”) [5]. Однако, мы можем пойти дальше, обозначив каждую вещь — ассоциацией или связью, и задать для этого прочный формальный фундамент, о чём и будет эта статья.

Реляционная алгебра

Реляционная алгебра и реляционная модель основаны на понятиях отношения и n-кортежей.

Отношение определяется как множество n-кортежей:

$R \subseteq S_1 \times S_2 \times \dots \times S_n.$ [1]

Рис. 1. Таблица описывается отношением , которое представляется множеством строк , принадлежащих декартову произведению . — **Рис. 1.** Таблица описывается отношением , которое представляется множеством строк , принадлежащих декартову произведению $S_1 \times S_2 \times \dots \times S_n$ .

Где:

Символ обозначает отношение (таблицу);
Символ обозначает, что левая часть выражения является подмножеством правой части;
Символ обозначает декартово произведение двух множеств;
Выражение обозначает домен, то есть множество всех возможных значений, которые может содержать каждая ячейка в столбце.

Строки, или элементы отношения , представлены в виде n-кортежей.

Данные в реляционной модели группируются в отношения. Используя n-кортежи в этой модели, можно точно представить любую возможную структуру данных — если бы мы действительно когда-нибудь использовали для этого n-кортежи. Но нужны ли вообще n-кортежи? Например, каждый n-кортеж можно представить в виде вложенных упорядоченных пар, что предполагает, что упорядоченных пар может быть достаточно для представления любых данных. Более того, нечасто встретишь, что значения столбцов в таблицах представляются n-кортежами (хотя, например, число можно разложить на n-кортеж битов). В некоторых SQL базах данных даже запрещено использовать более 32 столбцов в таблице (и, соответственно, в её n-кортеже). Таким образом, фактическое значение n обычно меньше 32. Поэтому в этих случаях нет настоящих n-кортежей — даже в современных реляционных базах данных.

Рис. 2. Сравнение реляционной модели и ассоциативной модели данных (изначальная модель, предложенная Саймоном Вильямсом, была упрощена нами дважды) [3] [5]. Иными словами, для представления всех данных в реляционной моделитребуется множество таблиц — по одной для каждого типа данных — тогда как в ассоциативной модели оказалось, что сначала было достаточно двух таблиц (items и links), а затем и вовсе одной таблицы триплетов-связей или дуплетов-связей. — **Рис. 2.** Сравнение реляционной модели и ассоциативной модели данных (изначальная модель, предложенная Саймоном Вильямсом, была упрощена нами дважды) [3] [5]. Иными словами, для представления всех данных в реляционной моделитребуется множество таблиц — по одной для каждого типа данных — тогда как в ассоциативной модели оказалось, что сначала было достаточно двух таблиц (`items` и `links`), а затем и вовсе одной таблицы триплетов-связей или дуплетов-связей.

Ориентированный граф

Ориентированные графы — и графы в целом — основаны на понятиях вершин и рёбер (2-кортежей).

Ориентированный граф определяется так:

$\mathbf{G = (V, E), \quad E \subseteq V \times V.}$ [2]

Где:

— это множество, элементы которого называются вершинами, узлами или точками;
— это множество упорядоченных пар (2-кортежей) вершин, называемых дугами, направленными рёбрами (иногда просто рёбрами), стрелками или направленными отрезками.

В модели ориентированного графа данные представлены двумя отдельными множествами: узлами и рёбрами. Эту модель можно использовать для представления почти всех структур данных, кроме, вероятно, последовательностей (n-кортежей). Иногда можно встретить, что используются цепочки вершин как представления последовательностей. И хотя этот метод работает, он гарантированно приводит к дупликации данных, а дедупликация в этом случае будет осложнена или недоступна. Ещё, вероятно, последовательности в графах можно представить, используя разложение последовательности на вложенные множества, но, на наш взгляд, это непрактичный способ. Вероятно, не одни мы так считаем, что может объяснить, почему мы не встретили примеров использования такого метода другими людьми.

Рис. 3. Сравнение теории графов и теории связей. Вершина эквивалентна замкнутой на себя связи — связи, которая в себе начинается и в себе заканчивается. Направленное ребро отображается в направленную связь-дуплет, а ненаправленное ребро — в пару направленных связей-дуплетов в обоих противоположных направлениях. Иными словами, если в теории графов требуется два типа сущностей — вершины и рёбра, то в теории связей достаточно только связей (больше всего похожих на рёбра). — **Рис. 3.** Сравнение теории графов и теории связей. Вершина эквивалентна замкнутой на себя связи — связи, которая в себе начинается и в себе заканчивается. Направленное ребро отображается в направленную связь-дуплет, а ненаправленное ребро — в пару направленных связей-дуплетов в обоих противоположных направлениях. Иными словами, если в теории графов требуется два типа сущностей — вершины и рёбра, то в теории связей достаточно только связей (больше всего похожих на рёбра).

Теория связей

Теория связей основана на понятии связи.

В проекции теории связей в теорию множеств связь определяется как n-кортеж ссылок на связи, у которой есть собственная ссылка, используя которую другие связи могут ссылаться на неё.

Стоит отметить, что отдельное понятие ссылки здесь требуется только потому, что рекурсивные определения недоступны в теории множеств. Сама же теория связей может описать себя без необходимости отдельного термина ссылки — то есть ссылка это частный случай связи.

Дуплеты

Связь-дуплет представлена дуплетом (2-кортежем или упорядоченной парой) ссылок на связи. У связи-дуплета есть собственная ссылка.

R = { 1 , 2 }

R × R = {
  (1, 1),
  (1, 2),
  (2, 1),
  (2, 2),
}

Где:

— это множество ссылок (от английского слова «References» — ссылки).

В этом примере в множестве всего ссылки на связи, а именно и . Иными словами, в сети связей, построенной на таком множестве ссылок, может быть только связи.

Чтобы получить все возможные значения связи, используется декартово произведение на само себя, то есть $R \times R$ .

Рис. 4. Матрица, представляющая декартово произведение множества на само себя. Здесь мы видим, что у связей с двумя ссылками на связи может быть всего 4 возможных значения. — **Рис. 4.** Матрица, представляющая декартово произведение множества $\set{1, 2}$ на само себя. Здесь мы видим, что у связей с двумя ссылками на связи может быть всего 4 возможных значения.

Рис. 5. Таблица строк, содержащих все возможные варианты значений связей для сети с двумя связями; эти варианты получаются при помощи декартова произведения на само себя. — **Рис. 5.** Таблица строк, содержащих все возможные варианты значений связей для сети с двумя связями; эти варианты получаются при помощи декартова произведения $\set{1, 2}$ на само себя.

Сеть связей-дуплетов определяется как:

$\mathbf{N^2: R \to R \times R}$

Где:

обозначает отображение (функцию);
обозначает функцию, определяющую сеть связей-дуплетов ( от англ. “Network”);
обозначает множество ссылок на связи ( от англ. “References”).

Пример в математической нотации:

$1 \to (1, 1)$
$2 \to (2, 2)$
$\mathbf{3 \to (1, 2)}$

Пример в нотации связей:

(1: 1 1)
(2: 2 2)
(3: 1 2)

Рис. 6. Сеть из трёх связей. Представление сети дуплетов похоже на граф, но такую визуализацию мы называем сетью связей. Первая и вторая связи имеют похожую структуру — обе начинаются в себе и заканчиваются в себе. Отсюда получается, что вместо традиционного представления вершины в виде точки в теории графов мы получаем графическое представление замкнутой самоссылочной стрелки, которое похоже на символ бесконечности. — **Рис. 6. Сеть из трёх связей.** Представление сети дуплетов похоже на граф, но такую визуализацию мы называем сетью связей. Первая и вторая связи имеют похожую структуру — обе начинаются в себе и заканчиваются в себе. Отсюда получается, что вместо традиционного представления вершины в виде точки в теории графов мы получаем графическое представление замкнутой самоссылочной стрелки, которое похоже на символ бесконечности.

Рис. 7. Это графическое представление декартова произведения в виде матрицы, которое отображает все возможные значения связей. Связи, определяющие конкретную сеть, выделены оранжевым цветом. Иными словами, из возможных вариантов значений связи выбраны всего связи, что соответствует размеру множества . — **Рис. 7.** Это графическое представление декартова произведения в виде матрицы, которое отображает все возможные значения связей. Связи, определяющие конкретную сеть, выделены оранжевым цветом. Иными словами, из возможных вариантов значений связи выбраны всего связи, что соответствует размеру множества .

Сеть связей-дуплетов может представлять любую структуру данных.

Например, связи-дуплеты могут:

связывать объект с его свойствами;
связывать два дуплета вместе, чего определение теории графов не позволяет;
представлять любую последовательность (n-кортеж) в виде дерева, построенного из вложенных упорядоченных пар;
описать предложение на естественном языке, например, по модели подлежащее-сказуемое.

Благодаря этому и другим фактам мы убеждены, что связи-дуплеты могут представлять любую возможную структуру данных.

Триплеты

Связь-триплет представлена триплетом (3-кортежем) ссылок на связи.

R = { 1 , 2 }

R × R = {
  (1, 1),
  (1, 2),
  (2, 1),
  (2, 2),
}

R × R × R = {
  (1, 1, 1),
  (1, 1, 2),
  (1, 2, 1),
  (1, 2, 2),
  (2, 1, 1),
  (2, 1, 2),
  (2, 2, 1),
  (2, 2, 2),
}

Рис. 8. Трёхмерный куб-матрица, который представляет все возможные значения связи-триплета. Такой куб получается рекурсивным декартовым произведением множества на само себя, то есть — **Рис. 8.** Трёхмерный куб-матрица, который представляет все возможные значения связи-триплета. Такой куб получается рекурсивным декартовым произведением множества $\set{1, 2}$ на само себя, то есть $\set{ 1, 2 } \times \set{ 1, 2 } \times \set{ 1, 2 }.$

Рис. 9. Таблица всех возможных вариантов значений связи-триплета, получаемая рекурсивным декартовым произведением множества на само себя, то есть Примечание: первая ссылка может интерпретироваться как начало, вторая как тип, а третья как конец; пользователь сам определяет, как интерпретировать компоненты кортежа ссылок в соответствии с решаемой задачей. — **Рис. 9.** Таблица всех возможных вариантов значений связи-триплета, получаемая рекурсивным декартовым произведением множества $\set{ 1, 2 }$ на само себя, то есть $\set{ 1, 2 } \times \set{ 1, 2 } \times \set{ 1, 2 }.$ **Примечание:** первая ссылка может интерпретироваться как начало, вторая как тип, а третья как конец; пользователь сам определяет, как интерпретировать компоненты кортежа ссылок в соответствии с решаемой задачей.

Сеть связей-триплетов определяется как:

$\mathbf{N^3 : R \to R \times R \times R}$

Где:

обозначает функцию, определяющую сеть связей-триплетов ( от англ. “Network”);
обозначает множество ссылок на связи ( от англ. “References”).

Пример функции, задающей конкретную сеть триплетов в математической нотации:

$1 \to (1, 1, 1)$
$2 \to (2, 2, 2)$
$3 \to (3, 3, 3)$
$\mathbf{4 \to (1, 2, 3)}$

И в нотации связей:

(1: 1 1 1)
(2: 2 2 2)
(3: 3 3 3)
(4: 1 2 3)

Рис. 10. Ассоциативная сеть триплетов, представленная в виде цветного ориентированного графа. В этой ассоциативной сети 4 триплета, соответствующие функции, заданной выше. Узлы соответствуют связям, а цвета рёбер соответствуют ссылкам на связи в соответствии с Рис. 9 (красный — from, синий — type, зелёный — to). — **Рис. 10.** Ассоциативная сеть триплетов, представленная в виде цветного ориентированного графа. В этой ассоциативной сети 4 триплета, соответствующие функции, заданной выше. Узлы соответствуют связям, а цвета рёбер соответствуют ссылкам на связи в соответствии с Рис. 9 (красный — from, синий — type, зелёный — to).

Связи-триплеты могут делать то же, что и связи-дуплеты. Поскольку в триплетах есть дополнительная ссылка, её можно, например, использовать для указания типа связи.

Например, связи-триплеты могут:

связывать объект, его свойство и значение;
связывать две связи вместе определённым отношением;
описать предложение на естественном языке, например, по модели подлежащее-глагол-дополнение.

Последовательности

Последовательность ссылок на связи — также известная как n-кортеж — является общим случаем.

В общем виде сеть связей определяется как:

$\mathbf{N^n: R \rightarrow \underbrace{ R \times R \times \ldots \times R}_{n}}$

Где:

обозначает функцию, определяющую сеть связей размерности ( от англ. “Network”);
обозначает множество ссылок на связи ( от англ. “References”).

Пример в математической нотации:

$\mathbf{4 → (1, 2, 3, 2, 1)}$

И в нотации связей:

(1: 1)
(2: 2 2)
(3: 3 3 3)
(4: 1 2 3 2 1)

В этом примере используются n-кортежи переменной длины в качестве значений связей.

Последовательности (кортежи) по сути эквивалентны по выразительной силе реляционной модели — факт, который ещё предстоит доказать в рамках разрабатываемой теории. Однако, когда мы заметили, что связей-дуплетов и связей-триплетов достаточно для представления последовательностей любого размера, появилось предположение об отсутствии необходимости использовать последовательности напрямую, поскольку они представимы связями-дуплетами.

Итоги сравнения

Реляционная модель данных может представить всё — включая ассоциативную модель, но для этого необходимо ввести отношение порядка, которое обычно принимает форму отдельного столбца ID. Это связано с тем, что реляционная модель данных основана на понятии множества, а не последовательности. В противоположность этому, графовая модель отлично представляет отношения, но менее эффективна в представлении уникальных дедуплицированных последовательностей.

Хотя сама реляционная модель не требует разделения данных на несколько таблиц, традиционные реализации обычно принимают такой подход с фиксированными схемами, что приводит к фрагментации связанных данных и усложняет восстановление заложенных связей. В противоположность этому, ассоциативная модель использует единое хранилище связей, которое достигает максимально возможной степени нормализации. Такая архитектура упрощает взаимно-однозначное отображение предметной области, тем самым облегчая быстрые изменения требований [4].

Ассоциативная модель может легко представить n-кортежи неограниченной длины, используя кортежи с . Она столь же хороша, как теория графов, в своей способности представлять ассоциации, и столь же мощна, как реляционная модель, способная полностью представить любую таблицу SQL. Кроме того, ассоциативная модель может представлять строгие последовательности, позволяя инкапсулировать любую последовательность в единственную уникальную связь, что полезно для дедупликации.

В реляционной модели достаточно всего одного отношения, чтобы воспроизвести поведение ассоциативной модели, и обычно при этом нужно не более 2–3 столбцов помимо явного ID или встроенного ID строки. Сам ID требуется в реляционной модели, поскольку она построена на понятии множества; в противоположность этому теория связей построена на понятии последовательности, поэтому явный ID не требуется (и может быть добавлен опционально, если пользователь действительно в нём нуждается).

По определению графовая модель не может напрямую создать ребро между рёбрами. Поэтому ей потребуется либо переопределение, либо расширение с помощью однозначного метода хранения уникальных дедуплицированных последовательностей. Хотя последовательности можно хранить в виде вложенных множеств внутри графовой модели, этот подход не популярен. Несмотря на то что графовая модель наиболее близка к связям-дуплетам, она всё же отличается по определению.

Использование ассоциативной модели означает, что больше не нужно выбирать между SQL и NoSQL базами данных; вместо этого ассоциативное хранилище данных может представить всё самым простым возможным способом, при этом данные всегда находятся в наиболее близкой к оригиналу форме (обычно это нормализованная форма, но денормализация тоже возможна при необходимости).

Продолжение статьи в процессе оформления, пожалуйста добавьте статью в закладки, чтобы дочитать позднее... Если у вас хорошо с английским, можно посмотреть предыдущую версию статьи: habr.com/ru/articles/895896

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

50%Да2

25%Нет1

25%Мне нужно подумать1

0%Ещё не прочитал статью0

0%Жду пока статья будет готова к прочтению0

0%Расскажу о своей идее в комментариях0

Проголосовали 4 пользователя. Воздержался 1 пользователь.