Как мне реализовать постоянство объектов, не включая загрузку в память?

Question

У меня есть объект Graph (это на Perl), для которого я вычисляю его транзитивное замыкание (т.е. для решения проблемы кратчайших путей для всех пар )).

Из этого объекта меня интересуют вычисления:

1. Кратчайший путь из любых вершин u -> v.
2. Матрица расстояний для всех вершин.
3. Общие вопросы достижимости.
4. Общие характеристики графа (плотность и т. Д.).

График имеет около 2000 вершин, поэтому вычисляет транзитивное замыкание (используя ).Алгоритм Флойд-Варшалла ) занимает пару часов.В настоящее время я просто кеширую сериализованный объект (используя Storable , так что это уже довольно эффективно).

Моя проблема в том, что десериализация этого объекта все еще занимает достаточно много времени (минута или около того).) и потребляет около 4 ГБ оперативной памяти.Это неприемлемо для моего приложения.

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

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

Answer 1

Для начала звучит так, будто вам нужны две сущности: вершина и ребро и, возможно, пара таблиц для результатов.Я хотел бы предложить таблицу, которая хранит информацию от узла к узлу.Если A достижим от Y, отношение получает атрибут достижимости.Итак,

Vertex:
    any coordinates (x,y,...)
    name: string
    any attributes of a vertex*

Association: 
    association_id: ID
    association_type: string

VertexInAssociation:
    vertex: (constrained to Vertex)
    association: (constrained to association)

AssociationAttributes:
    association_id: ID (constrained to association)
    attribute_name: string
    attribute_value: variable -- possibly string

* Возможно, вы также захотите хранить атрибуты вершин в таблице, в зависимости от их сложности.

Причина, по которой я добавляю сложностьАссоциация состоит в том, что ребро не считается направленным, и это упрощает запросы, чтобы рассматривать обе вершины просто как элементы набора вершин "connected-by-edge-x"

Таким образом, ребро является просто ассоциациейтипа ребра, который будет иметь атрибут расстояния.Путь является ассоциацией типа пути и может иметь атрибут прыжков.

Могут быть и другие, более оптимизированные схемы, но эта концептуально чиста - даже если она не превращает первоклассную концепцию «ребро» в сущность первого класса.

Чтобы создать минимальное ребро, вам понадобится сделать следующее:

begin transaction
select associd = max(association_id) + 1 from Association
insert into Association ( association_id, association_type ) 
    values( associd, 'edge' )
insert 
    into VertexInAssociation( association_id, vertex_id )
          select associd, ? -- $vertex->[0]->{id}
    UNION select associd, ? -- $vertex->[1]->{id}
insert into AssociationAttributes ( association_id, association_name, association_value )
          select associd, 'length', 1 
    UNION select associd, 'distance', ? -- $edge->{distance}

commit

Возможно, вы также захотите создать типы ассоциативных классов.Таким образом, «краевая» ассоциация автоматически считается «достижимой» ассоциацией.В противном случае, вы также можете вставить туда UNION select associd, reachable, 'true'.

• И тогда вы можете запросить объединение достижимых ассоциаций обеих вершин и вывести их в виде достижимых ассоциаций на другой узел, если они не существуют, и сбросить существующее значение атрибута длины + 1 в атрибут длины.

Тем не менее, вы, вероятно, хотите ORM для всего этого, и просто манипулировать им внутри Perl.

my $v1 = Vertex->new( 'V', x => 23, y => 89, red => 'hike!' );
my $e  = Edge->new( $v1, $v2 ); # perhaps Edge knows how to calculate distance.