Roman MejtesmaytonЯ добавлю чего куб не любит.
3. Поиск по неполному набору атрибутов. Вместо поиска точки мы будем искать множество фактов на гипер-прямой или гиперплоскости и т д. O(1) превращается в линейный или полиномиальный.
Одна из базовых основ кубов, это получение среза.... а не получения конкретной точки (Obs)
Вы говорите об OLAP. Я говорю о другой структуре данных.

Dima Tmayton3. Поиск по неполному набору атрибутов. Вместо поиска точки мы будем искать множество фактов на гипер-прямой или гиперплоскости и т д. O(1) превращается в линейный или полиномиальный.
Если набор атрибутов всегда полный, то я уже выше предлагал рассматривать биткарту как многомерный массив бит 21452572

При большом размере биткарты возможно фильтр Блума как-то подойдет.
По первому пункту - да. 100%.

По фильтрам. Почти да. При условии что мы делаем частичное кеширование. Доступ к БД по прежнему нужен.

Я не против Блума но сначала хочу исчерпать возможности сваей первой постановки.

Dima Tmayton, почитай про карту Карно.
https://ru.wikipedia.org/wiki/Карта_Карно Куб Карно́ — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок[1]. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определённую плоскую развертку n-мерного булева куба.
Карно - это графическое представление булевой функции. Сам же метод карно требует участия человека эксперта который эту минимизацию делает вручную.

Альтернатива это Квайн который автоматизирован но не факт что построит компактную функцию. Собственно здесь можно поставить вопрос о принципиальной возможности что то минимизировать.

Dima TmaytonЦифры. Для куба с расходом памяти в 2Gbyte. (~17 179 869 184 boolean элемента) ...
2 Гб много для оперативки, но если использовать мапинг файла в память, то можно 2 Тб легко задействовать. Дисковая память недорогая, для этой задачи хватит HDD.

Большие разреженные файлы из ноликов ОС умеют создавать, т.е. наполнение будет относительно быстрое. При использовании отображаться в память файл будет постранично, т.е. оперативки много не потребуется.
На файловой системе (random access) надо подумать об умной буферизации. При начальной инициализации.

ViPRoshVosttКонкретная задача, пусть хотя бы для примера, сильно бы упростила бы поиск решения.
УГУ.
Я попробую сделать учебный пример. Но вы наверное не в курсе моей традиции создавать пятничные топики мозгового штурма. Я делюсь мыслями а не бизнес постановкой.

Вобщем не ждите от меня ТЗ. Фантазируйте. Дополняйте.

Dima Tmaytonпропущено...

На файловой системе (random access) надо подумать об умной буферизации. При начальной инициализации.
Суть этой идеи в том что об этом будет думать ОС, т.е. не надо заморачиваться вопросом, который ты задал.
Не согласен.

Dima Tmaytonпропущено...

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

Вернемся к диску потом. Позже.

hVosttТогда надо в область нейросететей, искусственного интеллекта, квантовых кубитов и т.п. Всё равно это невозможно проверить и ни в чём убедиться. Зато фантазировать -- сколько угодно :)
Ну... на правах топик-стартера я всё-таки предлагаю ограничиться темой первого поста.
Но если вы имеете что сказать по ИИ или нейросетям - прошу создавайте новую ветку.
Я возможно подключусь.

По поводу фильтра Блума. Я привожу некий субъективный сравнительный анализ куба и фильтра Блума
в виде таблички. По каждому пункту я готов дать свою аргументацию. Некоторые пункты которые
я отметил звездочной (*) требуют детализации и я ее отпишу чуть позже по мере времени.

Комментарии.

(*) Memory consuming MBHC определяется формулой. . Формулой произведения кардинальностей всех измерений кортежей.
Плюс накладные на использование справочников измерений.

Допустим у нас есть табличка фактов с 4 колонками на 80000 строк. Несмотря на большой объем
сегмента данных - раздельные величины кардинальностей равны 8, 5, 3, 10. Поля имеют различные
типы данных. Строка. Дата. Число. И еще одно число. Но тип нам не особо интересен. Мы создаём 4 справочника.
для отображения строк дат и уникальных чисел на ограниченный диапазон индексов (желательно начиная с нуля).
0..7, 0..4 e.t.c. Конструем куб с объемом на 8*5*3*10 = 1200 бит или 150 байт. Это и есть наш memory consuming
и некое сериализованное в памяти состояние 4 справочников размер которых я сейчас посчитать не могу
но вы можете прикинуть сами исходя из средних метрик для продуктовых баз. Что там? Имена? Коды товаров?
Придумайте сами.

(**) Поддержка интерфейа Итерации в многомерном булевом кубе возможна.

В самом начале топика я писал что невозможно. Или сложно.

Вобщем смотрите. Основное назначение куба - хранение и извлечение фактов в режиме жесткого OLTP.
Тоесть мы предполагаем точечные запросы вида



Какой смысл делать переборные алгоритмы в таких условиях? Я не знаю. Может просто COUNT() всех фактов.

Придумайте сами. Временная сложность будет линейна если мы скипаем field1 и будет расти если отбрасывать
другие поисковые ограничители. Словом поиск по полному совпадению всех ключей кортежа - предпочтителен.
Итерация - возможна но куб теряет смысл. Тогда лучше искать в БД.

(***) Поддержка интервальных запросов.

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

Например выбрать все факты где средне-годовой доход в диапазоне от 50 000 $ до 950 000 $.
Разумеется оригинальный запрос должен будет быть трансформирован через справочних
классов доходов в некое целочисленное значение индекса. Здесь для достижения эффекта
мы должны физически организовать куб таким образом чтобы факты этого диапазона лежали рядом.

Далее (****) Расширение сегмента данных для фильтра Блума.

Я не буду здесь долго описывать теорию. Можете почитать Вики. Фильтр Блума принципиально не расширяется.
Его можно пересоздать заново и используя оригинальную БД прогрузить весь amount фактов в новый сегмент.
Добавление новых фактов - возможно но приводит к потере избирательности.

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

Здесь же. По поводу MBHC и расширения в одном измерении. Думаю возможно. Если в примере CUBE2
мы аллоцируем чуть больше памяти (с запасом) и порежем куб на гиперплоскости которые соответствуют средним годовым доходам. И при этом аллоцированная сырая память операционной системы заполнена кубом на 80% то нам ничто не мешает
отформатировать ее продолжение под следующую гиперплоскость и считать что куб растянулся.

Почему мы не аллоцировали все сразу? Предлагаю подумать и о возможном расширении других измерений
в условиях когда мы не знаем как будут расти справочные данные. Чисто технически - это просто движение
битов в биткарте (с учотом padding) и все прочее. Дело нудное и скушное и я сейчас просто не хочу
об этом думать но утверждаю что технически - возможно. Если сильно надо - то растянем.

Далее (*****) Возможность сжатия.

Это больной вопрос. Можно сказать слабое место алгоритма. Я подведу под это практическую
базу. Мне только нужна учебная схема типа Борей и терпение чтобы оценить как лягут
таблички в куб. Сам куб я не буду строить пока. Для оценки мне достаточно к примеру
прогрузить тот-де Борей в SQLite и посчитать его кардинальности.

Чтобы не флудить словами я ввожу функцию


и буду на нее ссылаться как на основную метрику КПД куба в части памяти.

Ну и для простоты еще число строк



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