no.sesat.search.query.parser.alt
Class RotationAlternation

java.lang.Object
  no.sesat.search.query.parser.alt.AbstractAlternation
      no.sesat.search.query.parser.alt.RotationAlternation

All Implemented Interfaces:

Alternation

public final class RotationAlternation
extends AbstractAlternation

SKER-439 - Rotation Alternation

Rotates like-joined DoubleOperatorClauses (forests). Tree rotation on the Query clause heirarchy is expensive, and as clauses are immutable and are reused through a weak-referenced cache map, performing and remembering the rotations directly after tree construction is a performance benefit over repeated on-the-fly rotations.
The memory increase, taking into account the weak-reference maps is (N-1)^2 +2N -2, where N is the number leaf clauses in the forest. From this it can also be shown that the asymptotic complexity is just shy of O(n^2).
XorClauses with Hint.ROTATION_ALTERNATION are used to store these alternations within the query tree.

Typical usecases of these Rotation-variant XorClauses are visitors that are interested in possible combinations, or joins, between leaf clauses, for example the query evaluation and analysis, and the synonym query transformer.

Here's an example of the sequencial rotations on a query clause heirarchy of eight leaf clauses, all eight leaf clauses are joined by DefaultOperatorClause, so there is only one forest to perform rotations on.
The numbers one through to eight represent the eight terms in the query string and hence the eight leaf clauses. In every rotation these leaf clauses refer to the same reused immutable instances.
The letters A through to G represent the DoubleOperatorClauses. In every rotation these are always different instances as their layout of grandchildren differ.
The number of rotations in any forest is always one less than the number of DoubleOperatorClauses in the forest.
The leaf clauses from left to right always remain in order so visitors can be assured that the query string at large remains the same.

To perform each rotation, the iterate, top, bottom, and orphan clause must be all determined. This is indicated in the diagram on the forest before the rotation occurs.

• The iterate starts at the deepest clause and works itself back one each rotation, eg G for the first rotation process, F for the second rotation process, etc.
• The bottom clause is the right-most parent of the iterate clause.
• The top clause is the left-most parent of the bottom clause where its parent inturn does not have parent to the right. There is an exception here, it is allowed for the top clause's parent to be on the right-side when the top is the direct left parent to the bottom.
• The orphan clause is the left child leaf clause to the deepest double operator clause.

The process of rotation is then split into three steps, pre-rotation, post-rotation, and centre-of-rotation. This is indicated in the diagram on the forest after it has been rotated.

• Pre-Rotation, or 'RIGHT-LEANING-LOWER BRANCH ROTATION', is responsible for rotating the double operator clauses from the bottom's parent up til and including the top clause.
• Post-Rotation, or 'LEFT-LEANING-UPPER-BRANCH ROTATION', is the rotation from the orphan's parent (the double operator clause), which is to become the top's (in it's new position) new parent, up til and including the bottom clause.
• Centre-of-Rotation, or 'ORIGINAL TREE ROOT ROTATION', is the reconstruction of the forest above the bottom's new position up til and including the root clause of the forest. This section remains in appearance the same as the previous rotation but must be reconstructed due to differences in how the grandchildren are laid out.

Example usecases of the resulting rotations within the query
The questions begs when is this rotation actually used and to what benefit?

• Query Analysis relies on all possible term combinations to exist with their corresponding tokenPredicates (which must be exact on the boundaries). The analysis does one complete sweep of the query tree, including the rotations, looking for tokenPredicates inaccordance with the rules to create the scores for each rule.
• The ParentFinder class, a utility visitor implementation, contains the method getParents(root, clause).
  While this visitor does not explicitly use the XorClause.ROTATION_ALTERNATION, it simply visits down all branches of the query returning clauses it comes across that a child matching the clause argument.
  Through this utility it is possible to find variations of combinations that a term in the query can be applicable to.
• SynonymQueryTransformer. Has not yet been fully rewritten to utilise the rotations. SKER863 - Rewrite SynonymQueryTransformer to use RotationAlternation
  But it does already use the ParentFinder visitor utility to check if a given clause is inside a given tokenPredicate.
• WhoWhereSplitter is a utility vistor that splits the query into 'where' and 'who' components.
  It relies heavily upon tokenPredicates linked to fast-lists from the query matching servers.
  Since the where component is often defined by either a fullname or companyname predicate which is generally multi-worded, so the class uses the ParentFinder to check if a given clause is inside one of these given tokenPredicates. The use of the ParentFinder is extended within the private method parentsOf(clause).

References:
Binary Tree Rotation
Institute of Standards and Technology - Rotation
Sequence tagging

Version:

$Id: RotationAlternation.java 7225 2009-04-09 00:32:20Z ssmiweve $

Nested Class Summary

Nested classes/interfaces inherited from interface no.sesat.search.query.parser.alt.Alternation

Alternation.Context

Field Summary

Fields inherited from class no.sesat.search.query.parser.alt.AbstractAlternation

context

Constructor Summary

RotationAlternation(Alternation.Context cxt)
Creates a new instance of RotationAlternation.

Method Summary

Clause	alternate(Clause originalRoot) Returns a alternated clause where all child forests contain XorClauses.
protected <T extends UnaryClause> T	createOperatorClause(Clause left, Clause right, T replacementFor)
protected XorClause.Hint	getAlternationHint()

Methods inherited from class no.sesat.search.query.parser.alt.AbstractAlternation

createXorClause, leftChild, leftOpChild, parent, parents, replaceDescendant, replaceOperatorClause, rightChild, rightOpChild

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RotationAlternation

public RotationAlternation(Alternation.Context cxt)

Creates a new instance of RotationAlternation.

Parameters:

cxt -

Method Detail

alternate

public Clause alternate(Clause originalRoot)

Returns a alternated clause where all child forests contain XorClauses. These XorClauses hold all possible rotations for the corresponding forest. Each XorClause always puts the left-leaning rotation as the left child, and the right-leaning rotation (or the next XorClause) as the right child.

Parameters:

originalRoot -

Returns:

createOperatorClause

protected <T extends UnaryClause> T createOperatorClause(Clause left,
                                                         Clause right,
                                                         T replacementFor)

Overrides:

createOperatorClause in class AbstractAlternation

Returns:

getAlternationHint

protected XorClause.Hint getAlternationHint()

Specified by:

getAlternationHint in class AbstractAlternation

Returns:

the XorClause.Hint used during this alternation process.