Not all graphs are trees
buttondown.email
buttondown.email
> Even in a language like Rust, which has not yet implemented mutable aliasing (an oft-requested feature stuck at the RFC stage)
Disallowing mutable aliasing is in fact the whole point of Rust. Perhaps it’s “requested” by people still learning the language? Is the “not yet implemented” part meant as irony? Does the author mean something else?
[0]: https://doc.rust-lang.org/std/cell/struct.UnsafeCell.html
I wish this post had more examples of concrete non-tree queries. Is cross-joining a CTE to itself realistic?
Imo this discussion seems to assume multiple references of a CTE contain many of the same rows with different transforms which are later joined.. what’s an actual example of this? I don’t think I’ve ever seen it
Usually CTEs are shorthand for doing a few joins. And when you reference them multiple times, it’s almost always with different rows in the CTE table. AKA little-no reuse potential. Postgres WITH AS NOT MATERIALIZED of course
Speaking from experience, there's lots of rewrites you'd want to do in a query optimizer that having access to efficient DAG-shaped query plans would make tenable, but as a specific example they are an important part of doing full subquery decorrelation [3].
[1] https://buttondown.email/jaffray/archive/why-are-query-plans...
[2] https://egraphs-good.github.io/
[3] https://www.scattered-thoughts.net/writing/materialize-decor...
the simplest example is a simple two-column table of a directed graph's edges, e(from, to). Then: Triangle(a, b, c) := e(a, b), e(b, c), e(c, a).
#Triangle <= c * (#e)^1.5, for a small c. (I think c = 3 in this case, but I'm not sure.)
Using binary joins for pathological input will however take O((#e)^2). If you do row-granularity lookup using an auxiliary index (actually 2 in the simplified way, but they can be merged by pushing the post-lookup choice down to index creation) along with indexing e twice (once for each of the two columns), you can do it in O((#e)^1.5):
Create auxiliary indices eaux1 and eaux2: eaux1(from, (#e(from, to))). eaux2(to, (#e(from, to))).
Iterate over e(a, b): Look up eaux1(b, ?countbc) and eaux2(a, ? countca). If countbc < countca, then: expand through point lookup e(b, ?c). Filter those resulting e(?a, b), e(b, ?c) candidates using a point membership query suitable index of e(c, a). else: expand through point lookup e(?c, a). Filter those resulting e(a, ?b), e(?c, a) candidates using a point membership query suitable index of e(b, c).
Done.
As can be seen, the trick is to select between the current options for "next table to join current partial row against" at each nesting level of the generally nested-loop-join structured query execution, using premade indices that reveal the iteration count of the upcoming inner nested loop in O(1) time.
Yes! Technically you have to say `WITH RECURSIVE ...` first, but yes, it's a very common thing to do to, for example, compute the transitive closure of nested groups. Just remember to use `UNION` not `UNION ALL`! (Otherwise you will get an infinite loop if there's a circular group.)
WITH RECURSIVE closure AS (
// Seed the closure
SELECT parent AS parent, child AS child
FROM groups
// Repeat the right side of the UNION
// until no new rows are added
UNION
// Recursively join the closure to the
// groups
SELECT g.parent, c.child
FROM groups g
JOIN closure c ON g.child = c.parent
);Now that I'm a gamedev, if there's a permissively licensed C/C++ or a DLL, or something in .net land that would let me store facts and rules and run some queries, I could put it to work.
If anyone that reads this has cooked with deductive databases / theorem proving / logic programming languages things I'd love to hear your guidepost opinions.
The fact it comes with baked in graph traversal means I could offload pathfinding to it for certain kinds of projects (thinking like turn based strategy games on a hex grid, multiplayer board games). I'm a big fan of isomorphism in anything multiplayer.
There's some more esoteric things I want to think about, I just don't know datalog enough yet to know how much magic this will bring to these ideas.
I need to learn enough to answer questions like "how hard is it to solve a game of clue (the boardgame, with the rooms and the murder by candlestick) with a query in cozo?" -- If it's no sweat, like I think it might be, then that opens up a lot of possibilities for deductive AI systems. Constraint based solving / deduction is what I'm really interested in. Once I get a sense of what I can do, the ideas will come.
State machines, graphs and trees are data structures I use _constantly_. I want to love cozo enough to promote it to handling those almost every time I use one that might benefit from persistence or have any chance of enjoying emergent mechanics from being able to create cross system relations.
I saw the api had dijkstra's but I didn't see A* which seemed interesting. Lots to learn.
Explanation:
rooted: One vertex (also called a node) has been designated the root. The depth of a vertex is the number of branches in the path from root to the vertex. So depth of the root itself is zero and is the only vertex in the tree with this property.
strict: The edges have no weight(s).
connected: A graph is said to be connected if there is a path (edge) between every pair of vertices. From every node to any other node, there is a path to traverse.
undirected: The edges have no directionality specified.
acyclic: The are no closed loops (no cycles of any length).
graph: An abstract data structure consisting of a finite set of vertices and a finite set of edges (vertices pairs).
As another commenter has pointed out, the definition of a tree in mathematics is somewhat different...a tree need not have a root.
For example, B-trees are directed trees, and Huffman Coding is based on a weighted tree structure.
From chapter two of the book "Algorithmic Graph Theory and Sage" [1]; it states the following concerning directedness:
"A directed tree is a digraph which would be a tree if the directions on the edges were ignored." ... which is the correct definition from my understanding.
However, the authors go on to say:
"A rooted tree can be regarded as a directed tree since...Directed trees are pervasive in theoretical computer science, as they are useful structures for describing algorithms and relationships between objects in certain datasets."
So, colloquially (but perhaps not formally), one can refer to a directed, rooted, connected, acyclic graph as a tree.
Concerning weights, wolfram provides a definition of a strict graph [2] which specifies the unweighted qualifier (and undirected qualifier):
"A simple graph, also called a strict graph (Tutte 1998, p. 2), is an unweighted, undirected graph..."
The wolfram definition of a tree [3] includes the 'simple' qualifier:
Tree "is a simple, undirected, connected, acyclic graph..."
So, I would suggest formally, a tree cannot have weights (recall that weights are basically labels assigned to the edges).
Incidentally, I took down from the shelf my copy of The Art of Computer Programming (TAOCP) Volume One, and section 2.3 deals with trees exclusively. Donal Knuth asserts that trees are 'the most important nonlinear structures that arise in computer algorithms'. I skimmed the entire section and although he makes reference to weighted path lengths, I did not see any mention of weighted trees.
So, to my understanding, the original definition I proposed is valid, but I am very open to correction.
Concerning spanning trees and Huffman Coding - the tree are constructed from weighted graphs (not that the trees are weighted themselves). However, I understand where you are coming from, where again colloquially (but perhaps not formally), people often refer to and construct weighted trees.
At the beginning of Section 2.3.4 in TAOCP, Knuth makes the following important point concerning graph theory:
"Unfortunately, there will probably never be a standard terminology in this field, and so the author has followed the usual practice of comtemporary books on graph theory, namely to use words that are similar but not identical to the terms used in any other books on graph theory...the nomenclature used here is also biased towards computer applications".
So, in summary, my definition of a tree is open to debate :)
I am grateful for your question because in seeking out the answer, it has deepened my understanding of what a tree is.
[1] Algorithmic Graph Theory and Sage" by David Joyner, Minh Van Nguyen, David Phillip; Version 0.8-r1991;
In order, the representations are:
1. "Inlining", a direct tree structure, in C++-like syntax something like `struct Node {vector<Node>;}`. The insight here is that if you're not storing a tree, some of the nodes need to be duplicated.
2. "Let Bindings", An indirect tree structure, like `struct Node {vector<Node*>;}`. Here, the insight is that instead of storing nodes, you store names of nodes (in this case pointers), so that the nodes can be re-used. Note that the nodes themselves may be stored somewhere else in the same expressions.
3. "Self-Reference", same as above, but a node can store the name of itself, or one of its ancestors.
4. "Fixpoint Operator", Instead of explicitly storing a graph, we store a transformation from one graph to another, then say the graph we want equals that transformation repeatedly applied to some starting graph, until the transformation's output equals its input (a.k.a. a fixed point is found). Something like `struct ImplicitGraph {Graph initial; Graph (*)(Graph) transform;}`. If you're unfamiliar with C++ function pointers, transform is a function from Graph to Graph. The "hole" the author talks about refers to the fact that the output graph of the transformation can contain copies of the input graph, so the "hole" is the transform parameter; there's a "hole" in the output graph until the parameter is known. Since the transformation can be arbitrarily complex, any graph can be represented, although typically, you'd want as simple a transform as possible.
5. "Explicit Listing of Edges", this method is actually more straightforward than the previous, but it requires thinking about the graph a little differently. It's exactly what it says on the tin; instead of the graph being implicit in the structure of the data, the edges (a.k.a. links or lines) are explicitly listed. There's more than one way to do this, for example a straightforward way might look like `struct Graph {set<Node>; set<pair<Node*, Node*>>;}`. From the example in the article, it looks like Datalog is closer to something like `struct Graph {set<Node> initial_nodes; set<optional<Node> (*)(Node)> generators;}`. Kind of like in 4., you start with a set of nodes, then repeatedly apply each generator to each node until you stop getting new nodes. The edges in this case are between each node and the nodes it generates.
Finally, all of these types of representations also exist syntactically, not just structurally. After all, an expression in a given syntax is just a way of representing some structure, the same way a bunch of bytes in memory can be a way of representing some structure. And each of these representations has strengths syntactically and structurally.
Slight nitpick: in mathematics, a tree need not have a root.
https://mathworld.wolfram.com/FreeTree.html: “a normal tree with no node singled out for special treatment”
https://mathworld.wolfram.com/RootedTree.html: “A rooted tree is a tree in which a special ("labeled") node is singled out. This node is called the "root" or (less commonly) "eve" of the tree. Rooted trees are equivalent to oriented trees (Knuth 1997, pp. 385-399). A tree which is not rooted is sometimes called a free tree, although the unqualified term "tree" generally refers to a free tree.”
> A tree which is not rooted is sometimes called a free tree, although the unqualified term "tree" generally refers to a free tree.
I wonder if that was once the case but no longer is. I'm learning I think of trees mostly through the lens of data structures and not graph theory and I imagine more people do than not.
A tree is (also) any loop-free graph.
Sorry my inner edge case fairy beckoned.
Let’s say we want to get from A to B, but we visit Y twice. That means there’s a segment of A~B that is Y~Y (a loop). However, since we’re talking about undirected edges, we can reverse that segment. Then both our original A~B and the A~B with Y~Y reversed are paths from A to B.
So if there’s a single path from A to B, there cannot be a Y we visit twice along that path.
(Please don’t take this as criticism; my pedantic nature got the better of me.)
I was trying to find terminology for something Like 'all possible paths between these two nodes contain exactly one Hamiltonian sub-path' but I think that's a bit of a circular definition
All that said I'm running off 3 hours of sleep and about to recoup so that probably explains my non constructive comments here
(to complement cperciva's answer with a counter example)
2001: Arrays & Trees (Json)
2042: Graphs, Trees, Arrays (XML final era)
As Haskell is lazy, this self-referencing is quite nice. There is this reddit-joke about implementing an is-even function. In haskell we can write an infinite list of alternating True/False like `alt = True : False : alt` and is-even is now `is_even n = alt !! n` where !! is array access.
Even if the data structure is not cyclic, but you're talking about sharing, then you have to have syntax about explicit sharing and the lifetime of the share (immutability comes to the rescue again), as detecting sharing is a very difficult problem in and of itself.
in expr(x)
They are DAGs, which are a deduplicated representation of trees.
E.g. the Lisp expression (+ a (* b b)), informally called a syntax tree, is actually a DAG. Both apparent instances of the b symbol are actually graph edges leading to the same symbol object. Moreover, nothing points to its parent; that would be horrible.
Other kinds of trees don't always have parent pointers. For instance search trees like red-black can be implemented with parent pointers, or without; e.g. with functional recursion.
That is a syntax tree. Syntactically it is a tree. The fact that you have a later step that recognises that the `b` identifiers refer to the same object and turn it into a DAG doesn't mean it isn't a tree initially.
E.g. see the tree and tree-structure glossary entries in ANSI CL.
https://www.lispworks.com/documentation/lw61/CLHS/Body/26_gl...