Stream: mapping-framework
Topic: Where are the DAGs?
Justin Pombrio (Jul 17 2019 at 19:08):
Hi, I'm new here, but hoping I can just jump right in and ask a question!
The FHIR mapping spec says it "describes how one set of Directed Acyclic Graphs (an instance) is transformed to another set of directed acyclic graphs". What is this referring to? I thought that FHIR resources were tree-shaped, i.e. that an element of a resource always has exactly one parent element. Or if it's talking about fhir references, can't there be cycles in the references, thus making it not be a directed acyclic graph?
Diego Bosca (Jul 17 2019 at 20:00):
Every tree is a DAG (we are talking about polytrees actually, which even with multiple parents they can be interpreted as DAGs)
Justin Pombrio (Jul 17 2019 at 20:08):
What's the edge relation for which FHIR trees are polytrees? If (A, B) is in the set of edges, I was expecting that to mean that A and B are elements of a resource, and B is nested under A in the structure diagram. (So, for example, (name, given) would be an edge in HumanName.) Is the edge relation something else?
Diego Bosca (Jul 18 2019 at 07:57):
Each class/resource can be seen as a graph node (or tree node) and every attribute that relates classes/resources is a directed edge. The same applies for xml btw
Josh Mandel (Jul 18 2019 at 13:45):
From the perspective of FHIR, I think the documentation could have been written with "trees" in place of "DAGs". Would that that have been clearer @Justin Pombrio ? (And for others here: Would that description leave out important capabilities or goals of the language?)
Justin Pombrio (Jul 18 2019 at 14:57):
@Diego Bosca Since references can contain cycles, I'm guessing you don't mean to include them in "attributes that relate classes/resources"? Could you give an example of a resource that has two parents, by edges that aren't references? (Sorry if this is this is an easy thing I'm just missing because I don't know FHIR very well yet.)
@Josh Mandel My understanding was that each FHIR resource was a tree, and that resources related to one another primarily via references, which form a (possibly cyclic) graph. So I was expecting that sentence to say either "tree" or "graph", but not "DAG". (With "trees" being more appropriate since the mapping language is mostly dealing with transforming individual resources.) But if I'm wrong about that, it's important that the docs say the correct thing.
Diego Bosca (Jul 18 2019 at 15:05):
yeah, but when you reference something you are not including the class, but a reference to a given object (it literally is a class of 'Reference' type). In a data instance, when you arrive to a reference you don't actually put it's contents there, so references are leaf nodes in your tree
Justin Pombrio (Jul 18 2019 at 15:20):
Yes, I understand. You said that FHIR resources form a polytree, via edges that are "attributes that relate classes/resources", right? If so, it's possible for a resource to have two parents. Can you give an example of a resource that has two parents?
Diego Bosca (Jul 18 2019 at 15:44):
polytrees, which have less constraints than trees (e.g. can have multiple parents), are equivalent to DAGs. Trees in most standards (FHIR included) have more constraints (they only have one parent, etc.) so they are still equivalent to DAGs
Justin Pombrio (Jul 18 2019 at 16:01):
Ok, so "tree" would be the appropriate thing to say. (As Diego points out, every tree is a DAG. But developers need to know what they have to deal with in the worst case, and they don't have to deal with an element with two parents. And regardless, it's always better to use the more precise term.)
Josh Mandel (Jul 18 2019 at 17:20):
I'm agreeing with you @Justin Pombrio (and tried to express this above; apologies if I was unclear) -- as long as nobody else thinks the mapping language actually applies to non-tree DAGs, we should just be saying "tree".
Justin Pombrio (Jul 25 2019 at 20:53):
Thanks @Josh Mandel. Yeah, you were clear :-). I think "tree" or "forest" would make sense; "DAG" just scared me because I thought I was missing something about how FHIR resources worked.
Josh Mandel (Jul 25 2019 at 21:09):
Great. I added GF#23007 to capture this conversation.
Justin Pombrio (Jul 25 2019 at 21:12):
(deleted)
Grahame Grieve (Jul 25 2019 at 21:14):
hang on. catching up with this topic.... FHIR resources are trees, but the mapping language works on DAGs. That's a clear difference
Justin Pombrio (Jul 25 2019 at 21:16):
Sorry, I accidentally started a new conversation and can't figure out how to delete it. Probably we should continue the other conversation to avoid confusion, though I don't know Zulip well yet.
Grahame Grieve (Jul 25 2019 at 21:18):
fixed.
Justin Pombrio (Jul 25 2019 at 21:18):
@Grahame Grieve You say that the mapping language works on DAGs. What do you mean by that: what are the edges? If the edges are fhir references, then they can form cycles, and so it's a general graph, not a DAG.
Grahame Grieve (Jul 25 2019 at 21:18):
references are not edges. But I don't understand your question
Grahame Grieve (Jul 25 2019 at 21:19):
FHIR resources are trees, with a designated starting point, and a single heirarchy.
Justin Pombrio (Jul 25 2019 at 21:19):
What are the edges of the DAGs that the language works on?
Grahame Grieve (Jul 25 2019 at 21:19):
but the mapping language works with DAGs, and some of the other content that you map from/to are not trees, they are DAGS
Grahame Grieve (Jul 25 2019 at 21:19):
I don't understand 'what are the edges'
Justin Pombrio (Jul 25 2019 at 21:20):
What's an example of other content that's a DAG?
Grahame Grieve (Jul 25 2019 at 21:21):
I worked with someone who was working with a custom XML format where id links were redirections that were followed internally.
Grahame Grieve (Jul 25 2019 at 21:22):
HL7 has never published a poly-heirarchy, nor has openEHR or IHE, to my knowledge, but I have seen them in private formats - programmers fall into them naturally and do not have the experience not to until too late
Justin Pombrio (Jul 25 2019 at 21:23):
But the format didn't allow cycles? I'm surprised because "the mapping language works on DAGs" suggests that if you give it a DAG, it can transform it into another DAG, but is not capable of accidentally transforming it into a graph, and I didn't think that was easy to achieve.
Grahame Grieve (Jul 25 2019 at 21:26):
The input format did not make use of cycles. I cannot say whether it allowed cycles or not at some level in the definition. In terms of output.... I guess the mapping language could produce a true graph, not a DAG, but I'm not sure exactly how that would work in practice. I'd have to investigate
Justin Pombrio (Jul 25 2019 at 21:29):
I don't mean to send you off on a whole investigation! The important thing, at least to me, is that the docs scared me into thinking that maybe fhir resources weren't trees. A parenthetical note saying that while the language is more general, it typically acts on fhir resources---which are trees---would clear up the confusion.
Grahame Grieve (Jul 25 2019 at 21:31):
I agree with that. I added a note to the task
Justin Pombrio (Jul 25 2019 at 21:32):
Thanks for diving so deep into one sentence with me.
Grahame Grieve (Jul 25 2019 at 21:33):
no problems
Last updated: Apr 12 2022 at 19:14 UTC
