6.2 Derived node relations

In queries, one wants to refer to indeterminate portions of a graph. Therefore, generalized notions of dominance and precedence ('wildcards') are necessary. Furthermore, certain convenient abbreviations should be introduced like a sibling operator.

Dominance

Dominance in general means that there is a path from one node to another one via a connected series of direct dominance relations. The distance of a dominance relation is the length of the path between the two nodes, i.e. the number of direct dominance relations to be traversed. The minimum distance is 1, i.e. in TIGERSearch, a node does not dominate itself.

We introduce the following generalizations of the labelled direct dominance relation >L:

> unlabelled direct dominance
>* dominance (minimum distance 1)
>n dominance with distance n (n>0)
>m,n dominance with distance between m and n (0<m<n)
>@l leftmost terminal successor ('left corner')
>@r rightmost terminal successor ('right corner')
!>L negated labelled direct dominance
!> negated unlabelled direct dominance
!>* negated dominance
!>n negated dominance, distance n
!>m,n negated dominance, distance m...n (0<m<n)
!>@l negated left corner
!>@r negated right corner

For unlabelled edges, the label is considered to be unspecified, i.e. an unlabelled edge can match any edge.

The left corner resp. the right corner relation is reflexive, i.e. the leftmost resp. rightmost successor of a leaf node is the leaf node itself.

For the example tree in subsection 6.1, the following relations hold:

#n1 >* #n4
#n1 >2 #n4
#n1 >@l #n4
#n4 >@l #n4

Concerning the negated node relations, remember that variables are bound existentially at the outermost formula level. For example, the following query has to be read as 'find a syntax graph with an NP node and an NE node which are not connected by an NK-edge.'

[cat="NP"] !>NK [pos="NE"]

Precedence

So far, we have only talked about the precedence of leaf nodes. Whereas, for syntax trees, the precedence relation among its inner nodes is obvious, the situation is not clear at all for syntax graphs, which admit crossing edges. For example, the following two figures are different visualizations of the same syntax graph wrt. the arrangement of the nodes #n2 and #n3.

Figure: Precedence of inner nodes, first layout

Figure: Precedence of inner nodes, second layout

There are several alternatives to define the precedence of inner nodes. One could adopt the strict precedence definition of proper trees: A node #n1 precedes a node #n2 if all nodes dominated by #n1 precede all nodes dominated by #n2 (cf. [SteinerKallmeyer2002]), i.e. if the right corner of #n1 precedes the left corner of #n2. Based on this strict definition, there would be no precedence relation at all between the nodes #n2 and #n3 in the first syntax graph shown above.

We decided for a somewhat weaker definition, which admits precedence statements even for overlapping graphs: A node #n1 is said to precede another node #n2 if the left corner of #n1 precedes the left corner of #n2 (left corner precedence).

According to the left corner based definition, node #n2 precedes node #n3 in the first syntax graph shown above. The user may define his own version of precedence as a template (cf. section 9), e.g. with the help of the right corner operator >@r.

The distance n between two non-identical leaf nodes is the number of leaf nodes between these two nodes increased by 1. For example, the distance between two direct neighbour leaves is 1. The distance between two inner nodes #x and #y is the distance between their respective left corners. Two nodes which share the same left corner, do not precede each other. In particular, a node does not precede itself. For the precedence relation, there are the derived operators listed below:

.* precedence (minimum distance 1)
.n precedence with distance n (n>0)
.m,n precedence with distance between m and n (0>m>n)
!.* negated precedence
!.n negated precedence, distance n
!.m,n negated precedence, distance m...n

Sibling relation

Two nodes #n1 and #n2 are siblings if they are directly dominated by the same node #n0, i.e. if they have the same mother node #n0. We use the following writing conventions:

$ siblings
$.* siblings with precedence
!$ negated siblings

We did not include the negated $.* relation since it seems rather counter-intuitive.