Quote: "When one door closes another door opens; but we so often look so long and so regretfully upon the closed door, that we do not see the ones which open for us." – Alexander Graham Bell

// An index structure for the graph.

First, we transfer the graph into a relational table. The basic structure of such a table is like: 

Attribute:	node id	edge label list	parent node id
Semantics:	the identifier of the node	a set of labels for the edges connecting this node and its parent	the identifier of the parent of this node

Note: There are three attributes in the table composing the relation depicted by the graph. 

As far as a path query is concerned, we could use split-join operations to do the evaluation. When evaluating the query, we must enforce the constraints of a valid path defined in the section (***) on the results. Meantime, a table is also constructed for easily performing the compatibility check. The structure of the table is as follows:

Attribute:	node/complex_assertion id	result id list
Semantics:	the identifier of the node	results containing this node

Note: The element of the list for results  in the table has a pair structure <result_id, node_position>. The first item in the pair denotes the identifier of the result containing the very node, and the later one gives the position of the node in the corresponding result. ( Is this table really necessary??? )

Finally, we organize all results for a path query in a table like: 

Attribute:	result id	simple format	full format	Shared node list
Semantics:	the identifier of the result	the result without edges or functional nodes, just for the user.	the result with edges and functional nodes, used for compatibility checks.	the set of node ids or complex assertion ids which are shared with other results. (it is computed from the table above.)

Note: the user asks for the compatibility of any two results with the simple format.