This is a page of the online appendix of our paper on Structural Essence.

Here we present the most fundamental recursive datatypes, their representation in UML, in our distilled model, and their absolute structural essence. Note that lists have a structural essence of 1, trees have a structural essence of 2, and graphs have a structural essence of 3.

UML Model | Distilled Model | Essence | Example Object Graph | Datatype |

Linked Lists | ||||
---|---|---|---|---|

A 1->1 next A | A->A | 0+1 = 1 | a1->a2->a3->a1 | Circular singly-linked list |

A 0..1->0..1 next A | A->A | 0+1 = 1 | a1->a2->a3 | Singly-linked list |

A prev 1<->1 next A | A->A | 0+1 = 1 | a1->a2->a3->a1 a3->a2->a1->a3 |
Circular doubly-linked list |

A prev 0..1<->0..1 next A | A->A | 0+1 = 1 | a1->a2->a3 a3->a2->a1 |
Doubly-linked list |

Trees | ||||

A 0..1->0..* children A | A->A[ A[->A |
1+1 = 2 | a1->a11, a1->a12, a11->a111 | Tree |

A parent 0..1<->0..* children A | A->A[ A[->A A->A |
1+1 = 2 | a1->a11, a1->a12, a11->a111 a111->a11, a11->a1, a12->a1 |
Tree with parent pointer |

A parent 0..1<-0..* A | A[->A A->A |
1+1 = 2 | a111->a11, a11->a1, a12->a1 | Tree without children pointers |

Graphs | ||||

A 0..*->0..* successors A | A->A[ A[->A A['->A |
2+1 = 3 | a1->a2, a1->a3, a2->a4, a4->a2 | Singly-linked graph |

A predecessors 0..*<->0..* successors A | A->A[ A[->A A->A[' A['->A |
2+1 = 3 | a1->a2, a2->a1, a1->a3, a3->a1, a2->a4, a4->a2 | Doubly-linked graph |

Besides the above fundamental recursive datatypes above, we also investigate some more specialized datatypes, in particular mutually-recursive lists and trees.

UML Model | Distilled Model | Essence | Example Object Graph | Datatype |

Mutually-Recursive Linked Lists | ||||
---|---|---|---|---|

A 1->1 nextB B B 1->1 nextA A |
A->B B->A |
0+2 = 2 | a1->b1->a2->b2->a1 | Circular singly-linked mutually-recursive list |

A 1->0..1 nextB B B 0..1->1 nextA A |
A->B B->A |
0+2 = 2 | a1->b1->a2 | Singly-linked mutually-recursive list |

A prevA 1<->1 nextB B A nextA 1<->1 prevB B |
A->B B->A |
0+2 = 2 | a1->b1->a2->b2->a1 b2->a2->b1->a1->b2 |
Circular doubly-linked mutually-recursive list |

A prevA 1<->0..1 nextB B A nextA 1<->0..1 prevB B |
A->B B->A |
0+2 = 2 | a1->b1->a2 a2->b1->a1 |
Doubly-linked mutually-recursive list |

Mutually-Recursive Trees | ||||

A 1->0..* children B B 0..1->0..* children A |
A->B[ B[->B B->A[ A[->A |
2+2 = 4 | a1->a11, a1->a12, a11->a111 | Mutually-recursive tree |

A parent 1<->0..* children B B parent 0..1<->0..* children A |
A->B[ B[->B B->A B->A[ A[->A A->B |
2+2 = 4 | a1->a11, a1->a12, a11->a111 a111->a11, a11->a1, a12->a1 |
Mutually-recursive tree with parent pointer |

A parent 1<-0..* B B parent 0..1<-0..* A |
B[->B B->A A[->A A->B |
2+2 = 4 | a111->a11, a11->a1, a12->a1 | Mutually-recursive tree without children pointer |

Mutually-Recursive Graphs | ||||

A 1->0..* outEdges B B 0..*->1 targetNode A |
A->B[ B[->B B->A B['->B |
2+2 = 4 | a1->b1, b1->a2, a1->b2, b2->a3, a2->b3, b3->a4, a4->b4, b4->a2 | Singly-linked graph with edges |

A sourceNode 1<->0..* outEdges B B inEdges 0..*<->1 targetNode A |
A->B[ B[->B B->A A->B[' B['->B |
2+2 = 4 | a1->b1, b1->a2, a1->b2, b2->a3, a2->b3, b3->a4, a4->b4, b4->a2 | Doubly-linked graph with edges |

- A mutually recursive tree could be used e.g. to represent a minimax game strategy (A would correspond to a MIN node, B would correspond to a MAX node).
- Note that our distilled model collapses parallel edges.
- We use option 3 to deal with unidirectional associations with multiplicity at their tail end (e.g., for the "Tree without children pointers", the "Singly-linked graph", or the "Singly-linked graph with edges")