Today we continue reading the paper  "Horton: Online Query Execution Engine For Large Distributed Graphs" by Sarwat, Elnikety, He and Kliot.
This paper talks about large graphs that don't fit on a single server. The paper introduces Horton a graph query execution engine. We were reviewing its architecture.
It has four components  - the graph client library, the graph coordinator, graph partitions and the graph manager.We saw that the implementation was in C# using Codebook graphs. This is a social network application that represents software engineers, software components and their interactions in large software projects.  Codebook manages information about source code with its revisions, documentation and the organizational structure of developers. It can answer queries such as "Who wrote this function?" "what libraries depend on this library", "Whom should I contact to fix this bug"
We review the query processing phases. For example,
"Who wrote the specification for the MethodSquare code ?" translates to query such as
C:\ Horton -query *(Code MethodSquare) MentionedBy WordDocument AuthoredBy Person*
and "Who is the manager of the person who closed or created work item bug #673 ?" translates to
C:\Horton -query "Person Manages Person (Closed | Created) (WorkItemRevision #673)"
The finite state machine for the latter query makes the following changes:
Node_Type = person
Edge_Type = Manages
Node_Type = person
Edge_Type = closed                                         Edge_Type = created
Node_Type =                                                   Node_Type =
WorkItemRevision Node_ID = #673                 WorkItemRevision Node_ID = #673
The above finite state machine has a disjunction for closed and created cases.
If the query were to be optimized a '-query' will be added.
The system reports the execution time of each query. The query result is in the form of graph paths ( a sequence of graph nodes).
#codejam
Given two orientations of the same ominoes as in the earlier posts, determine whether the clockwise or the anticlockwise is the shorter transition from one to the other.
int countl = 0;
for (int i = 0; i < 360; i+=90)
   var temp = rotate_matrix(matrix, i);
   countl += 1;
   if (compareTo(matrix, temp) == 0)
     return count;
countr = 0;
for (int i = 0; i < 360; i+=90)
   var temp = rotate_matrix(matrix, 0-i);
   countr += 1;
   if (compareTo(matrix, temp) == 0)
     return count;
if (countl < countr) return -1;
if (countl > countr) return +1;
if (countl == countr && countl == 0) return -1;
return 0;