/usr/share/perl5/RDF/Query/BGPOptimizer.pm is in librdf-query-perl 2.918-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 | # RDF::Query::BGPOptimizer
# -----------------------------------------------------------------------------
=head1 NAME
RDF::Query::BGPOptimizer - Optimizer for ordering the joins of triple patterns in a BGP
=head1 VERSION
This document describes RDF::Query::BGPOptimizer version 2.918.
=head1 STATUS
This module's API and functionality should be considered unstable.
In the future, this module may change in backwards-incompatible ways,
or be removed entirely. If you need functionality that this module provides,
please L<get in touch|http://www.perlrdf.org/>.
=head1 METHODS
=over 4
=cut
package RDF::Query::BGPOptimizer;
use strict;
use warnings;
use Data::Dumper;
use List::Util qw(reduce);
use Scalar::Util qw(blessed reftype refaddr);
use RDF::Query::Error qw(:try);
######################################################################
our ($VERSION);
BEGIN {
$VERSION = '2.918';
}
######################################################################
=item C<< ordered_triples ( $context, @triples ) >>
Returns a list of triples, ordered so as to optimize a left-deep join plan based
on the frequency counts provided by the underlying model.
=cut
sub ordered_triples {
my $self = shift;
my $context = shift;
my @triples = @_;
my $model = $context->model;
my %vars;
my %seen;
my @weighted = map {
my $triple = RDF::Query::Plan::Triple->new( $_->nodes );
[ $_, $self->_cost( $triple, $context ) ]
} @triples;
my %triples = map { refaddr($_->[0]) => $_ } @weighted;
my @ordered = sort { $a->[1] <=> $b->[1] } @weighted;
foreach my $t (@triples) {
my @vars = $self->_triple_vars( $t );
foreach my $name (@vars) {
push( @{ $vars{ $name } }, $t ) unless ($seen{ $name }{ refaddr($t) }++);
}
}
my %edges;
foreach my $name (keys %vars) {
my @triples = @{ $vars{ $name } };
foreach my $t (@triples) {
my $ta = refaddr($t);
foreach my $u (@triples) {
my $ua = refaddr($u);
next if ($ta == $ua);
$edges{ $ta }{ $ua } = $u;
}
}
}
my @final;
my %used;
my $start = shift(@ordered);
$used{ refaddr($start) }++;
push(@final, $start);
my @seen = refaddr($start->[0]);
my $count = 0;
while (@ordered) {
if (++$count > scalar(@triples)) {
die "loop in BGPOptimizer (?)";
}
my @frontier = grep { not($used{refaddr($_)}) } map { $triples{ $_ } } map { keys(%{ $edges{ $_ } }) } @seen;
my @orderedf = sort { $a->[1] <=> $b->[1] } @frontier;
if (@orderedf) {
my $next = shift(@orderedf);
my $addr = refaddr($next);
$used{ $addr }++;
push(@final, $next);
push(@seen, refaddr($next->[0]));
@ordered = grep { refaddr($_) != $addr } @ordered;
} else {
my $next = shift(@ordered);
my $addr = refaddr($next);
$used{ $addr }++;
push(@final, $next);
push(@seen, refaddr($next->[0]));
}
}
return map { $_->[0] } @final;
}
sub _cost {
my $self = shift;
my $pattern = shift;
my $context = shift;
my $l = Log::Log4perl->get_logger("rdf.query.bgpoptimizer");
my $bf = $pattern->bf( $context );
my $f = ($bf =~ tr/f//);
my $r = $f / 3;
$l->debug( "Pattern has bf representation '$bf'" );
$l->debug( "There are $f of 3 free variables" );
$l->debug( 'Estimated cardinality of triple is : ' . $r );
# round the cardinality to an integer
return int($r + .5 * ($r <=> 0));
}
sub _triple_vars {
my $self = shift;
my $t = shift;
my @nodes = $t->nodes;
my (@vars, %seen);
foreach my $n (@nodes) {
if ($n->isa('RDF::Trine::Node::Variable')) {
my $name = $n->name;
push(@vars, $name) unless ($seen{ $name }++);
}
}
return @vars;
}
1;
__END__
=back
=head1 AUTHOR
Gregory Todd Williams <gwilliams@cpan.org>
=cut
|