Recursive relationships

[jmatsushita]

Hi there 👋

I'm trying to work with recursive relationships.

TutorialD (master/main): rec := relation{tuple{src 0, tgt 1}, tuple{src 1, tgt 2}, tuple{src 2, tgt 3}}
TutorialD (master/main): :showexpr rec
┌────────────┬────────────┐
│src::Integer│tgt::Integer│
├────────────┼────────────┤
│0           │1           │
│1           │2           │
│2           │3           │
└────────────┴────────────┘

It seems to work ok for a depth 1 traversal:

TutorialD (master/main): :showexpr ((rec where src=0) join (rec rename {tgt as tgt2, src as tgt}))
┌────────────┬────────────┬─────────────┐
│src::Integer│tgt::Integer│tgt2::Integer│
├────────────┼────────────┼─────────────┤
│0           │1           │2            │
└────────────┴────────────┴─────────────┘

Also if I add an edge:

TutorialD (master/main): insert rec relation{tuple{src 1, tgt 4}}
TutorialD (master/main): :showexpr rec
┌────────────┬────────────┐
│src::Integer│tgt::Integer│
├────────────┼────────────┤
│1           │4           │
│2           │3           │
│1           │2           │
│0           │1           │
└────────────┴────────────┘
TutorialD (master/main): :showexpr ((rec where src=0) join (rec rename {tgt as tgt2, src as tgt}))
┌────────────┬────────────┬─────────────┐
│src::Integer│tgt::Integer│tgt2::Integer│
├────────────┼────────────┼─────────────┤
│0           │1           │2            │
│0           │1           │4            │
└────────────┴────────────┴─────────────┘

I can work out a way to do a depth 2 traversal:

TutorialD (master/main): :showexpr ((rec where src=0) join (rec rename {tgt as tgt2, src as tgt}) join (rec rename {tgt as tgt3, src as tgt2}))
┌────────────┬────────────┬─────────────┬─────────────┐
│src::Integer│tgt::Integer│tgt2::Integer│tgt3::Integer│
├────────────┼────────────┼─────────────┼─────────────┤
│0           │1           │2            │3            │
└────────────┴────────────┴─────────────┴─────────────┘

Can this be generalised to a depth n traversal? Also would it be possible to group the result by depth?

Thanks for your time!

Jun

[jmatsushita]

Also unfortunately:

TutorialD (master/main): foreign key src_tgt rec{src} in rec{tgt}
ERR: RelationTypeMismatchError attributesFromList [(Attribute "src" IntegerAtomType)] attributesFromList [(Attribute "tgt" IntegerAtomType)]

UPDATE: I think this is non-sensical though 😅

[jmatsushita]

Ok what I was really trying to do was:

TutorialD (master/main): nod := relation{tuple{nid 0, lbl "a"}}
TutorialD (master/main): insert nod relation{tuple{nid 1, lbl "b"}}
TutorialD (master/main): :showexpr nod
┌─────────┬────────────┐
│lbl::Text│nid::Integer│
├─────────┼────────────┤
│"b"      │1           │
│"a"      │0           │
└─────────┴────────────┘
TutorialD (master/main): foreign key src_nod (rec rename {src as nid}){nid} in nod{nid}
ERR: InclusionDependencyCheckError "src_nod" Nothing
TutorialD (master/main): insert nod relation{tuple{nid 2, lbl "c"}}
TutorialD (master/main): insert nod relation{tuple{nid 3, lbl "d"}}
TutorialD (master/main): insert nod relation{tuple{nid 4, lbl "e"}}
TutorialD (master/main): foreign key src_nod (rec rename {src as nid}){nid} in nod{nid}
TutorialD (master/main): foreign key tgt_nod (rec rename {tgt as nid}){nid} in nod{nid}

Works nicely

[jmatsushita]

Oh wow, actually this does work if I make the root loop on itself (tuple {src 0, tgt 0}) and map src and tgt attributes to another name x:

TutorialD (master/main): rec := relation{tuple{src 0, tgt 0},tuple{src 0, tgt 1}, tuple{src 1, tgt 2}, tuple{src 2, tgt 3}}
TutorialD (master/main): foreign key src_tgt (rec rename {src as x}){x} in (rec rename {tgt as x}){x}

[agentm]

That's a clever workaround. I suppose it wouldn't hurt to make a utility wrapper command to make this pattern more convenient. Do you have some syntax in mind?

By the way, the foreign key syntax is itself a convenience wrapper around inclusion dependencies which have been proven to be able to represent any database constraint.

[agentm]

I've also been thinking about how to represent n-ary, nested relationships within a relation outside the scope of adjacency lists since we could leverage nested relations. However, the top-level relation type does not seem to be able to represent arbitrarily-nested relation types, so I don't see off-hand how to represent arbitrary levels of nesting.

[jmatsushita]

Thanks for the feedback 🙏 I'll try to think about a syntax for traversing recursive relationships. Datalog might be an inspiration ? I'm very interested in modeling n-ary relations but I don't quite visualise how to do it with a nested relation even for the arity 2 case. Could you give an example?

[jmatsushita]

Sort of broadening the scope quite a bit here, but I was wondering what are principled approaches to model graphs in a relation database. This seems like a very interesting paper on implementing graph algorithms in RDBMSes using new operations and a while syntax.

https://dsl.cds.iisc.ac.in/~course/TIDS/papers/allinone.pdf

To support graph processing, in this work, we propose 4 new relational algebra operations, MM- join, MV-join, anti-join, and union-by-update.

[agentm]

Thanks for linking to that paper- it proposes new SQL syntax to support said traversals. However, it is still limited by the capabilities of SQL (which Project:M36 is not). For example, Project:M36 supports algebraic data types and relation-valued attributes, both of which can be leveraged to represent graph more effectively.

For example, relation-valued attributes would be a great way to query a database to service an ORM. Here's a sample dashboard using the C.J. Date example. This would typically done by an outer join in SQL, but the Project:M36 representation is quite natural:

:showexpr (s join sp){p#,qty,s#,sname} group ({p#,qty} as parts)
┌───────────────────────────────────────┬────────┬───────────┐
│parts::relation {p#::Text,qty::Integer}│s#::Text│sname::Text│
├───────────────────────────────────────┼────────┼───────────┤
│┌────────┬────────────┐                │"S4"    │"Clark"    │
││p#::Text│qty::Integer│                │        │           │
│├────────┼────────────┤                │        │           │
││"P4"    │300         │                │        │           │
││"P5"    │400         │                │        │           │
││"P2"    │200         │                │        │           │
│└────────┴────────────┘                │        │           │
│┌────────┬────────────┐                │"S1"    │"Smith"    │
││p#::Text│qty::Integer│                │        │           │
│├────────┼────────────┤                │        │           │
││"P4"    │200         │                │        │           │
││"P5"    │100         │                │        │           │
││"P6"    │100         │                │        │           │
││"P3"    │400         │                │        │           │
││"P1"    │300         │                │        │           │
││"P2"    │200         │                │        │           │
│└────────┴────────────┘                │        │           │
│┌────────┬────────────┐                │"S3"    │"Blake"    │
││p#::Text│qty::Integer│                │        │           │
│├────────┼────────────┤                │        │           │
││"P2"    │200         │                │        │           │
│└────────┴────────────┘                │        │           │
│┌────────┬────────────┐                │"S2"    │"Jones"    │
││p#::Text│qty::Integer│                │        │           │
│├────────┼────────────┤                │        │           │
││"P2"    │400         │                │        │           │
││"P1"    │300         │                │        │           │
│└────────┴────────────┘                │        │           │
└───────────────────────────────────────┴────────┴───────────┘

We could consider some syntax addition to TutorialD which would generate graph traversals using RVAs, but I'm not yet sure what that would look like.

[YuMingLiao]

I encounter this issue too when I want to record tree-like comments.

I found an article talking about tree structure in sql (in Chinese). Tree structure in SQL

Basically, it says there are four ways to do that:

Adjacency List: easiest to implement and understand Path Enumeration: convenient when paths are needed Nested Sets: good for query frequently but modify occasionally. Closure Table: flexible, needs extra space.

[agentm]

There's actually a more natural way to represent graphs in the relational algebra which I have not seen before. It's not quite possible in Project:M36 because we don't support recursive data types, but it should be possible to support in the future.

Here's an example that works today that hints at what could be possible:

TutorialD (master/main): :showexpr relation{tuple{val 4, children relation{tuple{val 6,children relation{tuple{}}}}},                   tuple{val 10, children relation{tuple{val 1, children relation{tuple{}}},                                                   tuple{val 2, children relation{tuple{}}}}}}
┌───────────────────────────────────────────────────────┬────────────┐
│children::relation {children::relation {},val::Integer}│val::Integer│
├───────────────────────────────────────────────────────┼────────────┤
│┌─────────────────────┬────────────┐                   │4           │
││children::relation {}│val::Integer│                   │            │
│├─────────────────────┼────────────┤                   │            │
││┌┐                   │6           │                   │            │
││││                   │            │                   │            │
││├┤                   │            │                   │            │
││└┘                   │            │                   │            │
│└─────────────────────┴────────────┘                   │            │
│┌─────────────────────┬────────────┐                   │10          │
││children::relation {}│val::Integer│                   │            │
│├─────────────────────┼────────────┤                   │            │
││┌┐                   │2           │                   │            │
││││                   │            │                   │            │
││├┤                   │            │                   │            │
││└┘                   │            │                   │            │
││┌┐                   │1           │                   │            │
││││                   │            │                   │            │
││├┤                   │            │                   │            │
││└┘                   │            │                   │            │
│└─────────────────────┴────────────┘                   │            │
└───────────────────────────────────────────────────────┴────────────┘

If we could define a recursive type for the top-level relation, then we could conceivably enable unlimited levels of nested structures using nested relations. This would allow us, for example, to enable fine-grained constraints on the graph use normal database constraints.

This is certainly more natural than adjanceny lists and less error-prone than number range-based graphs structures.