I discussed with Dr.Candan about my research on Null Value last afternoon. In the meeting, we decided to put focus on the understanding what our tasks are first of all, based on which we could introduce an indexing structure for the graph representing all assertions in the XML document. 

First of all, the definition and property of the compatibility should be brought up in order to develop a  deep discussion. Basically, the compatibility is kind of property among two objects. In our case, we can say (a) one path instance is compatible with the other path instance, or (b) one path instance is compatible with a set composed of many path instances, or (c) a set of path instances is compatible with the other set. It's easy to understand the relationship of compatibility between two path instances based on the definition we introduced in the paper.  When a set is concerned, such as (b) and (c), each elements in the set should be considered. To satisfy compatibility defined in (b) one path instance should be compatible with every element in the set, and so is (c).  In addition, we call a universe here to be a set of compatible path instances for one path query. 

An operator is defined to represent the compatibility relation among objects, which is ~. 

1. Given a path query q, we have path instances p_1 and p_2. Then, 

• p_1 ~ p_2 iff. both of them satisfy constraints defined by 1-4.

2.  Given a path query q, we have a path instance p' and a set of path instances P = {p_1, p_2, ..., p_N}. Then,

• p_1 ~ P iff. for each p_i in P, p ~ p_i.

3.  Given a path query q, we have two sets of path instances P = {p_1, p_2, ..., p_N} and Q = {q_1, q_2, ..., q_M}. Then, 

• P ~ Q iff for each p_i in P, p_i ~ Q. 

There are three categories of tasks we have to deal with:

Given a path query q, we can get a set of instances of q as P = {p_1, p_2, ..., p_N}. 

1. Compatibility Checking

• Check whether P is a universe, i.e., is there any pair of elements in P which are not compatible.
• Given an instance p' of the query q, decide whether p' ~ P.
• Given an instance p' of the query q, decide whether p' !~ p_i. ('!~' means the 'not compatible') 

Given all instances U = {p_1, p_2, ..., p_N} for a path query q, we can build a set of subsets of U, U = {V_1, V_2, ..., V_M}.  Each subset V_i includes some elements in U, all of which are compatible to each other. 

2. Ranking all instances for a path query based on the compatibility

3. Set operations based on the compatibility