Portable Network Data Model

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

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

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

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

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

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

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

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

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

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 - контракты

Контракты могут применяться к ассоциативным контейнерам Map и MultiMap. Контракты имеют следующие параметры:

• Правила отношения (linking_rules) - условия применяемые к ассоциативным контейнерам относящимся к контракту, при нарушении данных условий ассоциативный контейнер исключается из контракта;
• Генераторы полей (field_generators) - поля вычисляемые при обращении к ассоциативному контейнеру относящемуся к контракту;
• Поля времени отношения (linking_time_fields) - вычисляемые при связывании ассоциативного контейнера с контрактом поля и удаляемые при исключении ассоциативного контейнера из контракта;
• Поисковые индексы (search_indexes) - индексы индексирующие ассоциативные массивы по одной или нескольким парам ключ-значение;
• Иерархия наследования (inheritance_hierarchy):
  • Дочерние контракты (child_contracts) - дочерние контракты, наследующие все параметры текущего контракта;
  • Родительские контракты (parent_contracts) - родительские контракты, от которых текущий контракт наследует все параметры.

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

Отличительные особенности контрактов:

• Поиск ассоциативных массивов через контракты, может осуществляться только средствами поисковых индексов, если контракт не содержит поисковых индексов, то через контракт невозможно найти ассоциативный массив относящийся к данному контракту. В случае если контракт не содержит поисковых индексов, контракт выступает только в качестве инструмента валидации или генерации полей, поскольку из ассоциативного массива можно узнать, к каким контрактам он относится, а сгенерированные поля остаются в ассоциативном массиве до тех пор, пока не нарушаются правила отношения или ассоциативный массив вручную не исключается из контракта;
• В отличии от таблицы в реляционных моделях данных, в контрактах, отсутствует строгие правила применяемые к парам ассоциативных массивов и их типам данных. Ограничения задаются через правила отношения, в которых могут быть не прописаны строгие требования к типу данных пары ассоциативного массива. Так же к контрактам могут относиться ассоциативные массивы с большим колличеством пар, если чёткое их колличество не определено в правилах отношений;
• Контракты могут входить в иерархию наследования, при вхождении в иерархию контракты наследуют правила отношения вышестоящих контрактов и ассоциативные массивы связывающиеся с такими контрактами должен удовлетворять так же и наследуемым правилам отношения. В данном случае, при связывании нового ассоциативного массива с одним из контрактов находящимся в иерархии наследования, происходит автоматическа проверка правил отношений всех остальных контрактов находящихся ниже в иерархии наследования, и если связанный с текущим контрактом ассоциативный массив им соответствует, он так же связывается с нижестоящими контрактами. Поскольку текущий контракт наследует правила отношений всех вышестоящих контрактов, то связанный с текущим контрактом ассоциативный массив связывается и со всеми вшестоящими контрактами, в которых в свою очеред происходит проверка всех нижестоящих, за исключением уже связанных. Таким образом происходит каскадное связывание иерархии контрактов с ассоциативным массивом;
• При внесении изменений в ассоциативный массив связанного с одним и более контрактом автоматически происходит проверка всех правил отношений связанных с ним контрактов, в случае нарушения данных правил, происходит отсоединение ассоциативного массива от контрактов, с удалением полей времени отношения и отключение генераторов полей от ассоциативного массива.

Типы индексов контрактов:

• tree - сбалансированное дерево поиска (значение является простой структурой данных);
• link_tree - сбалансированное дерево для поиска по ссылкам на элементы (отсутствуют требования к значениям);
• dictionary_link_tree - сбалансированное дерево для по ссылкам на элементы из словаря (значение или эквивалентное значение присутствует в словаре);
• hash - хэш-таблица (значение является простой структурой данных);
• full_text_tree - сбалансированное дерево для полнотекстового поиска (значение относится к интерфейсу BufferArray).

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

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

Статус реализации по публичному интерфейсу библиотеки:

• cdfc::Storage - RAM требуется сделать; DBMS требуется сделать; RPC требуется сделать;
  • cdfc::RAMStorage - требуется сделать;
  • cdfc::DBMSStorage - требуется сделать;
  • cdfc::RemoteStorage (RPC) - требуется сделать;
• cdfc::Variable - RAM в процессе; DBMS требуется сделать; RPC требуется сделать;
  • cdfc::Number - RAM реализовано, тестируется; DBMS требуется сделать; RPC требуется сделать;
  • cdfc::BufferArray - RAM реализовано, тестируется; DBMS требуется сделать; RPC требуется сделать;
  • cdfc::Array - RAM реализовано, тестируется; DBMS требуется сделать; RPC требуется сделать;
  • cdfc::List - RAM реализовано, тестируется; DBMS требуется сделать; RPC требуется сделать;
  • cdfc::Map - RAM требуется сделать; DBMS требуется сделать; RPC требуется сделать;
  • cdfc::MultiMap - RAM требуется сделать; DBMS требуется сделать; RPC требуется сделать;
  • cdfc::Contrcat - RAM требуется сделать; DBMS требуется сделать; RPC требуется сделать;
• cdfc::NumberReference - RAM реализовано, тестируется; DBMS требуется сделать; RPC требуется сделать;
• cdfc::KeyValue - RAM требуется сделать; DBMS требуется сделать; RPC требуется сделать;
• cdfc::IndexedVariable - RAM требуется сделать; DBMS требуется сделать; RPC требуется сделать;