line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
# |
2
|
|
|
|
|
|
|
# Copyright (c) 2004-2006 IBM Corporation. |
3
|
|
|
|
|
|
|
# |
4
|
|
|
|
|
|
|
# All rights reserved. This program and the accompanying materials |
5
|
|
|
|
|
|
|
# are made available under the terms of the Eclipse Public License v1.0 |
6
|
|
|
|
|
|
|
# which accompanies this distribution, and is available at |
7
|
|
|
|
|
|
|
# http://www.eclipse.org/legal/epl-v10.html |
8
|
|
|
|
|
|
|
# |
9
|
|
|
|
|
|
|
# File: $Source: /var/lib/cvs/ODO/lib/ODO/Query/RDQL/DefaultHandler.pm,v $ |
10
|
|
|
|
|
|
|
# Created by: Stephen Evanchik( evanchik@us.ibm.com ) |
11
|
|
|
|
|
|
|
# Created on: 12/01/2004 |
12
|
|
|
|
|
|
|
# Revision: $Id: DefaultHandler.pm,v 1.2 2009-11-25 17:53:53 ubuntu Exp $ |
13
|
|
|
|
|
|
|
# |
14
|
|
|
|
|
|
|
# Contributors: |
15
|
|
|
|
|
|
|
# IBM Corporation - initial API and implementation |
16
|
|
|
|
|
|
|
# |
17
|
|
|
|
|
|
|
package ODO::Query::RDQL::DefaultHandler; |
18
|
|
|
|
|
|
|
|
19
|
5
|
|
|
5
|
|
1746
|
use strict; |
|
5
|
|
|
|
|
10
|
|
|
5
|
|
|
|
|
169
|
|
20
|
5
|
|
|
5
|
|
29
|
use warnings; |
|
5
|
|
|
|
|
11
|
|
|
5
|
|
|
|
|
154
|
|
21
|
|
|
|
|
|
|
|
22
|
5
|
|
|
5
|
|
47
|
use ODO::Exception; |
|
5
|
|
|
|
|
13
|
|
|
5
|
|
|
|
|
182
|
|
23
|
5
|
|
|
5
|
|
27
|
use ODO::Query::Simple; |
|
5
|
|
|
|
|
7
|
|
|
5
|
|
|
|
|
189
|
|
24
|
5
|
|
|
5
|
|
2599
|
use ODO::Query::VariablePatternMap; |
|
5
|
|
|
|
|
14
|
|
|
5
|
|
|
|
|
252
|
|
25
|
5
|
|
|
5
|
|
184
|
use vars qw /$VERSION/; |
|
5
|
|
|
|
|
11
|
|
|
5
|
|
|
|
|
396
|
|
26
|
|
|
|
|
|
|
$VERSION = sprintf "%d.%02d", q$Revision: 1.2 $ =~ /: (\d+)\.(\d+)/; |
27
|
5
|
|
|
5
|
|
31
|
use base qw/ODO::Query::Handler/; |
|
5
|
|
|
|
|
15
|
|
|
5
|
|
|
|
|
3419
|
|
28
|
|
|
|
|
|
|
|
29
|
|
|
|
|
|
|
|
30
|
|
|
|
|
|
|
=head1 NAME |
31
|
|
|
|
|
|
|
|
32
|
|
|
|
|
|
|
ODO::Query::RDQL::DefaultHandler - Implementation of the generic query processing engine for RDQL |
33
|
|
|
|
|
|
|
|
34
|
|
|
|
|
|
|
=head1 SYNOPSIS |
35
|
|
|
|
|
|
|
|
36
|
|
|
|
|
|
|
=head1 DESCRIPTION |
37
|
|
|
|
|
|
|
|
38
|
|
|
|
|
|
|
=head1 METHODS |
39
|
|
|
|
|
|
|
|
40
|
|
|
|
|
|
|
=over |
41
|
|
|
|
|
|
|
|
42
|
|
|
|
|
|
|
=item evalutate_query( ) |
43
|
|
|
|
|
|
|
|
44
|
|
|
|
|
|
|
0. Get all statements in graph pattern and mark them as not done |
45
|
|
|
|
|
|
|
1. Sort query statements by priority |
46
|
|
|
|
|
|
|
2. Remove query statements already executed |
47
|
|
|
|
|
|
|
3. Generate list of queries based on current query triple |
48
|
|
|
|
|
|
|
i. Find variable with smallest result list |
49
|
|
|
|
|
|
|
ii. Create query triple with variable values substituted |
50
|
|
|
|
|
|
|
4. Execute queries in list |
51
|
|
|
|
|
|
|
i. Union results |
52
|
|
|
|
|
|
|
ii. Update each variable's result list |
53
|
|
|
|
|
|
|
5. Mark query statement as done |
54
|
|
|
|
|
|
|
|
55
|
|
|
|
|
|
|
=cut |
56
|
|
|
|
|
|
|
|
57
|
|
|
|
|
|
|
sub evaluate_query { |
58
|
0
|
|
|
0
|
1
|
|
my $self = shift; |
59
|
|
|
|
|
|
|
|
60
|
0
|
|
|
|
|
|
$self->__initialize(); |
61
|
|
|
|
|
|
|
|
62
|
0
|
|
|
|
|
|
my $completed_statements = {}; |
63
|
|
|
|
|
|
|
|
64
|
|
|
|
|
|
|
# Mark all statemetns as 'not searched' |
65
|
0
|
|
|
|
|
|
my $result_set = $self->{'graph_pattern'}->query($ODO::Query::Simple::ALL_STATEMENTS); |
66
|
0
|
|
|
|
|
|
my $statements = $result_set->results(); |
67
|
0
|
|
|
|
|
|
foreach my $stmt (@{ $statements }) { |
|
0
|
|
|
|
|
|
|
68
|
0
|
|
|
|
|
|
$completed_statements->{ $stmt->hash() } = 0; |
69
|
|
|
|
|
|
|
} |
70
|
|
|
|
|
|
|
|
71
|
0
|
|
|
|
|
|
my $completed = 0; |
72
|
0
|
|
|
|
|
|
my $size = scalar( @{ $statements } ); |
|
0
|
|
|
|
|
|
|
73
|
|
|
|
|
|
|
|
74
|
0
|
|
|
|
|
|
while($completed < $size) { |
75
|
|
|
|
|
|
|
|
76
|
0
|
|
|
|
|
|
my @prioritized_statements = @{ $self->__prioritize_statements( $statements ) }; |
|
0
|
|
|
|
|
|
|
77
|
|
|
|
|
|
|
|
78
|
|
|
|
|
|
|
# Remove triples from the results array that have been completed |
79
|
0
|
|
|
|
|
|
while($completed_statements->{ $prioritized_statements[0]->hash() } == 1) { |
80
|
0
|
|
|
|
|
|
shift @prioritized_statements; |
81
|
|
|
|
|
|
|
} |
82
|
|
|
|
|
|
|
|
83
|
0
|
|
|
|
|
|
my $query_list = $self->{'variable_map'}->make_query_list($prioritized_statements[0]); |
84
|
0
|
|
|
|
|
|
$self->__do_query_list($prioritized_statements[0], $query_list); |
85
|
|
|
|
|
|
|
|
86
|
0
|
|
|
|
|
|
$completed_statements->{ $prioritized_statements[0]->hash() } = 1; |
87
|
0
|
|
|
|
|
|
$completed++; |
88
|
|
|
|
|
|
|
} |
89
|
|
|
|
|
|
|
|
90
|
0
|
|
|
|
|
|
return $self->{'variable_map'}->get_result_graph(); |
91
|
|
|
|
|
|
|
} |
92
|
|
|
|
|
|
|
|
93
|
|
|
|
|
|
|
|
94
|
|
|
|
|
|
|
=back |
95
|
|
|
|
|
|
|
|
96
|
|
|
|
|
|
|
=head1 INTERNALS |
97
|
|
|
|
|
|
|
|
98
|
|
|
|
|
|
|
=over |
99
|
|
|
|
|
|
|
|
100
|
|
|
|
|
|
|
=item __do_query_list( $stmt_query, $query_list ) |
101
|
|
|
|
|
|
|
|
102
|
|
|
|
|
|
|
=cut |
103
|
|
|
|
|
|
|
|
104
|
|
|
|
|
|
|
sub __do_query_list { |
105
|
0
|
|
|
0
|
|
|
my ($self, $stmt_query, $query_list) = @_; |
106
|
|
|
|
|
|
|
|
107
|
0
|
|
|
|
|
|
my $inter_results = ODO::Graph::Simple->Memory(); |
108
|
|
|
|
|
|
|
|
109
|
0
|
|
|
|
|
|
foreach my $q (@{ $query_list }) { |
|
0
|
|
|
|
|
|
|
110
|
0
|
|
|
|
|
|
my $result_set = $self->data()->query($q); |
111
|
0
|
|
|
|
|
|
$inter_results->add($result_set->results()); |
112
|
|
|
|
|
|
|
} |
113
|
|
|
|
|
|
|
|
114
|
0
|
|
|
|
|
|
return $self->{'variable_map'}->invalidate_results($stmt_query, $inter_results); |
115
|
|
|
|
|
|
|
} |
116
|
|
|
|
|
|
|
|
117
|
|
|
|
|
|
|
|
118
|
|
|
|
|
|
|
=item __get_neighbors( $stmt_match ) |
119
|
|
|
|
|
|
|
|
120
|
|
|
|
|
|
|
=cut |
121
|
|
|
|
|
|
|
|
122
|
|
|
|
|
|
|
sub __get_neighbors { |
123
|
0
|
|
|
0
|
|
|
my ($self, $stmt_match) = @_; |
124
|
0
|
|
|
|
|
|
my $neighbor_match = ODO::Query::Simple->new($stmt_match->object(), undef, undef); |
125
|
0
|
|
|
|
|
|
my $result_set = $self->{'graph_pattern'}->query($neighbor_match); |
126
|
0
|
|
|
|
|
|
return $result_set->results(); |
127
|
|
|
|
|
|
|
} |
128
|
|
|
|
|
|
|
|
129
|
|
|
|
|
|
|
|
130
|
|
|
|
|
|
|
=item __make_key( $node1, [ $node2, [ $node3 ] ] ) |
131
|
|
|
|
|
|
|
|
132
|
|
|
|
|
|
|
=cut |
133
|
|
|
|
|
|
|
|
134
|
|
|
|
|
|
|
sub __make_key { |
135
|
0
|
|
|
0
|
|
|
my $self = shift; |
136
|
0
|
|
|
|
|
|
my ($n1, $n2, $n3) = @_; |
137
|
0
|
0
|
|
|
|
|
return join("", (($n1) ? $n1->hash() : '', ($n2) ? $n2->hash() : '', ($n3) ? $n3->hash() : '')); |
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
138
|
|
|
|
|
|
|
} |
139
|
|
|
|
|
|
|
|
140
|
|
|
|
|
|
|
|
141
|
|
|
|
|
|
|
=item __statement_weight( $stmt_query ) |
142
|
|
|
|
|
|
|
|
143
|
|
|
|
|
|
|
Weight = number of variables + 1 if triple match has neighbors otherwise |
144
|
|
|
|
|
|
|
Weight = number of variables |
145
|
|
|
|
|
|
|
|
146
|
|
|
|
|
|
|
=cut |
147
|
|
|
|
|
|
|
|
148
|
|
|
|
|
|
|
sub __statement_weight { |
149
|
0
|
|
|
0
|
|
|
my ($self, $statement) = @_; |
150
|
0
|
|
|
|
|
|
my $w = $self->__num_variables($statement); |
151
|
|
|
|
|
|
|
|
152
|
0
|
|
|
|
|
|
return $w + 1 |
153
|
0
|
0
|
|
|
|
|
if(scalar(@{ $self->__get_neighbors( $statement )}) > 0); |
154
|
|
|
|
|
|
|
|
155
|
0
|
|
|
|
|
|
return $w; |
156
|
|
|
|
|
|
|
} |
157
|
|
|
|
|
|
|
|
158
|
|
|
|
|
|
|
|
159
|
|
|
|
|
|
|
=item __num_variables( $stmt_query ) |
160
|
|
|
|
|
|
|
|
161
|
|
|
|
|
|
|
Counts the number of variables present in a triple match. |
162
|
|
|
|
|
|
|
|
163
|
|
|
|
|
|
|
=cut |
164
|
|
|
|
|
|
|
|
165
|
|
|
|
|
|
|
sub __num_variables { |
166
|
0
|
|
|
0
|
|
|
my ($self, $stmt_query) = @_; |
167
|
|
|
|
|
|
|
|
168
|
0
|
|
|
|
|
|
my $vars = 0; |
169
|
|
|
|
|
|
|
|
170
|
0
|
|
|
|
|
|
foreach my $component ('s', 'p', 'o') { |
171
|
0
|
0
|
|
|
|
|
$vars++ |
172
|
|
|
|
|
|
|
if(UNIVERSAL::isa($stmt_query->$component(), 'ODO::Node::Variable')); |
173
|
|
|
|
|
|
|
} |
174
|
|
|
|
|
|
|
|
175
|
0
|
|
|
|
|
|
return $vars; |
176
|
|
|
|
|
|
|
} |
177
|
|
|
|
|
|
|
|
178
|
|
|
|
|
|
|
|
179
|
|
|
|
|
|
|
=item __prioritize_statements( \@statements ) |
180
|
|
|
|
|
|
|
|
181
|
|
|
|
|
|
|
Sort the graph of L statements by the L object's |
182
|
|
|
|
|
|
|
'weight' . L object 'A' weighs more than L object 'B' |
183
|
|
|
|
|
|
|
iff the following is true: |
184
|
|
|
|
|
|
|
|
185
|
|
|
|
|
|
|
=cut |
186
|
|
|
|
|
|
|
|
187
|
|
|
|
|
|
|
sub __prioritize_statements { |
188
|
0
|
|
|
0
|
|
|
my ($self, $statements) = @_; |
189
|
|
|
|
|
|
|
|
190
|
0
|
0
|
0
|
|
|
|
my @results = sort { |
191
|
0
|
|
|
|
|
|
($self->__num_variables($a) >= $self->__num_variables($b)) |
192
|
|
|
|
|
|
|
&& ($self->__statement_weight($a) >= $self->__statement_weight($b)) |
193
|
|
|
|
|
|
|
&& ($self->{'variable_map'}->known_variable_count($a) >= $self->{'variable_map'}->known_variable_count($b)) |
194
|
0
|
|
|
|
|
|
} @{ $statements }; |
195
|
|
|
|
|
|
|
|
196
|
0
|
|
|
|
|
|
return \@results; |
197
|
|
|
|
|
|
|
} |
198
|
|
|
|
|
|
|
|
199
|
|
|
|
|
|
|
|
200
|
|
|
|
|
|
|
=item __initialize |
201
|
|
|
|
|
|
|
|
202
|
|
|
|
|
|
|
=cut |
203
|
|
|
|
|
|
|
|
204
|
|
|
|
|
|
|
sub __initialize { |
205
|
0
|
|
|
0
|
|
|
my $self = shift; |
206
|
0
|
|
|
|
|
|
$self->{'variable_map'} = ODO::Query::VariablePatternMap->new(); |
207
|
0
|
|
|
|
|
|
$self->{'graph_pattern'} = ODO::Graph::Simple->Memory(); |
208
|
|
|
|
|
|
|
|
209
|
0
|
|
|
|
|
|
my $statement_patterns = $self->query_object()->statement_patterns()->{'#patterns'}; |
210
|
0
|
|
|
|
|
|
$self->{'graph_pattern'}->add($statement_patterns); |
211
|
|
|
|
|
|
|
|
212
|
0
|
|
|
|
|
|
return $self; |
213
|
|
|
|
|
|
|
} |
214
|
|
|
|
|
|
|
|
215
|
|
|
|
|
|
|
|
216
|
|
|
|
|
|
|
sub init { |
217
|
0
|
|
|
0
|
1
|
|
my ($self, $config) = @_; |
218
|
0
|
|
|
|
|
|
$self = $self->SUPER::init($config); |
219
|
0
|
|
|
|
|
|
$self->__initialize(); |
220
|
0
|
|
|
|
|
|
return $self; |
221
|
|
|
|
|
|
|
} |
222
|
|
|
|
|
|
|
|
223
|
|
|
|
|
|
|
|
224
|
|
|
|
|
|
|
=back |
225
|
|
|
|
|
|
|
|
226
|
|
|
|
|
|
|
=head1 COPYRIGHT |
227
|
|
|
|
|
|
|
|
228
|
|
|
|
|
|
|
Copyright (c) 2004-2006 IBM Corporation. |
229
|
|
|
|
|
|
|
|
230
|
|
|
|
|
|
|
All rights reserved. This program and the accompanying materials |
231
|
|
|
|
|
|
|
are made available under the terms of the Eclipse Public License v1.0 |
232
|
|
|
|
|
|
|
which accompanies this distribution, and is available at |
233
|
|
|
|
|
|
|
http://www.eclipse.org/legal/epl-v10.html |
234
|
|
|
|
|
|
|
|
235
|
|
|
|
|
|
|
=cut |
236
|
|
|
|
|
|
|
|
237
|
|
|
|
|
|
|
1; |
238
|
|
|
|
|
|
|
|
239
|
|
|
|
|
|
|
__END__ |