Introduce a subclass of tree:Relation e.g. tree:SubsetRelation to Identify the Minimum spanning tree inside a graph, which could facilitate the search from the perspective of a (tree) client. #85
Comments
|
Doing my own translation of the problem and proposal first before diving deeper into possible other solutions at a later time: When a client follows their own traversal approach, it is automatically going to prune relations to nodes it already visited. The relations it prunes could then be seen as client-decided non-subsetrelations or the gray relations. The proposal here is that the server annotates the relations that will create one of the possible trees from the graph. The benefit of this proposal would be that the client can trust that, if it only decides to follow the relations annotated by the server, no parent or sibling relations (gray relations) will be provided, and that
|
|
The importance here is that by defining a relation as a subset, we introduce transitivity of traversed relations: For example, say we want to partition a geospatial dataset: We make a tree with 3 sublevels: tree:zoom, tree:longitudeTile and tree:latitudeTile I think we would run into issues with the pruning algorithm of relations when either trees are crawler depth first or are not coherent in structure. If the client plans to walk the whole tree, this is probably not much of an issue. But I do think that it would be best to define which relations are transitive in relation to others. |
|
I would argue the transitivity is something that at this moment the client must take into account; but it is not guaranteed by the server, because the server wants to document multiple ways of arriving at a similar node. It’s thus the client that must be smarter, and understand that following a link it already visited of course won’t result in new members to be discovered. Why we decided to add this in the past:
However, the benefits of extending the spec somehow to allow for saying: _ “hey, I’m a server that won’t provide search forms, backlinks or sibling links, so you can just keep your state as the yet to be fetched nodes without keeping the full history of what you’ve already seen”_ is big. E.g., the issue on state in LDES could benefit a lot from it: SEMICeu/LinkedDataEventStreams#31 While we didn’t want to close the door on other use cases, I thus do believe a server should have a way to indicate to server that it can guarantee a search tree without cycles, so you don’t need to keep a list of all visited pages and members as part of your state. This should lead to a lower memory footprint and potentially a higher performance. Different options: 1. Annotating the relations, cfr. the SubsetRelations proposal ↑As proposed by @xdxxxdx, we would somehow annotate the relations with a specific traversal strategy that will be guaranteed to be a search tree by the server. However, in this case I don’t see the benefit of adding sibling or parent relations at all, as you wouldn’t be able to use search forms with this proposal anymore either. I’m thus not a big fan of the proposed solution. 2. Annotating the tree:Node to say it’s a disjoint subgraph from hereWhen it’s an entry node, you don’t have history yet. If however you follow a link to a node that is again linked using Instead of We could propose a new property, for example |
|
Hello @pietercolpaert, How to use
|
|
@xdxxxdx I’m not entirely sure what you mean here. Let’s have a call about this before the next CG meeting, and present our common understanding there. Afterwards we can update and comment here a motivation for a potential design decision |
|
During the 11th TREE CG meeting of 2023-12-20 we discussed a possible resolution for this discussion: Quoting myself from the past:
I refute that today: we can solve this using validation.
Based on our discussions, we said it would make sense that a search form would jump to a page from which not all members can be reached, but explicitly a subset searched for. I agree with that conclusion. This should be added to the spec on traversing relations.
The only use case for not having a search tree we saw so far in implementations would be a double linked list (a single linked list is strictly speaking a search tree). We therefore would make it explicit in the specification for view builders, that In order to maintain backwards compatibility with existing implementations, we would however make it mandatory to still prune relations to the previous page. Impacted issue is certainly how clients can keep state to resume later on, as for example is the case in LDES: SEMICeu/LinkedDataEventStreams#31 |
Isn't this a bit too restrictive? The way I interpret it, it also implies that two collections for example can't share a fragment? graph TD;
C1-->B;
C2-->B;
|
I think that’s left open It’s indeed a bit restrictive as you won’t be able to have 2 nodes pointing at the same other node - but I haven’t seen use cases so far that would require that. |
|
To be proposed in a PR:
|
Fixing #85: it’s a search tree now and not a graph and new meaning to tree:view
Hope this is a clear explanation of the idea from @sandervd
Introduce a subclass of
tree:Relatione.g.tree:SubsetRelationto Identify the Minimum spanning tree inside a graph, which could facilitate the search from the perspective of a (tree) client.e.g.
Diagram -1
As presented in diagram-1, when the Client starts from
tree:Nodemarked as 1, the client could only follow thetree:SubsetRelationto arrive at alltree:Node.Diagram - 2
If the client starts from the
tree:Nodemarked as 2 (as shown in Diagram - 2), this implies the client is only interested in the node under the subset condition oftree:SubsetRelationmarked as 3 (Diagram - 2)In practice, Current available tree:Relation(s):
tree:PrefixRelation,tree:SubstringRelation,tree:SuffixRelation,tree:GreaterThanRelation,tree:GreaterThanOrEqualToRelation, etc.. can be typed astree:SubsetRelationwhen it is the case.The text was updated successfully, but these errors were encountered: