Computing Graph Algorithms - e.g. Transitive Closure and Common Table Expressions (CTE)

[DavidPratten]

Hi

Curious if edgedb has/will have equivalent expressive power of SQL's CTE that can, for example, compute transitive closures on graphs or compute the solution to a Sudoku .

Either currently, or on the roadmap?

Thanks

David

[elprans]

Support for recursion in queries is planned. Aside from transitive closure a-la WITH RECURSIVE we also plan to add syntactic support for retrieving trees to arbitrary depth in SELECT, e.g.

SELECT Post { comments: { author, text, comments* } }

This would return a structure with nested comments (up to some depth limit).

[DavidPratten]

@elprans curious as to your thoughts on this.

I'm passionate about the goal to "do better than SQL"!

I writing to propose that edgedb consider the option of not imposing CTE-like machinery on the mechanism for recursive relational queries for transitive closure and similar use-cases.

A simpler and more direct alternative to the CTE machinery is described here: Composable Recursive Relational Queries.

Thoughts?

David

[elprans]

Hi David. Thanks for sharing the article, it's quite interesting and insightful! I agree that the full recursive CTE syntax for arbitrary traversals is overkill, and we'll be considering simpler syntax for these use cases.

[shackra]

Probably related, but I see this use-case of linked lists using CTE on Postgres and was wondering if this is already covered in EdgeDB in some other way, or we need to wait until the support for CTE is provided as stated on answer above?

[tailhook]

Probably related, but I see this use-case of linked lists using CTE on Postgres and was wondering if this is already covered in EdgeDB in some other way, or we need to wait until the support for CTE is provided as stated on answer above?

To the best of my understanding this is not covered. I think I've always seen some numeric priority-like field or any other sortable keys used for ordering such list.

Please elaborate on the following if you want to see this feature implemented. This will help us prioritize it.

1. It looks like this pattern prioritizes writes more than reads, right? At which point (in terms of read RPS/write RPS, data size, etc..) it makes sense in your opinion? Or is it for concurrent inserts (i.e. collaborative environment or similar)? I mean read query is quite complex. If you have read-heavy workload it should be much easier to keep numeric priorities, and just update all subsequent numeric priorities in the case of insertion. In case of a huge list it may be a problem, but in case of a huge list, recursive read query is perhaps slow too. And you can also organize numeric priorities in a way that provides some gaps to make it even faster than in "linked list" case, at the expense of the recalculating all the indexes at some rare occasions. Although, I'm not sure how great postgres is at optimizing such recursive queries.
2. Can you the topology sort on the client? And what the downside of that? Do you (plan to) store multiple lists in the same table without a key that identifies each list? (so you can't fetch all the items that belongs to that list and sort them on the client easily)
3. How often do you see and/or implement linked lists in database in practice? Or do you want to just experiment with it for the first time?

[shackra]

At which point (in terms of read RPS/write RPS, data size, etc..) it makes sense in your opinion?

IDK, I'm not a database engineer :(

Or is it for concurrent inserts (i.e. collaborative environment or similar)?

I have a couple of use cases that requires ordered lists of things, I think getting the data already ordered from the query to the database is ergonomic than sorting things after receiving the data.

Do you (plan to) store multiple lists in the same table without a key that identifies each list? (so you can't fetch all the items that belongs to that list and sort them on the client easily)

In my particular case, I wouldn't dare to store lists of things without some sort of identifier that allows me to differentiate them.

How often do you see and/or implement linked lists in database in practice? Or do you want to just experiment with it for the first time?

hard to tell, but I would say “experimenting” is not on my plans, for my use-case I'm attempting to solve a particular problem relaying on linked lists