| java.lang.Object
 com.hp.hpl.jena.graph.query.SimpleTripleSorter
| SimpleTripleSorter | | public class SimpleTripleSorter implements TripleSorter(Code) | | A TripleSorter for "optimising" queries. The triples of the query are permuted by
moving the "lightest" triples to earlier positions. Within each region of the same
lightness, triples the bind the most variables to their right are preferred. Otherwise
the order is preserved.
The notion of "lightness" makes more concrete triples lighter than less concrete ones,
and variables lighter than ANY. Variables that have been bound by the time their
containing triple is processed weigh just a little.
The notion of "bind the most" is just the sum of occurances of the variables in the
triple in the other triples.
No weighting is applied to predicate position, and no knowledge about the graph
being queried is required.
author:
kers |
| Constructor Summary | |
| public | SimpleTripleSorter()
A public SimpleTripleSorter needs no arguments (we imagine more sophisticated
ones might). | | protected | SimpleTripleSorter(Triple[] triples)
Initialise a working SimpleTripleSorter from the triple array to sort. |
| Method Summary | |
| protected void | accept(Triple t)
Accept a triple as the next element in the result array, note that all its variables are
now bound, and remove it from the list of remaining triples. | | protected int | bc(Node n, Node other)
Answer 1 if nodes are .equals, 0 otherwise. | | protected void | bind(Triple t)
Bind a triple by binding each of its nodes. | | protected void | bind(Node n)
| | protected int | bindingCount(Triple t)
The binding count of a triple is the number of instances of variables in other triples
it would capture if it were to be bound. | | protected int | bindingCount(Triple t, Triple other)
| | protected int | bindingCount(Node n, Triple o)
| | protected List | findLightest(List candidates)
Answer a list of the lightest triples in the candidate list; takes one pass over the
candidates. | | protected Triple | findMostBinding(List candidates)
Answer the first most-binding triple in the list of candidates. | | public Triple[] | sort(Triple[] ts)
Sort the triple array so that more-bound triples come before less-bound triples.
Preserve the order of the elements unless they have to move. | | protected Triple[] | sort()
Sort the triple array so that more-bound triples come before less-bound triples.
Preserve the order of the elements unless they have to move. | | protected int | weight(Triple t)
In this simple sorter, the weight of a triple is the sum of the weights of its nodes.
None of the positions get weighted differently. | | protected int | weight(Node n)
In this simple sorter, concrete nodes weigh nothing. |
| SimpleTripleSorter | | public SimpleTripleSorter()(Code) | | A public SimpleTripleSorter needs no arguments (we imagine more sophisticated
ones might).
|
| SimpleTripleSorter | | protected SimpleTripleSorter(Triple[] triples)(Code) | | Initialise a working SimpleTripleSorter from the triple array to sort. The working
copy has an empty set of bound variables and a mutable (and mutated) list of the
original triple array, in the same order.
|
| accept | | protected void accept(Triple t)(Code) | | Accept a triple as the next element in the result array, note that all its variables are
now bound, and remove it from the list of remaining triples.
|
| bc | | protected int bc(Node n, Node other)(Code) | | Answer 1 if nodes are .equals, 0 otherwise.
|
| bind | | protected void bind(Triple t)(Code) | | Bind a triple by binding each of its nodes.
|
| bindingCount | | protected int bindingCount(Triple t)(Code) | | The binding count of a triple is the number of instances of variables in other triples
it would capture if it were to be bound.
Parameters:
t - the triple to compute the binding count for the total binding count of t with respect to all the triples in remaining |
| bindingCount | | protected int bindingCount(Triple t, Triple other)(Code) | | Answer the binding count of t with respect to some other triple
|
| findLightest | | protected List findLightest(List candidates)(Code) | | Answer a list of the lightest triples in the candidate list; takes one pass over the
candidates.
Parameters:
candidates - the list of triples to select from the light of lightest triples [by weight], preserving order |
| findMostBinding | | protected Triple findMostBinding(List candidates)(Code) | | Answer the first most-binding triple in the list of candidates.
|
| sort | | public Triple[] sort(Triple[] ts)(Code) | | Sort the triple array so that more-bound triples come before less-bound triples.
Preserve the order of the elements unless they have to move. Return
a new permuted copy of the original array. The work is done by a new instance
of SimpleTripleSorter specialised to this triple array (and with helpful state).
|
| sort | | protected Triple[] sort()(Code) | | Sort the triple array so that more-bound triples come before less-bound triples.
Preserve the order of the elements unless they have to move.
The algorithm just repeatedly looks for a lightest triple, moves it into the result
array, and re-weighs triples in the light of the new bindings that makes. Of several
lightest triples, the first is picked [mostly so that it's easier to write the tests].
|
| weight | | protected int weight(Triple t)(Code) | | In this simple sorter, the weight of a triple is the sum of the weights of its nodes.
None of the positions get weighted differently. One might choose to weigh
positions that were more search-intensive more heavily.
Parameters:
t - the triple to be weighed [with respect to the bound variables] the weight of the triple, rising as the triple is more variable |
| weight | | protected int weight(Node n)(Code) | | In this simple sorter, concrete nodes weigh nothing. [This is, after all, computing
rather than building.] ANYs cost the most, because they cannot be bound, and
variable nodes cost a little if they are bound and a lot if they are not.
The rules are
- any concrete node weighs nothing
- a bound variable node weighs something, but a triple which is three bound
variables must weigh less than a triple with an unbound variable
- an ANY node weighs more than an unbound variable node but less than
two unbound variable nodes
Parameters:
n - the node to be weighed [with respect to the bound variables] the weight of the node |
|
|