Как я могу написать запрос SQLAlchemy, который будет возвращать всех потомков узла в графе? - PullRequest
Новая
       34

Как я могу написать запрос SQLAlchemy, который будет возвращать всех потомков узла в графе?

0 голосов
/ 19 сентября 2018

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

Понимая, что я в основном пытаюсьчтобы сохранить график в базе данных SQL, я обнаружил, что настройка самореференциальной схемы «многие ко многим» дала мне большую часть пути, но у меня возникли проблемы при написании запроса для возврата всех потомковузла.Я пытался следовать рекурсивному примеру SQLA CTE , который выглядит как правильный подход, но столкнулся с проблемами, заставляя его работать.Я думаю, что моя ситуация отличается от примера, потому что в моем случае запросы к Node.child (и Node.parent) возвращают инструментальные списки, а не объекты ORM.

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

a   b    c
 \ / \   |
  d   e  f
  |\ /
  g h     
  |
  i

И что я ищу, так это некоторую помощь в написании запроса, которыйдаст мне всех потомков узла.

  • get_descendants(d) должен вернуть g, h, i

  • get_descendants(b) должен вернуть d,e, g, h, i

Пример кода: 

from sqlalchemy.orm import aliased

from sqlalchemy import Column, ForeignKey, Integer, Table, Text
from sqlalchemy import create_engine
from sqlalchemy.ext.declarative import declarative_base
from sqlalchemy.orm import relationship
from sqlalchemy.orm import sessionmaker

engine = create_engine('sqlite:///:memory:', echo=True)
Session = sessionmaker(bind=engine)

session = Session()

Base = declarative_base()

association_table = Table('association_table', Base.metadata,
                           Column('parent_id', Integer, ForeignKey('node.id'), primary_key=True),
                           Column('child_id', Integer, ForeignKey('node.id'), primary_key=True))


class Node(Base):
    __tablename__ = 'node'
    id = Column(Integer, primary_key=True)
    property_1 = Column(Text)
    property_2 = Column(Integer)

    # http://docs.sqlalchemy.org/en/latest/orm/join_conditions.html#self-referential-many-to-many-relationship
    child = relationship('Node',
                            secondary=association_table,
                            primaryjoin=id==association_table.c.parent_id,
                            secondaryjoin=id==association_table.c.child_id,
                            backref='parent'
                            )

Base.metadata.create_all(engine)

a = Node(property_1='a', property_2=1)
b = Node(property_1='b', property_2=2)
c = Node(property_1='c', property_2=3)
d = Node(property_1='d', property_2=4)
e = Node(property_1='e', property_2=5)
f = Node(property_1='f', property_2=6)
g = Node(property_1='g', property_2=7)
h = Node(property_1='h', property_2=8)
i = Node(property_1='i', property_2=9)



session.add_all([a, b, c, d, e, f, g, h, i])
a.child.append(d)
b.child.append(d)
d.child.append(g)
d.child.append(h)
g.child.append(i)
b.child.append(e)
e.child.append(h)
c.child.append(f)

session.commit()
session.close()

1 Ответ

0 голосов
/ 25 сентября 2018

Решение

Следующий удивительно простой самореферентный рекурсивный запрос CTE "многие ко многим" вернет желаемые результаты для поиска всех потомков b: 

nodealias = aliased(Node)

descendants = session.query(Node)\
    .filter(Node.id == b.id) \
    .cte(name="descendants", recursive=True)

descendants = descendants.union(
    session.query(nodealias)\
    .join(descendants, nodealias.parent)
)

Тестирование с 

for item in session.query(descendants):
    print(item.property_1, item.property_2)

Выход: 

b 2
d 4
e 5
g 7
h 8
i 9

. Это правильный список b и всех его потомков.

Полный рабочий пример кода

В этом примере в класс Node добавлена ​​удобная функция для возврата всех потомков объекта, а также вычисления пути от самого себя ко всем его потомкам: 

from sqlalchemy.orm import aliased
from sqlalchemy import Column, ForeignKey, Integer, Table, Text
from sqlalchemy import create_engine
from sqlalchemy.ext.declarative import declarative_base
from sqlalchemy.orm import relationship
from sqlalchemy.orm import sessionmaker

engine = create_engine('sqlite://', echo=True)
Session = sessionmaker(bind=engine)

session = Session()

Base = declarative_base()

association_table = Table('association_table', Base.metadata,
                           Column('parent_id', Integer, ForeignKey('node.id'), primary_key=True),
                           Column('child_id', Integer, ForeignKey('node.id'), primary_key=True))


class Node(Base):
    __tablename__ = 'node'
    id = Column(Integer, primary_key=True)
    property_1 = Column(Text)
    property_2 = Column(Integer)

    # http://docs.sqlalchemy.org/en/latest/orm/join_conditions.html#self-referential-many-to-many-relationship
    child = relationship('Node',
                            secondary=association_table,
                            primaryjoin=id==association_table.c.parent_id,
                            secondaryjoin=id==association_table.c.child_id,
                            backref='parent'
                            )

    def descendant_nodes(self):
        nodealias = aliased(Node)
        descendants = session.query(Node.id, Node.property_1, (self.property_1 + '/' + Node.property_1).label('path')).filter(Node.parent.contains(self))\
            .cte(recursive=True)
        descendants = descendants.union(
            session.query(nodealias.id, nodealias.property_1, (descendants.c.path + '/' + nodealias.property_1).label('path')).join(descendants, nodealias.parent)
        )
        return session.query(descendants.c.property_1, descendants.c.path).all()


Base.metadata.create_all(engine)

a = Node(property_1='a', property_2=1)
b = Node(property_1='b', property_2=2)
c = Node(property_1='c', property_2=3)
d = Node(property_1='d', property_2=4)
e = Node(property_1='e', property_2=5)
f = Node(property_1='f', property_2=6)
g = Node(property_1='g', property_2=7)
h = Node(property_1='h', property_2=8)
i = Node(property_1='i', property_2=9)



session.add_all([a, b, c, d, e, f, g, h, i])
a.child.append(d)
b.child.append(d)
d.child.append(g)
d.child.append(h)
g.child.append(i)
b.child.append(e)
e.child.append(h)
c.child.append(f)
e.child.append(i)

session.commit()


for item in b.descendant_nodes():
    print(item)

session.close()


"""
Graph should be setup like this:

a   b    c
 \ / \   |
  d   e  f
  |\ /|
  g h |    
  +---+
  i

"""

Вывод: 

('d', 'b/d')
('e', 'b/e')
('g', 'b/d/g')
('h', 'b/d/h')
('h', 'b/e/h')
('i', 'b/e/i')
('i', 'b/d/g/i')

Комментарии

...