Как реализовать рекурсивное считыание всех потомков объекта в Gino()?

Question

[toddbarry]

База устроена так, что у каждого элемента таблицы может быть один или несколько дочерних элементов этйо же самой таблицы. Прошу помочь с реализацией запроса к базе, который бы возвращал детей, детей детей и т д - то есть всех потомков какого либо элемента. Вариант доставать из базы id дочерних элементов данного, а затем снова отправлять запросы к базе чтобы достать дочерние этих дочерних и т п мне не очень нравится из-за ресурсоемкости. asyncpg, с которым работает gino работает быстрее исполнения кода на python, поэтому рациональнее построить рекурсивный запрос к базе данных.
Я знаю, что эта задача легко решается в sqlalchemy. Пример ее решение приведен например здесь, однако мне необходим запрос именно в gino. Gino, на сколько я понял не поддерживает использование метода relationship, вместо этого подобные запросы реализуются как-то при помощи загрузчиков. в официальном руководстве приведен пример использования метода load для поска всех непосредственных дочерних элементов данного элемента вот здесь. Но я не знаю, как это использовать в решении моей задачи рекурсивного поиска всех потомков данного родителя.

На самом деле идеальным вариантом было бы даже не приведенное по ссылке решение, а решение, использующее немного другую структуру данных, если это возможно.

А именно - следующую

class Nodes(db.Model):
    __tablename__ = 'nodes'

    id = db.Column(db.Integer, primary_key=True)
    info = db.Column(db.Text)

class Edges(db.Model):
    __tablename__ = 'edges'

    id = db.Column(db.Integer, primary_key=True)
    source = db.Column(db.Integer, db.ForeignKey('nodes.id'))
    target = db.Column(db.Integer, db.ForeignKey('nodes.id'))

    _edge_idx = db.Index('edge_idx', 'source', 'target', unique=True)

Вместо того чтобы хранить список непосредственных дочерних элементов в табице Nodes, для меня было бы идеальным вариантом описать связи элементов в таблице edges, и при помощи рекурсивного запроса находить все строки в таблице Edges, такие что параметр target в них был бы заданным (он хранит id узла графа, с которым соединен), затем применял бы тот же запрос к параметрам source полученных строк в Edges - то есть искал бы все строки в таблице Edges, у которых параметр target совпадал бы с ранее полученными значениями параметра source и возвращал бы их значения параметров source и т д пока не останется таких строк, которые бы имели параметр target, равный одному из полученных значений параметра source на предыдущей итерации.

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

Очень прошу помощи, поскольку сам я, похоже прийти к решению не смогу

Answer 1

[Дмитрий Шицков]

Для поиска родителей-потомков есть там Self Referencing, правда экспериментальный.

Comments

[toddbarry]

На сколько я понимаю, так просто, используя пример с Self Referencing не получится реализовать отношение многие ко многим в пределах одной таблицы? Но данные, к сожалению, устроены так, что каждый родитель может иметь одного или нескольких детей и у каждого из детей может быть один или несколько родителей - прямо как в примере реализации решения данной задачи для sqlalchemy

[Дмитрий Шицков]

toddbarry, Self Referencing как раз для древовидной структуры отношений.

[toddbarry]

Дмитрий Шицков, Вот именно, древовидную. Если я не ошибаюсь, в дереве каждый дочерный элемент может иметь одного и только одного родителя. То есть здесь реализуется отношение многие к одному, так же, как указано в примере в документации. Однако мне нужен граф, в котором было бы реализовано отношение многие ко многим, то есть каждый родитель мог бы иметь одного или нескольких детей и каждый дочерний может иметь одного или нескольких родителей. Прошу прощения если я ошибаюсь в понимании понятия дерева и подобное возможно с использованием Self Referencing

Вот пример

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

[Дмитрий Шицков]

toddbarry, так, наконец увидел ваше ключевое "многие ко многим".

[Дмитрий Шицков]

toddbarry, я так понимаю будет затруднительно обойтись одной лишь таблицей. Понадобится дополнительная таблица отношений. Посмотрите пример в other-relationships many-to-many. Однако за связями всё равно придётся следить вручную.

[toddbarry]

Дмитрий Шицков, Уже смотрел. В приведенном примере мне многое не ясно

class Parent(db.Model):
    __tablename__ = 'parents'
    id = db.Column(db.Integer, primary_key=True)

    def __init__(self, **kw):
        super().__init__(**kw)
        self._children = set()

    @property
    def children(self):
        return self._children

    @children.setter
    def add_child(self, child):
        self._children.add(child)
        child._parents.add(self)


class Child(db.Model):
    __tablename__ = 'children'
    id = db.Column(db.Integer, primary_key=True)

    def __init__(self, **kw):
        super().__init__(**kw)
        self._parents = set()

    @property
    def parents(self):
        return self._parents


class ParentXChild(db.Model):
    __tablename__ = 'parents_x_children'

    parent_id = db.Column(db.Integer, db.ForeignKey('parents.id'))
    child_id = db.Column(db.Integer, db.ForeignKey('children.id'))


query = Parent.outerjoin(ParentXChild).outerjoin(Child).select()
parents = await query.gino.load(
    Parent.distinct(Parent.id).load(add_child=Child.distinct(Child.id))).all()

Например где определяется функция set()
Мне не ясно что происодит когда пишется wrapper '@children.setter'

Так же в примере используется таблица родителей и таблица детей, в случае использования Self Referencing методы, относящиеся к children и parent будут реализованы в пределах одного класса Nodes?

На сколько я понимаю, при использовании Self Referencing, в ParentXChild будет использоваться ссылка ForeignKey('nodes.id') как для child_id, так и для parent_id

Мне приведенная реализация отношения многие ко многим кажется очень запутанной

[toddbarry]

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

class Edges(db.Model):
    __tablename__ = 'edges'

    id = db.Column(db.Integer, primary_key=True)
    source = db.Column(db.Integer, db.ForeignKey('nodes.id'))
    target = db.Column(db.Integer, db.ForeignKey('nodes.id'))

    _edge_idx = db.Index('edge_idx', 'source', 'target', unique=True)

[Дмитрий Шицков]

где определяется функция set()

Это метод из db.Model

Мне не ясно что происодит когда пишется wrapper '@children.setter'

Видимо, вы недавно с python подружились. Про эти декораторы тут pythonz.net/references/named/property

в случае использования Self Referencing методы, относящиеся к children и parent будут реализованы в пределах одного класса Category?

Полагаю, что это так.

Реализация довольно "влоб", поэтмоу не уверен, что её можно назвать запутанной.

[toddbarry]

Дмитрий Шицков,

Видимо, вы недавно с python подружились.

Просто возвращаюсь к нему время от времени, когда появляется на это время. А появляется оно не так часто. С данным декоратором прежде и правда не встречался

Спасибо. Буду пытаться разобраться

[toddbarry]

Дмитрий Шицков, Пример из документации делает немножко не то - в примере с self referencing лишь говорится о том, что если в классе объявлено несколько внешних ключей, то необходимо использовать ссылки. Рекурсивного считывания детей, детей их детей и т д - то есть всех потомков там нет.

В итоге решение нашлось в использовании

cte(recursive=True)

Код получился следующим:

class Nodes(db.Model):
    __tablename__ = 'nodes'

    id = db.Column(db.Integer, primary_key=True)

    def __init__(self, *args, **kwargs):
        super(Nodes, self).__init__(*args, **kwargs)

class Edges(db.Model):
    __tablename__ = 'edges'

    id = db.Column(db.Integer, primary_key=True)
    source = db.Column(db.Integer, db.ForeignKey('nodes.id'))
    target = db.Column(db.Integer, db.ForeignKey('nodes.id'))

    _edge_idx = db.Index('edge_idx', 'source', 'target', unique=True)

    def __init__(self, *args, **kwargs):
        super(Edges, self).__init__(*args, **kwargs)

a1=await Edges.create(source=1,target=2)
a2=await Edges.create(source=1,target=3)
a3=await Edges.create(source=2,target=5)
a4=await Edges.create(source=2,target=6)
a5=await Edges.create(source=3,target=4)
a6=await Edges.create(source=3,target=5)
a7=await Edges.create(source=4,target=6)

a8=await Edges.create(source=7,target=8)
a9=await Edges.create(source=7,target=9)
a10=await Edges.create(source=8,target=9)

descendants = db.select([Edges.source, Edges.target]).where(Edges.source == 3).cte(recursive=True)

parents = descendants.alias()
edges = Edges.alias()
descendants = descendants.union(db.select([edges.source, edges.target]).where(edges.source == parents.c.target))
query = db.select([descendants.c.target, descendants.c.source]).select_from(descendants)
result = await query.distinct('target').gino.all()
print(result)

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