NAME

PMLTQ::BtredEvaluator - Pure perl evaluator of PML-TQ queries based on headless implementation of TrEd called Btred

VERSION

version 0.8.0

IMPLEMENTATION

1. find in the query graph an oriented sceleton tree, possibly using Kruskal and some weighting rules favoring easy to follow types of edges (relations) with minimum number of potential target nodes (e.g. parent, ancestor a/lex.rf are better than child, descendant or a/aux.rf, and far better then their negated counterparts).

2. Order sibling nodes of this tree by similar algorithm so that all relations between these nodes go from right bottom to left top (using reversing where possible) and the result is near optimal using similar weighting as above. This may be done only for relations not occuring in condition formulas.

3. For each relation between nodes that occurs in a condition formula, assume that the relation is or is not satisfied so that the truth value of the condition is not decreased (whether to take the formula negatively or positively is probably easy to compute since we may eliminate all negations of non-atomic subformulas and then aim for TRUE value of the respective literal; that is, we only count the number of negations on the path from the root of the expression to the predicate representing the relational constraint and assume TRUE for even numbers and FALSE for odd numbers).

The actual truth values of these relations will be verified only after all query nodes have been matched (or maybe for each node as soon as all nodes it refers to have been matched).

4. The query context consists of:

- the node in the query-tree being matched (current query node)

- association of the previously matched query nodes with result node iterators

- information about unresolved relational constraints on already matched nodes

5. the search starts by creating an initial query context and a simple iterator for the root query node matches

6. in each step one of the following cases occurs:

- the iterator for the current query node is empty -> backtrack: return to the state of the context of the previous query node and iterate the associated iterator -> fail if there is no previous query node

- the iterator returns a node:

- check relational constraints depending on this node.
  If any of them invalidates the condition on an already matched node,
  itereate and repeat 6

- if there is a following query node, make it the current query node
  and repeat 6

- otherwise: we have a complete match. Return the match, back-track
  the context to the root-node and iterate the root-node iterator.
  Then repeat 6.

Note: #occurrences are to be implemented as sub-queries that are processed along with other conditions within the simple iterators. The relation predicates from these sub-queries to the out-side trees are treated as predicate relations in complex relations and are only resolved as soon as all required query nodes are matched.

TODO

the code generated from the if() function should read instead (for both node constraint and filter code)

if ( do { # compute condition (using several nested foreach loops if needed) $reslt }) { # condition where if() is replaced by IF_TRUE } else { # condition where if() is replaced by IF_FALSE }

# or:

do { my @varX = do { # compute condition (using several nested foreach loops if needed) $reslt }) ? do { # all IF_TRUE values } : do { # all IF_FALSE values }; foreach $varX (@varX) { # ... } }

if ($clone_before_plan) { use Data::Dumper;$Data::Dumper::Deparse = 1;$Data::Dumper::Maxdepth = 3;print Dumper $query_tree; #$query_tree=Treex::PML::Factory->createFSFormat()->clone_subtree($query_tree); ??????? $query_tree=Treex::PML::FSFormat->clone_subtree($query_tree); }

AUTHORS

• Petr Pajas <pajas@ufal.mff.cuni.cz>

• Jan Štěpánek <stepanek@ufal.mff.cuni.cz>

• Michal Sedlák <sedlak@ufal.mff.cuni.cz>

COPYRIGHT AND LICENSE

This software is copyright (c) 2014 by Institute of Formal and Applied Linguistics (http://ufal.mff.cuni.cz).

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.