Visits: 12
HL7 Graph Walk and Cardinality
Nobuyuki SAMBUICHI
ISO/TC295 Audit data services/SG1 Semantic model Convener
1. Do we care cardinality then?
Yes, cardinality is an important aspect when designing and modeling associations between entities in a system. It defines the number of instances or elements that can be associated with each other. Cardinality provides information about the relationship between entities and helps determine the multiplicity of the association.
Cardinality helps answer questions such as:
How many instances of one entity can be associated with another entity?
Is the association one-to-one, one-to-many, or many-to-many?
Are there any constraints or limitations on the number of associations?
Understanding the cardinality of associations is crucial for accurately representing the relationships between entities and ensuring the integrity and consistency of the system’s data model. It helps in determining the structure of the system, defining navigation paths, and validating data constraints.
2. How cardinality affect graph walk defined in HL7?
In HL7, graph walk refers to the process of traversing through a message structure or data model to access specific data elements or relationships. Cardinality plays a significant role in graph walk as it determines the number of instances or repetitions of an element within the message or data model.
Cardinality affects graph walk in the following ways:
Navigation: Cardinality helps in navigating through the message structure by indicating the number of occurrences of a particular element. It provides information on whether an element is optional (0 or 1 occurrence) or repeatable (multiple occurrences).
Iteration: When cardinality allows for multiple occurrences of an element, graph walk may involve iterating or looping through the available instances to access and process the desired data.
Data Extraction: Cardinality defines the availability and expected number of occurrences of specific data elements. During graph walk, the cardinality helps determine if the required data element is present and accessible within the message. It also guides in handling scenarios where multiple occurrences of an element are expected, such as retrieving a list of values.
Validation: Cardinality is used to validate the conformance of a message against the defined data model. It ensures that the actual occurrence of elements matches the expected cardinality, helping to identify data integrity issues or missing data.
In summary, cardinality influences the graph walk process by guiding navigation, iteration, data extraction, and validation of HL7 messages or data models. It provides essential information for effectively accessing and interpreting the data within the message structure.
3. summarize HL7 graph walk using LIFO queue and cardinality.
10.3.3.1.2 Build the Hierarchical Message Definition
This part of building an HMD is really a pair of steps based on the “currently selected class.” Initially, the root class is selected. The steps are:Step 1: Copy a class from the Refined Message Information Model to the Hierarchical Message Definition.
Step 2: Select another class that is related to the currently selected class through a relationship.
As the Technical Committee repeats these steps, it will “walk” from class to class of the Refined Message Information Model, making its steps along the lines that represent associations. In order to keep its bearings it will maintain a list of the classes that have been selected. As it takes a step to a new class it will add the class name to the list. At certain times, as instructed in the steps below, it will remove the most recent item on the list. This kind of list is often called a LIFO list (for an accounting method for dealing with inventory, last-in, first-out.) It is also called a pushdown stack, a metaphoric reference to the spring-loaded plate carriers used in institutional dining halls, where the new plates added to the top of the stack push down the earlier plates, so the newest plate is taken off the stack first.
Step 1: Copy a class to the HMD and the LIFO.
Copy the class to the HMD. Include all attributes and associations that will or may appear in the message. Conventionally, attributes should be placed before the associations, but this is not a requirement.
Place the selected class on the top of the LIFO list.
Step 2: Find the next class.
The following rules provide guidance regarding the choice of the association to use to step from the current class to the next in the “walk.” Once an association has been used to step from the current class to a new class, do not re-use it unless the current class itself has been reached again by a different association. All selections of associations must be consistent with the intended semantics of the message. This is an important judgment that is made using domain experience and common sense.
The following rules must be applied in the order they are listed. As soon one of them is reached that is applicable, select the class it specifies and return to step 1, above.
Gen-to-Spec. If the current class is a generalization, and if it at least one of its specializations contains information that will be in the message format, or is on a path of associations toward a class that contains such information, then choose the specialized class.
Intimate Mandatory, Singular. If a (1,1) association from the current class is navigable to a class that seems to add information about the current class, then use it next.
Other Mandatory, Singular. Pick any (1,1) association that is navigable to needed information.
Singular. Pick any navigable association that is (0,1) and leads to needed information.
Other. Pick any navigable association that leads to needed information.
None. If none of the above rules apply, cross the current class off the LIFO list. Take the prior class on the LIFO as the “current” class and immediately repeat steps A-G. If you have crossed the last class of the LIFO list, you have finished the process of selecting the classes and associations for the Hierarchical Message Definition.
The sequence of Rules © – (F) leads to message types that seem more coherent to people. If there is doubt or disagreement about which association to pick based on this rule, the committee may ignore rules © – (F) completely and pick any association. The message will have the same information content.
The process of building a Hierarchical Message Definition (HMD) in HL7 involves navigating through the Refined Message Information Model using a LIFO (Last-In, First-Out) list. The LIFO list keeps track of the selected classes during the navigation. Here’s a summary of the process:
Step 1: Copy a class to the HMD and the LIFO list.
Copy the class to the HMD, including all attributes and associations that will or may appear in the message.
Place the selected class on the top of the LIFO list.
Step 2: Find the next class.
Apply the following rules in order until one of them is applicable:
Gen-to-Spec: If the current class is a generalization and its specializations contain information relevant to the message, choose the specialized class.
Intimate Mandatory, Singular: If there is a (1,1) association from the current class that adds information about the current class, use it next.
Other Mandatory, Singular: Choose any (1,1) association that leads to needed information.
Singular: Select any navigable association that is (0,1) and leads to needed information.
Other: Choose any navigable association that leads to needed information.
None: If none of the above rules apply, cross off the current class from the LIFO list and consider the prior class as the new “current” class. Repeat steps A-G.
If all classes in the LIFO list have been crossed off, the process of selecting classes and associations for the HMD is finished.
Note: Rules C-F (Other Mandatory, Singular; Singular; Other) are intended to create more coherent message types. However, if there is doubt or disagreement about which association to choose based on these rules, they can be ignored, and any association can be picked. The information content of the message will remain the same.
By following this process, the HMD can be constructed systematically by traversing the Refined Message Information Model using a LIFO list and selecting appropriate classes and associations based on the defined rules.
4. can you write python program perform graph walk?
Certainly! Here’s an example of a Python program that performs a graph walk using a LIFO queue:
from collections import deque
def graph_walk(graph, start_node):
visited = set()
stack = deque()
stack.append(start_node)
while stack:
current_node = stack.pop()
if current_node not in visited:
visited.add(current_node)
# Process current node
print("Visiting node:", current_node)
# Add unvisited neighbors to the stack
neighbors = graph[current_node]
for neighbor in neighbors:
if neighbor not in visited:
stack.append(neighbor)
# Example graph represented as an adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': [],
'E': ['F'],
'F': []
}
# Starting node for the graph walk
start_node = 'A'
# Perform graph walk
graph_walk(graph, start_node)In this example, we have a graph represented as an adjacency list. The graph_walk function performs the graph walk using a LIFO queue implemented as a deque. It starts from a specified starting node and visits each node in the graph, printing its value.
You can modify the code to fit your specific graph structure and customize the processing logic inside the while loop according to your requirements.
5. Can you handle following graph?
graph = {
{ 'name':'A',
'association': [
{ 'name':'B',
'cardinality':'0..1'
},
{ 'name':'C',
'cardinality':'1..*'
}
]
},
{ 'name':'B',
'association': [
{ 'name':'D',
'cardinality':'1..1'
}
]
},
{ 'name':'C',
'association': [
{ 'name':'E',
'cardinality':'1..1'
}
]
},
{ 'name':'D',
'association': [ ]
},
{ 'name':'E',
'association': [
{ 'name':'F',
'cardinality':'1..1'
}
]
},
{ 'name':'F',
'association': [ ]
}
}Certainly! Here’s an updated version of the Python program that handles the provided graph:
The code provided by ChatGPT is problematic and after several attempts the code looks like this:
def dfs(graph, start_node, visited=None):
if visited is None:
visited = set()
visited.add(start_node['name'])
print("Visiting node:", start_node['name'])
for neighbor in start_node['association']:
if neighbor['name'] not in visited:
dfs(graph, find_node(graph, neighbor['name']), visited)
def find_node(graph, node_name):
for node in graph:
if node['name'] == node_name:
return node
return None
# Example graph represented as a list of dictionaries
graph = [
{ 'name':'A',
'association': [
{ 'name':'B',
'cardinality':'0..1'
},
{ 'name':'C',
'cardinality':'1..*'
}
]
},
{ 'name':'B',
'association': [
{ 'name':'D',
'cardinality':'1..1'
}
]
},
{ 'name':'C',
'association': [
{ 'name':'E',
'cardinality':'1..1'
}
]
},
{ 'name':'D',
'association': [ ]
},
{ 'name':'E',
'association': [
{ 'name':'F',
'cardinality':'1..1'
}
]
},
{ 'name':'F',
'association': [ ]
}
]
# Starting node for the graph walk
start_node = find_node(graph, 'A')
# Perform graph walk using Depth-First Search (DFS)
dfs(graph, start_node)This code results:
Visiting node: A
Visiting node: B
Visiting node: D
Visiting node: C
Visiting node: E
Visiting node: F6. Python program perform HL7 Graph walk
#!/usr/bin/env python3
# coding: utf-8
#
# generate Audit Data Collection Hierarchy data model from Semantic model CSV
#
# designed by SAMBUICHI, Nobuyuki (Sambuichi Professional Engineers Office)
# written by SAMBUICHI, Nobuyuki (Sambuichi Professional Engineers Office)
#
# MIT License
#
# (c) 2023 SAMBUICHI Nobuyuki (Sambuichi Professional Engineers Office)
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
import os
import csv
DEBUG = True
VERBOSE = True
SEP = os.sep
base = './semantic/'
object_class_file = 'RIM.csv' # Added line item details
hierarchy_file = 'hierarchy.csv'
selectd_class = ['GL Header']
LIFOlist = []
hierarchicalModel = []
def file_path(pathname):
if SEP == pathname[0:1]:
return pathname
else:
pathname = pathname.replace('/', SEP)
dir = os.path.dirname(__file__)
new_path = os.path.join(dir, pathname)
return new_path
def parseClass(classTerm):
#Step 1: Copy a class to the hierarchical logical data model and place it on the top of
# the LIFO list.
LIFOlist.append(classTerm)
if DEBUG: print(f'- parseClass({classTerm} {LIFOlist})')
classObject = objectClassDict[classTerm]
attributes = classObject['attributes']
hierarchicalModel.append({'level':len(LIFOlist),'data':classObject})
# A. Copy the class to the hierarchical logical data model.
# Copy all properties and associations to the hierarchical logical data model.
# Conventionally, properties not related to the associated object class should be placed
# before them,
# but this is not a requirement.
for id,attr in attributes.items():
if len(id)>0 and 'AS'!=attr['bie'][:2]:
hierarchicalModel.append({'level':1+len(LIFOlist),'data':attr})
# B. Place the selected class on the top of the LIFO list.
# Step 2: Find the next class.
# The following rules provide guidance on choosing the association,
# which is a property that has the associated object class defined,
# to use for stepping from the current class to the next in a "walk".
# Once an association has been used to step from the current class to a new class,
# do not re-use it unless the current class itself has been reached again by a different
# association.
# All selections of associations must be consistent with the intended semantics of the
# data.
# The following rules should be applied in the order they are listed.
# As soon one of them is reached that is applicable, select the class it specifies and
# return to step 1, above.
# A. Gen-to-Spec.
# If the current class is a generalization,
# and if it at least one of its specializations contains information that will be in the
# message format or is on a path of associations toward a class that contains such
# information, then choose the specialized class.
if 'SP'==classObject['bie'][:2]:
selectedClassTerm = classObject['associatedClass']
if not selectedClassTerm in LIFOlist:
parseClass(selectedClassTerm)
specialClasses = [cls for cls in attributes.values() if 'SP'==cls['bie'][:2]]
for attr in specialClasses:
selectedClassTerm = attr['associatedClass']
if not selectedClassTerm in LIFOlist:
parseClass(selectedClassTerm)
# #
# if 'AS'==classObject['bie'][:2]:
# hierarchicalModel.append({'level':1+len(LIFOlist),'data':classObject})
# B. Intimate Mandatory, Singular.
# If a (1,1) association from the current class is navigable to a class that seems to
# add information about the current class, then use it next.
# C. Other Mandatory, Singular.
# Pick any (1,1) association that is navigable to needed information.
if 'AS'==classObject['bie'][:2] and '1..1'==classObject['card']:
selectedClassTerm = classObject['associatedClass']
if not selectedClassTerm in LIFOlist:
parseClass(selectedClassTerm)
mandateClasses = [cls for cls in attributes.values()
if 'AS'==cls['bie'][:2] and '1..1'==cls['card']]
for attr in mandateClasses:
selectedClassTerm = attr['associatedClass']
if not selectedClassTerm in LIFOlist:
hierarchicalModel.append({'level':1+len(LIFOlist),'data':attr})
parseClass(selectedClassTerm)
# D. Singular.
# Pick any navigable association that is (0,1) and leads to needed information.
if 'AS'==classObject['bie'][:2] and '0..1'==classObject['card']:
selectedClassTerm = classObject['associatedClass']
if not selectedClassTerm in LIFOlist:
hierarchicalModel.append({'level':1+len(LIFOlist),'data':attr})
parseClass(selectedClassTerm)
singularClasses = [cls for cls in attributes.values()
if 'AS'==cls['bie'][:2] and '0..1'==cls['card']]
for attr in singularClasses:
selectedClassTerm = attr['associatedClass']
if not selectedClassTerm in LIFOlist:
hierarchicalModel.append({'level':1+len(LIFOlist),'data':attr})
parseClass(selectedClassTerm)
# E. Other.
# Pick any navigable association that leads to needed information.
if 'AS'==classObject['bie'][:2] and '..*'==classObject['card'][1:]:
selectedClassTerm = classObject['associatedClass']
if not selectedClassTerm in LIFOlist:
parseClass(selectedClassTerm)
otherClasses = [cls for cls in attributes.values()
if 'AS'==cls['bie'][:2] and '..*'==cls['card'][1:]]
for attr in otherClasses:
selectedClassTerm = attr['associatedClass']
if not selectedClassTerm in LIFOlist:
hierarchicalModel.append({'level':1+len(LIFOlist),'data':attr})
parseClass(selectedClassTerm)
# F. None. If none of the above rules apply, cross the current class off the LIFO list.
# Take the prior class on the LIFO as the “current” class and immediately repeat steps
# A-E.
# If you have crossed the last class of the LIFO list, you have finished the process of
# selecting the classes and associations for the hierarchical logical data model.
# The sequence of Rules (C) – (F) leads to message types that seem more coherent to
# people.
# If there is doubt or disagreement about which association to pick based on this rule,
# the committee may ignore rules (C) – (F) completely and pick any association.
# The message will have the same information content.
LIFOlist.pop(-1)
if DEBUG: print(f'LIFO list {LIFOlist}')
if __name__ == '__main__':
objectClassDict = {}
entries = {}
object_class_file = f'{base}{object_class_file}'.replace('/', SEP)
object_class_file = file_path(object_class_file)
header = ['bie','id','level','card','classTerm','propertyTerm','representation','associatedClass']
with open(object_class_file, encoding='utf_8', newline='') as f:
reader = csv.DictReader(f, fieldnames=header)
next(reader)
attributes = []
detailsClass = set()
for row in reader:
bie = row['bie']
if ('CC'!=bie[-2:] and 'BIE'!=bie[-3:]) or len(bie)>5:
continue
classTerm = row['classTerm'].replace(u'\xa0', ' ').replace(' ',' ').strip()
propertyTerm = row['propertyTerm'].replace(u'\xa0', ' ').replace(' ',' ').strip()
associatedTerm = row['associatedClass'].replace(u'\xa0', ' ').replace(' ',' ').strip()
id = row['id']
if bie in ['ACC','ABIE','SPCC','SPBIE']:
if not classTerm in objectClassDict:
objectClassDict[classTerm] = row
objectClassDict[classTerm]['attributes'] = {}
else:
objectClassDict[classTerm]['attributes'][id] = row
objectClassDict[classTerm]['attributes'][id]['classTerm'] = classTerm
objectClassDict[classTerm]['attributes'][id]['associatedClass'] = associatedTerm
if 'AS'==bie[:2] and 'has'==propertyTerm[:3]:
detailsClass.add(associatedTerm)
# selectd_class = objectClassDict.keys()
for classTerm in selectd_class:
if classTerm in detailsClass:
continue
parseClass(classTerm)
hierarchy_records = []
for entry in hierarchicalModel:
level = entry['level']
data = entry['data']
record = {}
for key in header:
record[key] = data[key]
record['level'] = str(level)
hierarchy_records.append(record)
hierarchy_file = f'{base}{hierarchy_file}'.replace('/', SEP)
hierarchy_file = file_path(hierarchy_file)
with open(hierarchy_file, 'w', encoding='utf_8', newline='') as f:
writer = csv.DictWriter(f, fieldnames=header)
writer.writeheader()
writer.writerows(hierarchy_records)
print(f'** END {hierarchy_file}')
