InterConnected Variables Net

InterConnected Variables Net (рус. Сеть взаимосвязанных переменных) - самоописываемый формат данных, базирующийся на сетевой модели данных.

Целью данного проекта явлется реализация библиотеки формата данных общего назначения. Данный формат данных должен удовлетворять следующим требованиям:

• Обеспечение возможности описания сложных структур данных;
• Хранение и обработка данных в оперативной памяти процесса (RAM);
• Хранение и обработка данных в файле (DBMS);
• Хранение и обработка данных в удалённом процессе (RPC);
• Обеспечение единого интерфейса для взаимодействия с данными;
• Поддержка сериализации и десериализации данных.

Модель данных

Исходя из основной требований, предъявляемых к разрабатываемому формату данных выбрана сетевая модель данных.

К достоинствам сетевой модели данных относится:

• Гибкость – сетевые модели данных могут представлять сложные отношения, например, отношения “многие-ко-многим” между данными, и позволяют гибко моделировать различные типы данных;
• Эффективность – в сетевой модели данных используются прямые ссылки на связанные сегменты, что позволяет быстро получить доступ к данным без необходимости поиска по всей базе;
• Моделирование сложных структур – сетевые модели данных очень эффективны для моделирования сложных структур данных, ввиду наличия более широких возможности описания отношений между данными.

К недостаткам сетевой модели данных относится:

• Сложность - сетевая модель данных является сложной для понимания и использования, особенно для начинающих. Разработчикам необходимо хорошо разбираться в структурах данных и специфичных операциях;
• Наличие возможности циклической связности – в сетевой модели данных могут образоваться циклические связи между объектами, которые в свою очередь могут привести к таким проблемам как бесконечные циклы или не освобождение неиспользуемых ресурсов. В следствии чего системы, использующие сетевую модель данных, нуждаются в дополнительных средствах для определения циклических связей, что увеличивает потребление ресурсов, либо дополнительного контроля со стороны пользователя данной системы, что увеличивает порог вхождения для специалиста работающего с данной системой.

Архитектура проекта

Основной принцип разрабатываемого формата данных - “Неважно где располагаются данные, главное что с ними можно взаимодействовать”. Таким образом разработчику работающему с данной библиотекой должен предоставляться публичный интерфейс, по средствам которого он взаимодействует с данными. Детали того где и как располагаются данные скрыты от разработчика, за исключением тех случаев когда разработчик самостоятельно не запросит информацию о расположении данных.

Исходя из вышеописанных условий принято решение реализовать в библиотеки 3 слоя:

1. Слой управления - слой с которым взаимодействуют пользователь и RPC-сервер
2. Слой маршрутизации - промежуточный слой соединяющий слой управления и слой реализации
3. Слой реализации - слой содержащий реализации методов для взаимодействия с данными

Система типов данных

28 типов данных разделены на 8 основных интерфейсов по принципу схожести методов взаимодействия с данными:

• Null - интерфейс отсутствия значения (отдельная реализация интерфейса отсутствует):
  • null - отсутствие значения.
• Number - числовой интерфейс:
  • bool - логический тип данных;
  • ui8 - беззнаковое число размером 8 бит (1 байт), диапазон значений 0..255;
  • si8 - число размером 8 бит (1 байт) со знаком, диапазон значений -128..127;
  • ui16 - беззнаковое число размером 16 бит (2 байта), диапазон значений 0..65 535;
  • si16 - число размером 16 бит (2 байта) со знаком, диапазон значений -32 768..32 767;
  • ui32 - беззнаковое число размером 32 бит (4 байта), диапазон значений 0..4 294 967 295;
  • si32 - число размером 32 бит (4 байта) со знаком, диапазон значений -2 147 483 648..2 147 483 647;
  • f32 - число размером 32 бит (4 байта) c плавающей точкой, диапазон значений +/- 3.4E-38..3.4E+38;
  • ui64 - беззнаковое число размером 64 бит (8 байта), диапазон значений 0..18 446 744 073 709 551 615;
  • si64 - число размером 64 бит (8 байта) со знаком, диапазон значений -9 223 372 036 854 775 808..9 223 372 036 854 775 807;
  • f64 - число размером 64 бит (8 байта) c плавающей точкой, диапазон значений +/- 1.7E-308..1.7E+308.
• BufferArray - интерфейс гомогенных числовых векторов:
  • bit_array - вектор логических типов данных;
  • ui8_array - вектор беззнаковых чисел размером 8 бит (1 байт);
  • si8_array - вектор чисел размером 8 бит (1 байт) со знаком;
  • ui16_array - вектор беззнаковых чисел размером 16 бит (2 байта);
  • si16_array - вектор чисел размером 16 бит (2 байта) со знаком;
  • ui32_array - вектор беззнаковых чисел размером 32 бит (4 байта);
  • si32_array - вектор чисел размером 32 бит (4 байта) со знаком;
  • f32_array - вектор чисел размером 32 бит (4 байта) c плавающей точкой;
  • ui64_array - вектор беззнаковых чисел размером 64 бит (8 байта);
  • si64_array - вектор чисел размером 64 бит (8 байта) со знаком;
  • f64_array - вектор чисел размером 64 бит (8 байта) c плавающей точкой.
• Array - интерфейс гетерогенных векторов:
  • array - гетерогенный вектор.
• List - интерфейс гетерогенных связных списков:
  • list - гетерогенный двусвязный список.
• Map - интерфейс гетерогенных ассоциативных массивов с уникальным ключом:
  • map - гетерогенный ассоциативный массив с уникальным ключом.
• MultiMap - интерфейс гетерогенных ассоциативных массивов с не уникальным ключом:
  • multi_map - гетерогенный ассоциативный массив с не уникальным ключом.
• Contract - интерфейс контрактов:
  • contract - контракт.

Определение типов данных и их свойств находится в заголовочном файле type_system.hxx.

Простые структуры данных

Простыми типами данные являются null, Number и BufferArray. Ключевой особенностью данных типов данных является то что они могут сравниваться между собой, за счёт чего могут выступать в качестве ключа ассоциативных гетерогенных контейнеров: map, multimap, contract.

Number - числовые типы данных

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

• Является ли значение целочисленным или числом с плавящей точкой;
• Если значение является целочисленным, может ли оно быть отрицательным. Для краткости названия свойств числовых типов сокращены до одной буквы, таким образом эти буквы означают:
• u (unsigned) – беззнаковое;
• s (signed) – со знаком;
• i (integer) – целочисленное;
• f (floating point) – число с плавающей точкой. После определения свойств числа указывается его размер в битах 8, 16, 32, 64. Исключением является логический тип данных.

BufferArray - гомогенные числовые вектора

На основе вышеуказанных числовых типов определяются типы гомогенных векторов, наименование типов которых составляются из наименования числового типа данных, соотнесённых с ними и суффикса array, записываемого после нижнего подчёркивания. Они могут хранить переменное количество числовых значений, удовлетворяющих свойствам соотнесённого с ними числового типа. Помимо гомогенных векторов соотносящихся с числовыми типами данных так же имеется гомогенный вектор, базирующийся на логическом типе данных bool именуемый bit_array. Данный тип позволяет оптимально хранить массив из логических типов за счёт побитового расположения в памяти.

Временная и пространственная сложности:

• Произвольный доступ к элементам: O(1), O(log8(n)) - в реализации СУБД в качестве векторов выступает дерево произвольного доступа, в следствии чего асимптотическая сложность произвольного доступа описывается функцией O(log8(n)), данное решение принято в угоду снижения фрагментации данных в файле
• Доступ к первому и последнему элементу: O(1);
• Поиск - O(n);
• Вставка - O(n);
• Удаление - O(n);
• Сложность по памяти - O(n).

Гетерогенные структуры данных

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

Array - гетерогенный вектор

Интерфейс методов аналогичен BufferArray, за исключением того, что в качестве данных контейнера выступают элементы разных типов.

Временная и пространственная сложности:

• Произвольный доступ к элементам: O(1), O(log8(n)) - в реализации СУБД в качестве векторов выступает дерево произвольного доступа, в следствии чего асимптотическая сложность произвольного доступа описывается функцией O(log8(n)), данное решение принято в угоду снижения фрагментации данных в файле;
• Доступ к первому и последнему элементу: O(1);
• Поиск - O(n);
• Вставка - O(n);
• Удаление - O(n);
• Сложность по памяти - O(n).

List - гетерогенный двусвязный список

Интерфейс взаимодействия аналогичен std::list из стандартной библиотеки C++

Временная и пространственная сложности:

• Произвольный доступ к элементам: O(n);
• Доступ к первому и последнему элементу: O(1);
• Поиск - O(n);
• Вставка - O(1);
• Удаление - O(1);
• Сложность по памяти - O(n).

Map - гетерогенный ассоциативный массив с уникальным ключом

В качестве элементов выступают пары ключ значение, в качестве ключа могут выступать только простые структуры данных: Null, Number, BufferArray, в качестве занчение любой тип данных из системы типов, за исключением тех случаев когда пара ключ-значение индексирована в контейнере контракт, в данном случае, в зависимости от типа индекса контракта, к значению пары могут быть предъявлены дополнительные требования. Данный ассоциативный массив не может хранить пары с ключами эквивалентными друг другу.

Временная и пространственная сложности:

• Произвольный доступ к элементам: O(log(n));
• Доступ к первому и последнему элементу: O(log(n));
• Поиск - O(log(n));
• Вставка - O(log(n));
• Удаление - O(log(n));
• Сложность по памяти - O(n).

MultiMap - гетерогенный ассоциативный массив с не уникальным ключом

В качестве элементов выступают пары ключ значение, в качестве ключа могут выступать только простые структуры данных: Null, Number, BufferArray, в качестве занчение любой тип данных из системы типов, за исключением тех случаев когда пара ключ-значение индексирована в контейнере контракт, в данном случае, в зависимости от типа индекса контракта, к значению пары могут быть предъявлены дополнительные требования. Данный ассоциативный массив может хранить пары с ключами эквивалентными друг другу.

Временная и пространственная сложности:

• Произвольный доступ к элементам: O(log(n));
• Доступ к первому и последнему элементу: O(log(n));
• Поиск - O(log(n));
• Вставка - O(log(n));
• Удаление - O(log(n));
• Сложность по памяти - O(n).

Contract - контракты

Контракты - тип данных выполняющий 2 основные задачи: валидация данных и поиск данных.

Валидация осуществляется с помощью правила ассоциации содержащегося в контракте - условие которое автоматически проверяется при ассоциации Map или MultiMap с контрактом, а так же автоматически перепроверяются при изменении уже ассоциированных с контрактом Map или MultiMap.

Поиск осуществляется с помощью индексов содержащихся в контракте.

Статус проекта

На текущий момент проект находится на стадии разработки.