Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Category:

DAG database

Есть функция multiColor :: [Key] -> [Color], которую надо мемоизировать, используя дисковое хранилище. Ключей оч много и они не помещаются в память.
data Color = Red | Black

keyValue :: Key -> Value
keyChildren :: Key -> [Key]
valueColor :: (Key, Value) -> Color

keyColor :: Key -> Color
keyColor x = valueColor (x, keyValue x)

treeColor :: Key -> Color
treeColor x | keyColor x == Red = Red
treeColor x | any (\x -> treeColor x == Red) $ keyChildren x = Red
treeColor _ = Black

multiColor :: [Key] -> [Color]
multiColor = map treeColor
Функции keyValue, keyChildren и valueColor вычислительно дорогие. А valueColor ещё и апдейтится (я дописываю код). Т.е. необходимо иметь возможность перевычислять только цвета, используя мемоизированные ключи и значения.

Есть базовое решение: мемоизировать keyValue, keyChildren, keyColor и treeColor таблицами, а при изменении реализации valueColor очищать таблицы keyColor и treeColor.

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

Наивная схема с таблицей keyClosure, в которой по ключу находится блоб с его транзитивным замыканием, позволяет при изменении реализации valueColor перевычислять treeColor за одно обращение к физическому устройству, но неимоверно радувает хранимый объем данных.

Мое гугл-фу пока нашло только http://en.wikipedia.org/wiki/Triplestore и http://www.w3.org/TR/sparql11-overview/

Но меня скорее интересуют алгоритмы, нежели системы. Есть ли алгоритмы группировки узлов DAG для повышения локальности в физическом хранилище. Хотя от систем (DBMS) тоже не откажусь.
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments