Yesterday we started discussing incremental graph transformations:
Incremental Graph Transformations:
First, let us review the API for requesting graph transformations. They generally work in the following manner: The following example was taken from Microsoft Graph:
Initially a request is made for the resource
Subsequent pages of the resource are retrieved using a keyword like nextLink
Final response with nextLink indicates end of the original collection which is usually from a snapshot
The delta query is then issued with the deltaLink keyword that enables additions, deletions or updates to be queried
The delta query needs to detect the incremental changes in the graph.
One way to provide incremental updates is to keep track of graph transformations in materialized views with the help of transformation rules that can be pattern matched with the graph.
A graph transformation rule consists of a (LHS, RHS, NAC) where
LHS : left hand side graph
RHS: right hand side graph
NAC: Negative application condition
The matching results from LHS to RHS where NAC prohibits the presence of certain objects and links.
The rules are formed using metamodels and instance models:
The metamodel is represented by type graph where the nodes are called classes A class may have attributes and demonstrates inheritance and associations.
The instance model describes instances of the metamodels where the nodes are objects and the edges are links
A class is mapped to a table with a single column where (class(I)) stores the identifiers of the objects of the specified class
An association has three columns (assoc(I,S,T)) which contains identifiers for the link, source and target objects
An attribute is mapped to a table with two columns (attr(I,V)) for the object identifier and the attribute value
By defining the locations in the graph for the application of the rules, the tables itself go through very little changes.
#codingexercise
Given two sorted arrays of vastly different lengths, what is the lowest complexity to find intersection elements - Find the Math.Max(start1, start2) and Math.Min(end1, end2) for the values in the two arrays. Then for this sub-range in the smaller array, perform binary search in the longer array. If the lengths of the two arrays are comparable, sequentially traverse elements in both array in sorted order and printing elements that appear in both arrays.
Incremental Graph Transformations:
First, let us review the API for requesting graph transformations. They generally work in the following manner: The following example was taken from Microsoft Graph:
Initially a request is made for the resource
Subsequent pages of the resource are retrieved using a keyword like nextLink
Final response with nextLink indicates end of the original collection which is usually from a snapshot
The delta query is then issued with the deltaLink keyword that enables additions, deletions or updates to be queried
The delta query needs to detect the incremental changes in the graph.
One way to provide incremental updates is to keep track of graph transformations in materialized views with the help of transformation rules that can be pattern matched with the graph.
A graph transformation rule consists of a (LHS, RHS, NAC) where
LHS : left hand side graph
RHS: right hand side graph
NAC: Negative application condition
The matching results from LHS to RHS where NAC prohibits the presence of certain objects and links.
The rules are formed using metamodels and instance models:
The metamodel is represented by type graph where the nodes are called classes A class may have attributes and demonstrates inheritance and associations.
The instance model describes instances of the metamodels where the nodes are objects and the edges are links
A class is mapped to a table with a single column where (class(I)) stores the identifiers of the objects of the specified class
An association has three columns (assoc(I,S,T)) which contains identifiers for the link, source and target objects
An attribute is mapped to a table with two columns (attr(I,V)) for the object identifier and the attribute value
By defining the locations in the graph for the application of the rules, the tables itself go through very little changes.
#codingexercise
Given two sorted arrays of vastly different lengths, what is the lowest complexity to find intersection elements - Find the Math.Max(start1, start2) and Math.Min(end1, end2) for the values in the two arrays. Then for this sub-range in the smaller array, perform binary search in the longer array. If the lengths of the two arrays are comparable, sequentially traverse elements in both array in sorted order and printing elements that appear in both arrays.
No comments:
Post a Comment