Using the Path Index

Inserting and retrieving edges from the chart using path indexing is similar to the general method presented in Section 6.1.2. The first layer of the index is used to insert a mother as an edge into appropriate chart entries, according to the positional keys for the daughters it can match. Along with the mother, its path index key is inserted into the chart.

When searching for a matching edge for a daughter, the search is restricted by the first indexing layer to a single entry in the chart (labeled with the positional index key for the daughter). The second layer restricts searches to the edges that have a compatible path index vector. The compatibility is defined as type unification: the type pointed to by the element $V_{i,j}(n)$ of an edge's vector $V_{i,j}$ should unify with the type pointed to by the element $V_{i,j}(n)$ of the path index vector $V_{i,j}$ of the daughter on position $D_j$ in a rule $R_i$. Therefore, the unification between a mother and a daughter is attempted only when both the positional index keys and the path index vectors are compatible.