реляционные СУБД и вложенные структуры данных

[sab123]

О том, как подружить реляционные СУБД и вложенные структуры данных читать здесь:

http://babkin-cep.blogspot.com/2014/12/relational-operations-on-nested-data.html

или в PDF здесь:

http://web.newsguy.com/sab123/papers/rel_nested.pdf

Comments

[juan-gandhi.livejournal.com]

The need for such currying is almost obvious, but tell me something. Is it always a bounded-depth nested record? Can we, at least in imagination, to flatten it? Of course with 3 dimensions it does not make sense to do, but theoretically.

[sab123.livejournal.com]

Sure, why not? That would be the usual relational result of a join that is equivalent to the nested record. Or it can be "un-joined" back to the "original" tables used in that join.

[juan-gandhi.livejournal.com]

Makes sense to me then.

[enternet.livejournal.com]

По-моему, это неудачная шутка. Мне лично было бы стыдно описывать азы с серьезным видом.

[sab123.livejournal.com]

Если б это были азы, оно было бы везде реализовано. А так - вещь казалось бы очевидная, но чего-то не додумываются. Наоборот, пишут, что никак нельзя додуматься.

[vit-r.livejournal.com]

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

[sab123.livejournal.com]

Это "проще" только потому, что инструмент не умеет работать со структурами и приходится подстраиваться под ограничения инструмента. Оно кое-как работает только если в структуре данные повторяютс ятолько в одном измерении. Если в структуре есть несколько измерений, то получается комбинаторный взрыв. А я говорю о том, что давайте исправим инструмент, чтобы он не был кривым, тем более что делается несложно.

[vit-r.livejournal.com]

Вообще-то для OLAP cube есть свои тулы и свой язык запросов.

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

[sab123.livejournal.com]

Это не OLAP cube. Ну, то есть можно развернуть в куб, но очень дорого и никому не нужно. Настоящий куб - он потому и есть куб, что в нем действительно есть реальные данные по каждой точке в нем, и на самом деле глубина большинства измерений небольшая. А в древесных структурах - связей между разными ветвями дерева совсем нет. Если их разворачивать в куб, то получаются сплошные повторы, и дикий размер куба. И надо не забывать, что этих записей, то есть получающихся кубов - миллионы, миллиарды.

Кстати, таблицы с сотнями столбцов - совершенно типовая вещь в реальности финансовых приложений. И настоящие protobufs в Гугеле тоже гораздо больше моих масеньких примеров.

[vit-r.livejournal.com]

В кубах данные отнюдь не всегда плотные.
А деревья тоже не большие по вложенности. Сильно вложенные деревья, да с большим количеством данных - это на outer join будет вылетать по времени выполнения.

[sab123.livejournal.com]

А вот поэтому я и рассказываю, что скажем Гугель их хранит в иерархических структурах, protobufs. Для понимания масштаба, максимальный размер одного протобуфа ограничивается мегабайтами, и иногда случается, что маловато, хотелось бы больше. У него нет никаких джойнов, без них все работает быстро. Но с другой стороны, когда приспичит с ними делать какой-нибудь альтернативный джойн - то выходит как-то не очень. А я в своей бумаге рассказываю, как и на елку влезть, и жопу не ободрать.

[izblank.livejournal.com]

В Оракле есть поддержка вложенных структур, как в виде объектов, так и таблиц.

[sab123.livejournal.com]

Интересно, надо будет почитать. А он в состоянии ими на ходу манипулировать как обычными полями - скажем, извлечь под-дерево, или сделать поиск по значению в под-дереве?

[sab123.livejournal.com]

Почитал. Вроде, не оно. У них вложенные таблицы - это всего лишь разновидность массивов простых значений:

http://docs.oracle.com/cd/B10501_01/appdev.920/a96624/05_colls.htm

[izblank.livejournal.com]

В Оракле можно определять собственные типы и строить таблицы из них, так что "простое значение" может быть структурой. Кроме того, ваша ссылка на PL/SQL, что не совсем одно и то же. Вот поищите здесь ссылки на nested tables: http://docs.oracle.com/cd/B10501_01/server.920/a96540/index.htm#N или здесь http://docs.oracle.com/cd/B10501_01/mix.920/a96625/idx-n.htm#index-NE

[sab123.livejournal.com]

Получается, что в-принципе похоже. Причем уже в 9i, то есть очень давно. Но реализовано, судя по описаниям, через join, который происходит автоматически: вложенные записи складываются в отдельную таблицу и создаются неявные поля ключей, чтобы связать их друг с другом. Этакий встроенный ORM. Почему они пишут, что оно медленнее джойнов - непонятно.

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

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