1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
"""Illustrates the "materialized paths" pattern.
Materialized paths is a way to represent a tree structure in SQL with fast
descendant and ancestor queries at the expense of moving nodes (which require
O(n) UPDATEs in the worst case, where n is the number of nodes in the tree). It
is a good balance in terms of performance and simplicity between the nested
sets model and the adjacency list model.
It works by storing all nodes in a table with a path column, containing a
string of delimited IDs. Think file system paths:
1
1.2
1.3
1.3.4
1.3.5
1.3.6
1.7
1.7.8
1.7.9
1.7.9.10
1.7.11
Descendant queries are simple left-anchored LIKE queries, and ancestors are
already stored in the path itself. Updates require going through all
descendants and changing the prefix.
"""
from sqlalchemy import Column, Integer, String, func, select, create_engine
from sqlalchemy.orm import remote, foreign, relationship, Session
from sqlalchemy.ext.declarative import declarative_base
from sqlalchemy.sql.expression import cast
from sqlalchemy.dialects.postgresql import ARRAY
Base = declarative_base()
class Node(Base):
__tablename__ = "node"
id = Column(Integer, primary_key=True, autoincrement=False)
path = Column(String(500), nullable=False, index=True)
# To find the descendants of this node, we look for nodes whose path
# starts with this node's path.
descendants = relationship(
"Node", viewonly=True, order_by=path,
primaryjoin=remote(foreign(path)).like(path.concat(".%")))
# Finding the ancestors is a little bit trickier. We need to create a fake
# secondary table since this behaves like a many-to-many join.
secondary = select([
id.label("id"),
func.unnest(cast(func.string_to_array(
func.regexp_replace(path, r"\.?\d+$", ""), "."),
ARRAY(Integer))).label("ancestor_id")
]).alias()
ancestors = relationship("Node", viewonly=True, secondary=secondary,
primaryjoin=id == secondary.c.id,
secondaryjoin=secondary.c.ancestor_id == id,
order_by=path)
@property
def depth(self):
return len(self.path.split(".")) - 1
def __repr__(self):
return "Node(id={})".format(self.id)
def __str__(self):
root_depth = self.depth
s = [str(self.id)]
s.extend(((n.depth - root_depth) * " " + str(n.id))
for n in self.descendants)
return "\n".join(s)
def move_to(self, new_parent):
new_path = new_parent.path + "." + str(self.id)
for n in self.descendants:
n.path = new_path + n.path[len(self.path):]
self.path = new_path
if __name__ == "__main__":
engine = create_engine("postgresql://scott:tiger@localhost/test", echo=True)
Base.metadata.create_all(engine)
session = Session(engine)
print("-" * 80)
print("create a tree")
session.add_all([
Node(id=1, path="1"),
Node(id=2, path="1.2"),
Node(id=3, path="1.3"),
Node(id=4, path="1.3.4"),
Node(id=5, path="1.3.5"),
Node(id=6, path="1.3.6"),
Node(id=7, path="1.7"),
Node(id=8, path="1.7.8"),
Node(id=9, path="1.7.9"),
Node(id=10, path="1.7.9.10"),
Node(id=11, path="1.7.11"),
])
session.flush()
print(str(session.query(Node).get(1)))
print("-" * 80)
print("move 7 under 3")
session.query(Node).get(7).move_to(session.query(Node).get(3))
session.flush()
print(str(session.query(Node).get(1)))
print("-" * 80)
print("move 3 under 2")
session.query(Node).get(3).move_to(session.query(Node).get(2))
session.flush()
print(str(session.query(Node).get(1)))
print("-" * 80)
print("find the ancestors of 10")
print([n.id for n in session.query(Node).get(10).ancestors])
session.close()
Base.metadata.drop_all(engine)
|
