PML Tree Query

• Query and report language
• Two engines
  • SQL
  • Perl ([bnj]tred)
• Several clients
  • Browser (http://euler.ms.mff.cuni.cz:8090/)
  • TrEd
  • CLI

The SQL engine requires the data to be converted to SQL and loaded into a database → stable datasets.

The Perl engine is slow, but works directly with the data files → data in progress.

The Query Language

• Selecting all occurrences of nodes with given properties and in given relations (tree topology, cross-referencing, surface ordering, etc.)
• (Un)bounded iteration of relations (e.g. descendant{1,3}, coref_gram.rf{1,}, sibling{-1,1}, etc.)
• Multi-layered or aligned treebanks with structured attribute values
• Quantified or negated subqueries (e.g. “find all clauses with exactly three objects but no subject”)
• References (e.g. “find a parent and child that have the same case but different number”)
• Natural textual and graphical representation of the query
• Sublanguage for postprocessing and generating reports (filtering, grouping, aggregating, and sorting)
• Regular expressions, basic arithmetic and string operations

Simplest Queries

Search for a given word.

node $be := [
    lemma = "be"
]

Search for all subjects.

node $subj := [
    deprel = "SBJ"
]

Simple Reports

Count the occurrences.

node $subj := [
    deprel = "SBJ"
]
>> give count()

Structure and Aggregation

Group the results by a value of an attribute.

node $parent := [
    child node $subj := [
        deprel = "SBJ"
    ]
]
>> for $parent.pos
   give $1, count()
   sort by $2

• How can a noun be parent of a subject?

Relations

We can use the inverted relation.

node $subj := [
    deprel = "SBJ",
    parent node $parent := []
]
>> for $parent.pos
   give $1, count()
   sort by $2

Relations (2)

• child, parent
• descendant, ancestor
• same-tree-as
• sibling
• order-precedes, order-follows
• depth-first-precedes, depth-first-follows
• References
• Implementation specific

References, Quantifying Relations

Find two instances of the same lemma, separated by at most three words.

node $n1 := [
    order-precedes{1,4} node $n2 := [
        lemma = $n1.lemma
    ]
]

Predicates

• (!) =, ~, ~*, in
• <, >, <=, >=

For example, to select all nouns in the PDT:

a-node $noun := [
     m/tag ~ "^N"
]

Or, using a function:

a-node $noun := [
     substr(m/tag, 0, 1) = "N"
]

Not possible for English—tags are not positional.

Predicates (2)

node $noun := [
     pos ~ "^N"
]
>> for $noun.pos
   give $1, count()
   sort by $2 desc

NIL is not a noun!

node $noun := [
     pos in { "NN", "NNS", "NNP", "NNPS" }
]

Operators and Functions

Operators

+, -, *, div, mod, &

Functions

• descendants(), sons()…
• length(), substr(), match()…
• round(), exp(), sqrt()…
• count(), sum(), max(), ratio()…

Multi-Layered Treebanks

Function of Actor

t-node $act := [
    functor = "ACT",
    a/lex.rf a-node $a := [ ]
]
>> for $a.afun
   give $1, count()
   sort by $2

Multi-Layered Treebanks (2)

Reversed Dependency

t-node [
    a/lex.rf $a_child,
    echild t-node [ a/lex.rf $a_parent ]
];
a-node $a_parent := [
    echild a-node $a_child := [  ]
];

Negation

Atomic

cat = 'NP'

∃ x ∈ cat ( x = 'NP' )

cat != 'NP'

∃ x ∈ cat ( x ≠ 'NP' )

! cat = 'NP'

∀ x ∈ cat ( x ≠ 'NP' )

* cat = 'NP'

∀ x ∈ cat ( x = 'NP' )

Same for in, ~, etc.

Existencial

nonterminal [ 0x descendant terminal [pos = "NN"]]

Projectivity

A tree is projective

if and only if
for any two nodes connected by an edge all the nodes between them are descendants of some of the two.

Non-Projectivity

node $upper := [ 
    same-tree-as $between,
    child node $lower := [ ] ];
node $between := [
    ! ancestor $upper,
    ( ( order-precedes $upper 
        and order-follows $lower)
      or (order-follows $upper
          and order-precedes $lower) ) ]

$upper is not an ancestor of $between

Counting Non-Projectivities: The Trap

• Simple count() returns 15741.
• For one edge, there can be several $between nodes.
• The correct way is to use distinct:

  >> give distinct $lower
  >> give count()
  

• Chaining the filters.

More Complex Example

Verb Clause without a Subject

a-node [
    $$     = $aux and m/tag ~ '^V[^fs]'
    or $$ != $aux and m/tag ~ '^V[sf]',
    0x echild a-node [ afun = 'Sb' ], 
    ?  echild a-node $aux := [
        afun  = 'AuxV',
        m/tag ~ '^V[^f]'
] ]

Word Order Typology

For German

node $p := [
    substr(pos, 0, 1) = "V", 
    ? child node $ch := [
        deprel in { "SB", "OA", "OC", "OA2", "OP" }
] ]
>> give $p.xml:id,
        if($p = $ch,
           if($p.deprel = "ROOT", "V", "v"),
           substr($ch.deprel, 0, 1)),
        $ch.order
>> give distinct $1, concat($2, "" over $1 sort by $3)
>> give substitute($2, "([OS])\\1+", "\\1", "g")
>> filter ($1 ~ "O" and $1 ~ "S")
>> for $1
   give $1, if($1 ~ "V", count(), 0), if($1 ~ "V", 0, count())
>> give $1, if($1 ~ "V", 0, 1),
        percnt(ratio($2 over all) + ratio($3 over all), 3)
   sort by $2, $3 desc
>> give $1, $3 & " %"

Word Order Typology

For German (2)

Thank you.

Questions?