?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Remove some debug spew
[beagle.git] / Util / SemWeb / Query.cs
blobe2e939058d10a4dc76370cf37a5d01686c73acad
1 using System;
2 using System.Collections;
3 using System.IO;
4
5 using SemWeb;
6 using SemWeb.Stores;
7 using SemWeb.Util;
8
9 namespace SemWeb.Query {
10 public class QueryException : ApplicationException {
11 public QueryException(string message) : base(message) {
12 }
13
14 public QueryException(string message, Exception cause) : base(message, cause) {
15 }
16 }
17
18 public class QueryEngine {
19 // Setup information
20
21 ArrayList setupVariables = new ArrayList();
22 ArrayList setupVariablesDistinct = new ArrayList();
23 ArrayList setupValueFilters = new ArrayList();
24 ArrayList setupStatements = new ArrayList();
25 ArrayList setupOptionalStatements = new ArrayList();
26
27 int start = -1;
28 int limit = -1;
29
30 // Query model information
31
32 bool init = false;
33 object sync = new object();
34 Variable[] variables;
35 Entity[] variableEntities;
36 QueryStatement[][] statements;
37
38 // contains functional and inverse functional properties
39 ResSet fps = new ResSet(),
40 ifps = new ResSet();
41
42 private struct Variable {
43 public Entity Entity;
44 public ValueFilter[] Filters;
45 }
46
47 private struct VarOrAnchor {
48 public bool IsVariable;
49 public int VarIndex;
50 public Resource Anchor;
51 public Resource[] ArrayOfAnchor;
52
53 public override string ToString() {
54 if (IsVariable)
55 return "?" + VarIndex;
56 else
57 return Anchor.ToString();
58 }
59 }
60
61 private class QueryStatement { // class because of use with IComparer
62 public bool Optional;
63 public VarOrAnchor
64 Subject,
65 Predicate,
66 Object;
67
68 public int NumVars() {
69 return (Subject.IsVariable ? 1 : 0)
70 + (Predicate.IsVariable ? 1 : 0)
71 + (Object.IsVariable ? 1 : 0);
72 }
73
74 public override string ToString() {
75 return Subject + " " + Predicate + " " + Object;
76 }
77 }
78
79 class QueryResult {
80 public ResSet[] Bindings;
81 public QueryResult(QueryEngine q) {
82 Bindings = new ResSet[q.variables.Length];
83 }
84 private QueryResult(int x) {
85 Bindings = new ResSet[x];
86 }
87 public void Add(QueryStatement qs, Statement bs) {
88 if (qs.Subject.IsVariable) Add(qs.Subject.VarIndex, bs.Subject);
89 if (qs.Predicate.IsVariable) Add(qs.Predicate.VarIndex, bs.Predicate);
90 if (qs.Object.IsVariable) Add(qs.Object.VarIndex, bs.Object);
91 }
92 void Add(int varIndex, Resource binding) {
93 if (Bindings[varIndex] == null) Bindings[varIndex] = new ResSet();
94 Bindings[varIndex].Add(binding);
95 }
96 public void Clear(QueryStatement qs) {
97 if (qs.Subject.IsVariable && Bindings[qs.Subject.VarIndex] != null) Bindings[qs.Subject.VarIndex].Clear();
98 if (qs.Predicate.IsVariable && Bindings[qs.Predicate.VarIndex] != null) Bindings[qs.Predicate.VarIndex].Clear();
99 if (qs.Object.IsVariable && Bindings[qs.Object.VarIndex] != null) Bindings[qs.Object.VarIndex].Clear();
100 }
101 public void Set(QueryStatement qs, Statement bs) {
102 if (qs.Subject.IsVariable) Set(qs.Subject.VarIndex, bs.Subject);
103 if (qs.Predicate.IsVariable) Set(qs.Predicate.VarIndex, bs.Predicate);
104 if (qs.Object.IsVariable) Set(qs.Object.VarIndex, bs.Object);
105 }
106 void Set(int varIndex, Resource binding) {
107 if (Bindings[varIndex] == null) Bindings[varIndex] = new ResSet();
108 else Bindings[varIndex].Clear();
109 Bindings[varIndex].Add(binding);
110 }
111 public QueryResult Clone() {
112 QueryResult r = new QueryResult(Bindings.Length);
113 for (int i = 0; i < Bindings.Length; i++)
114 if (Bindings[i] != null)
115 r.Bindings[i] = Bindings[i].Clone();
116 return r;
117 }
118 }
119
120 class BindingSet {
121 public ArrayList Results = new ArrayList();
122 public QueryResult Union;
123
124 public BindingSet(QueryEngine q) {
125 Union = new QueryResult(q);
126 }
127 }
128
129 public void Select(Entity entity) {
130 if (entity.Uri == null) throw new QueryException("Anonymous nodes are automatically considered variables.");
131 if (setupVariables.Contains(entity)) return;
132 setupVariables.Add(entity);
133 }
134
135 public void MakeDistinct(Entity a, Entity b) {
136 SetupVariablesDistinct d = new SetupVariablesDistinct();
137 d.a = a;
138 d.b = b;
139 setupVariablesDistinct.Add(d);
140 }
141
142 public void AddValueFilter(Entity entity, ValueFilter filter) {
143 SetupValueFilter d = new SetupValueFilter();
144 d.a = entity;
145 d.b = filter;
146 setupValueFilters.Add(d);
147 }
148
149 public void AddFilter(Statement filter) {
150 setupStatements.Add(filter);
151 }
152
153 public void AddOptionalFilter(Statement filter) {
154 setupOptionalStatements.Add(filter);
155 }
156
157 public int ReturnStart { get { return start; } set { start = value; } }
158
159 public int ReturnLimit { get { return limit; } set { limit = value; } }
160
161 private class SetupVariablesDistinct {
162 public Entity a, b;
163 }
164 private class SetupValueFilter {
165 public Entity a;
166 public ValueFilter b;
167 }
168
169 public void Query(Store targetModel, QueryResultSink result) {
170 lock (sync) {
171 if (!init) {
172 Init();
173 init = true;
174 }
175 }
176
177 result.Init(variableEntities);
178
179 BindingSet bindings = new BindingSet(this);
180 foreach (QueryStatement[] group in statements) {
181 bool ret = Query(group, bindings, targetModel);
182 if (!ret) {
183 // A false return value indicates the query
184 // certainly failed.
185 result.Finished();
186 return;
187 }
188 }
189
190 VariableBinding[] finalbindings = new VariableBinding[variables.Length];
191 for (int i = 0; i < variables.Length; i++)
192 finalbindings[i].Variable = variableEntities[i];
193
194 int ctr = -1;
195 foreach (QueryResult r in bindings.Results) {
196 Permutation permutation = new Permutation(r.Bindings);
197 do {
198 ctr++;
199 if (ctr < start) continue;
200 for (int i = 0; i < variables.Length; i++)
201 finalbindings[i].Target = permutation[i];
202 result.Add(finalbindings);
203 if (ctr == start+limit) break;
204 } while (permutation.Next());
205 if (ctr == start+limit) break;
206 }
207
208 result.Finished();
209 }
210
211 class Permutation {
212 public int[] index;
213 public Resource[][] values;
214
215 public Resource this[int i] {
216 get {
217 return values[i][index[i]];
218 }
219 }
220
221 public Permutation(ResSet[] bindings) {
222 index = new int[bindings.Length];
223 values = new Resource[bindings.Length][];
224 for (int i = 0; i < bindings.Length; i++) {
225 values[i] = new Resource[bindings[i] == null ? 1 : bindings[i].Count];
226 if (bindings[i] != null) {
227 int ctr = 0;
228 foreach (Resource r in bindings[i])
229 values[i][ctr++] = r;
230 }
231 }
232 }
233 public bool Next() {
234 for (int i = 0; i < index.Length; i++) {
235 index[i]++;
236 if (index[i] < values[i].Length) break;
237
238 index[i] = 0;
239 if (i == index.Length-1) return false;
240 }
241 return true;
242 }
243 }
244
245 private void Debug(string message) {
246 //Console.Error.WriteLine(message);
247 }
248
249 class BindingEnumerator {
250 IEnumerator[] loops = new IEnumerator[3];
251 int loop = 0;
252
253 public BindingEnumerator(QueryStatement qs, QueryResult bindings) {
254 loops[0] = GetBindings(qs.Subject, bindings);
255 loops[1] = GetBindings(qs.Predicate, bindings);
256 loops[2] = GetBindings(qs.Object, bindings);
257 }
258
259 public bool MoveNext(out Entity s, out Entity p, out Resource o) {
260 while (true) {
261 bool b = loops[loop].MoveNext();
262 if (!b) {
263 if (loop == 0) { s = null; p = null; o = null; return false; }
264 loops[loop].Reset();
265 loop--;
266 continue;
267 }
268
269 if (loop <= 1) {
270 object obj = loops[loop].Current;
271 if (obj != null && !(obj is Entity)) continue;
272 }
273
274 if (loop < 2) { loop++; continue; }
275
276 s = loops[0].Current as Entity;
277 p = loops[1].Current as Entity;
278 o = loops[2].Current as Resource;
279 return true;
280 }
281 }
282 }
283
284 private bool Query(QueryStatement[] group, BindingSet bindings, Store targetModel) {
285 if (group.Length == 1) {
286 QueryStatement qs = group[0];
287
288 int numMultiplyBound = IsMultiplyBound(qs.Subject, bindings)
289 + IsMultiplyBound(qs.Predicate, bindings)
290 + IsMultiplyBound(qs.Object, bindings);
291
292 if (numMultiplyBound >= 1) {
293 // If there is one or more multiply-bound variable,
294 // then we need to iterate through the permutations
295 // of the variables in the statement.
296
297 Debug(qs.ToString() + " Something Multiply Bound");
298
299 Entity s, p;
300 Resource o;
301
302 ArrayList templates = new ArrayList();
303 BindingEnumerator enumer = new BindingEnumerator(qs, bindings.Union);
304 while (enumer.MoveNext(out s, out p, out o))
305 templates.Add(new Statement(s, p, o));
306
307 Debug("\t" + templates.Count + " Templates");
308
309 // But we still need to preserve the pairings of
310 // the multiply bound variable with the matching
311 // statements.
312
313 MemoryStore matches1 = targetModel.Select((Statement[])templates.ToArray(typeof(Statement)));
314
315 Debug("\t" + matches1.StatementCount + " Matches");
316
317 // The memory store that we get back from a select
318 // won't do indexing, but indexing will help.
319 MemoryStore matches = new MemoryStore();
320 matches.Import(matches1);
321
322 ArrayList newbindings = new ArrayList();
323
324 if (!qs.Optional) bindings.Union.Clear(qs);
325
326 foreach (QueryResult binding in bindings.Results) {
327 // Break apart the permutations in this binding.
328 BindingEnumerator enumer2 = new BindingEnumerator(qs, binding);
329 while (enumer2.MoveNext(out s, out p, out o)) {
330 // Get the matching statements from the union query
331 Statement bs = new Statement(s, p, o);
332 MemoryStore innermatches = matches.Select(bs);
333
334 // If no matches, the binding didn't match the filter.
335 if (innermatches.StatementCount == 0) {
336 if (qs.Optional) {
337 // Preserve the binding.
338 newbindings.Add(binding);
339 } else {
340 // Toss out the binding.
341 continue;
342 }
343 }
344
345 foreach (Statement m in innermatches) {
346 if (!MatchesFilters(m, qs, targetModel)) {
347 if (qs.Optional) newbindings.Add(binding);
348 continue;
349 }
350 bindings.Union.Add(qs, m);
351
352 QueryResult r = binding.Clone();
353 r.Set(qs, m);
354 newbindings.Add(r);
355 }
356 }
357 }
358
359 bindings.Results = newbindings;
360
361 } else {
362 // There are no multiply bound variables, but if
363 // there are more than two unbound variables,
364 // we need to be sure to preserve the pairings
365 // of the matching values.
366
367 int numUnbound = IsUnbound(qs.Subject, bindings)
368 + IsUnbound(qs.Predicate, bindings)
369 + IsUnbound(qs.Object, bindings);
370
371 bool sunbound = IsUnbound(qs.Subject, bindings) == 1;
372 bool punbound = IsUnbound(qs.Predicate, bindings) == 1;
373 bool ounbound = IsUnbound(qs.Object, bindings) == 1;
374
375 Statement s = GetStatement(qs, bindings);
376
377 // If we couldn't get a statement out of this,
378 // then if this was not an optional filter,
379 // fail. If this was optional, don't change
380 // the bindings any.
381 if (s == StatementFailed) return qs.Optional;
382
383 if (numUnbound == 0) {
384 Debug(qs.ToString() + " All bound");
385
386 // All variables are singly bound already.
387 // We can just test if the statement exists.
388 if (!targetModel.Contains(s)
389 && !qs.Optional)
390 return false;
391
392 } else if (numUnbound == 1) {
393 Debug(qs.ToString() + " 1 Unbound");
394
395 // There is just one unbound variable. The others
396 // are not multiply bound, so they must be uniquely
397 // bound (but they may not be bound in all results).
398 // Run a combined select to find all possible values
399 // of the unbound variable at once, and set these to
400 // be the values of the variable for matching results.
401
402 ResSet values = new ResSet();
403 foreach (Statement match in targetModel.Select(s)) {
404 if (!MatchesFilters(match, qs, targetModel)) continue;
405 if (sunbound) values.Add(match.Subject);
406 if (punbound) values.Add(match.Predicate);
407 if (ounbound) values.Add(match.Object);
408 }
409
410 Debug("\t" + values.Count + " matches");
411
412 if (values.Count == 0)
413 return qs.Optional;
414
415 int varIndex = -1;
416 if (sunbound) varIndex = qs.Subject.VarIndex;
417 if (punbound) varIndex = qs.Predicate.VarIndex;
418 if (ounbound) varIndex = qs.Object.VarIndex;
419
420 if (bindings.Results.Count == 0)
421 bindings.Results.Add(new QueryResult(this));
422
423 bindings.Union.Bindings[varIndex] = new ResSet();
424 foreach (Resource r in values)
425 bindings.Union.Bindings[varIndex].Add(r);
426
427 foreach (QueryResult r in bindings.Results) {
428 // Check that the bound variables are bound in this result.
429 // If it is bound, it will be bound to the correct resource,
430 // but it might not be bound at all if an optional statement
431 // failed to match -- in which case, don't modify the binding.
432 if (qs.Subject.IsVariable && !sunbound && r.Bindings[qs.Subject.VarIndex] == null) continue;
433 if (qs.Predicate.IsVariable && !punbound && r.Bindings[qs.Predicate.VarIndex] == null) continue;
434 if (qs.Object.IsVariable && !ounbound && r.Bindings[qs.Object.VarIndex] == null) continue;
435
436 r.Bindings[varIndex] = values;
437 }
438
439 } else {
440 // There are two or more unbound variables, the
441 // third variable being uniquely bound, if bound.
442 // Keep track of the pairing of unbound variables.
443
444 Debug(qs.ToString() + " 2 or 3 Unbound");
445
446 if (bindings.Results.Count == 0)
447 bindings.Results.Add(new QueryResult(this));
448
449 ArrayList newbindings = new ArrayList();
450 foreach (Statement match in targetModel.Select(s)) {
451 if (!MatchesFilters(match, qs, targetModel)) continue;
452 bindings.Union.Add(qs, match);
453 foreach (QueryResult r in bindings.Results) {
454 if (numUnbound == 2) {
455 // Check that the bound variable is bound in this result.
456 // If it is bound, it will be bound to the correct resource,
457 // but it might not be bound at all if an optional statement
458 // failed to match -- in which case, preserve the binding if
459 // this was an optional statement.
460 bool matches = true;
461 if (qs.Subject.IsVariable && !sunbound && r.Bindings[qs.Subject.VarIndex] == null) matches = false;
462 if (qs.Predicate.IsVariable && !punbound && r.Bindings[qs.Predicate.VarIndex] == null) matches = false;
463 if (qs.Object.IsVariable && !ounbound && r.Bindings[qs.Object.VarIndex] == null) matches = false;
464 if (!matches) {
465 if (qs.Optional)
466 newbindings.Add(r);
467 continue;
468 }
469 }
470
471 QueryResult r2 = r.Clone();
472 r2.Add(qs, match);
473 newbindings.Add(r2);
474 }
475 }
476 if (qs.Optional && newbindings.Count == 0)
477 return true; // don't clear out bindings
478 bindings.Results = newbindings;
479 }
480 }
481
482 } else {
483 // There is more than one statement in the group.
484 // These are never optional.
485
486 Debug("Statement group.");
487
488 VarOrAnchor var = new VarOrAnchor();
489 foreach (QueryStatement qs in group) {
490 if (qs.Subject.IsVariable && bindings.Union.Bindings[qs.Subject.VarIndex] == null) var = qs.Subject;
491 if (qs.Predicate.IsVariable && bindings.Union.Bindings[qs.Predicate.VarIndex] == null) var = qs.Predicate;
492 if (qs.Object.IsVariable && bindings.Union.Bindings[qs.Object.VarIndex] == null) var = qs.Object;
493 break;
494 }
495 // The variable should be unbound so far.
496 if (bindings.Union.Bindings[var.VarIndex] != null)
497 throw new Exception();
498
499 ArrayList findstatements = new ArrayList();
500 foreach (QueryStatement qs in group) {
501 Statement s = GetStatement(qs, bindings);
502 if (s == StatementFailed) return false;
503 findstatements.Add(s);
504 }
505
506 ResSet values = new ResSet();
507 foreach (Entity r in targetModel.FindEntities((Statement[])findstatements.ToArray(typeof(Statement)))) {
508 if (!MatchesFilters(r, var, targetModel)) continue;
509 values.Add(r);
510 }
511 if (values.Count == 0) return false;
512
513 bindings.Union.Bindings[var.VarIndex] = values;
514
515 if (bindings.Results.Count == 0)
516 bindings.Results.Add(new QueryResult(this));
517
518 foreach (QueryResult result in bindings.Results)
519 result.Bindings[var.VarIndex] = values;
520 }
521
522 return true;
523 }
524
525 static Resource[] ResourceArrayNull = new Resource[] { null };
526
527 private static IEnumerator GetBindings(VarOrAnchor e, QueryResult bindings) {
528 if (!e.IsVariable) {
529 if (e.ArrayOfAnchor == null)
530 e.ArrayOfAnchor = new Resource[] { e.Anchor };
531 return e.ArrayOfAnchor.GetEnumerator();
532 }
533 if (bindings.Bindings[e.VarIndex] == null) return ResourceArrayNull.GetEnumerator();
534 return bindings.Bindings[e.VarIndex].Items.GetEnumerator();
535 }
536 private int IsMultiplyBound(VarOrAnchor e, BindingSet bindings) {
537 if (!e.IsVariable) return 0;
538 if (bindings.Union.Bindings[e.VarIndex] == null) return 0;
539 if (bindings.Union.Bindings[e.VarIndex].Items.Count == 1) return 0;
540 return 1;
541 }
542 private int IsUnbound(VarOrAnchor e, BindingSet bindings) {
543 if (!e.IsVariable) return 0;
544 if (bindings.Union.Bindings[e.VarIndex] == null) return 1;
545 return 0;
546 }
547
548 private Resource GetUniqueBinding(VarOrAnchor e, BindingSet bindings) {
549 if (!e.IsVariable) return e.Anchor;
550 if (bindings.Union.Bindings[e.VarIndex] == null || bindings.Union.Bindings[e.VarIndex].Count == 0) return null;
551 if (bindings.Union.Bindings[e.VarIndex].Count > 1) throw new Exception();
552 foreach (Resource r in bindings.Union.Bindings[e.VarIndex].Items)
553 return r;
554 throw new Exception();
555 }
556
557 Statement StatementFailed = new Statement(null, null, null);
558
559 private Statement GetStatement(QueryStatement sq, BindingSet bindings) {
560 Resource s = GetUniqueBinding(sq.Subject, bindings);
561 Resource p = GetUniqueBinding(sq.Predicate, bindings);
562 Resource o = GetUniqueBinding(sq.Object, bindings);
563 if (s is Literal || p is Literal) return StatementFailed;
564 return new Statement((Entity)s, (Entity)p, o);
565 }
566
567 bool MatchesFilters(Statement s, QueryStatement q, Store targetModel) {
568 return MatchesFilters(s.Subject, q.Subject, targetModel)
569 && MatchesFilters(s.Predicate, q.Predicate, targetModel)
570 && MatchesFilters(s.Object, q.Object, targetModel);
571 }
572
573 bool MatchesFilters(Resource e, VarOrAnchor var, Store targetModel) {
574 if (!var.IsVariable) return true;
575 foreach (ValueFilter f in variables[var.VarIndex].Filters) {
576 if (!f.Filter(e, targetModel)) return false;
577 }
578 return true;
579 }
580
581 private void Init() {
582 // Any anonymous nodes in the graph are SelectFirst nodes
583 foreach (Statement s in setupStatements) {
584 InitAnonVariable(s.Subject);
585 InitAnonVariable(s.Predicate);
586 InitAnonVariable(s.Object);
587 }
588 foreach (Statement s in setupOptionalStatements) {
589 InitAnonVariable(s.Subject);
590 InitAnonVariable(s.Predicate);
591 InitAnonVariable(s.Object);
592 }
593
594 // Set up the variables array.
595 variables = new Variable[setupVariables.Count];
596 variableEntities = new Entity[variables.Length];
597 Hashtable varIndex = new Hashtable();
598 for (int i = 0; i < variables.Length; i++) {
599 variables[i].Entity = (Entity)setupVariables[i];
600 variableEntities[i] = variables[i].Entity;
601 varIndex[variables[i].Entity] = i;
602
603 ArrayList filters = new ArrayList();
604 foreach (SetupValueFilter filter in setupValueFilters) {
605 if (filter.a == variables[i].Entity)
606 filters.Add(filter.b);
607 }
608
609 variables[i].Filters = (ValueFilter[])filters.ToArray(typeof(ValueFilter));
610 }
611
612 // Set up the statements
613 ArrayList statements = new ArrayList();
614 foreach (Statement st in setupStatements)
615 InitSetStatement(st, statements, varIndex, false);
616 foreach (Statement st in setupOptionalStatements)
617 InitSetStatement(st, statements, varIndex, true);
618
619 // Order the statements in the most efficient order
620 // for the recursive query.
621 Hashtable setVars = new Hashtable();
622 ArrayList sgroups = new ArrayList();
623 while (statements.Count > 0) {
624 QueryStatement[] group = InitBuildNode(statements, setVars);
625 sgroups.Add(group);
626 foreach (QueryStatement qs in group) {
627 if (qs.Subject.IsVariable) setVars[qs.Subject.VarIndex] = setVars;
628 if (qs.Predicate.IsVariable) setVars[qs.Predicate.VarIndex] = setVars;
629 if (qs.Object.IsVariable) setVars[qs.Object.VarIndex] = setVars;
630 }
631 }
632
633 this.statements = (QueryStatement[][])sgroups.ToArray(typeof(QueryStatement[]));
634 }
635
636 private void InitAnonVariable(Resource r) {
637 if (r is Entity && r.Uri == null)
638 setupVariables.Add(r);
639 }
640
641 private void InitSetStatement(Statement st, ArrayList statements, Hashtable varIndex, bool optional) {
642 QueryStatement qs = new QueryStatement();
643
644 InitSetStatement(st.Subject, ref qs.Subject, varIndex);
645 InitSetStatement(st.Predicate, ref qs.Predicate, varIndex);
646 InitSetStatement(st.Object, ref qs.Object, varIndex);
647
648 qs.Optional = optional;
649
650 // If this statement has no variables, just drop it.
651 if (!qs.Subject.IsVariable && !qs.Predicate.IsVariable && !qs.Object.IsVariable)
652 return;
653
654 statements.Add(qs);
655 }
656
657 private void InitSetStatement(Resource ent, ref VarOrAnchor st, Hashtable varIndex) {
658 if (!varIndex.ContainsKey(ent)) {
659 st.IsVariable = false;
660 st.Anchor = ent;
661 } else {
662 st.IsVariable = true;
663 st.VarIndex = (int)varIndex[ent];
664 }
665 }
666
667 private class QueryStatementComparer : IComparer {
668 Hashtable setVars;
669 ResSet fps, ifps;
670
671 public QueryStatementComparer(Hashtable setVars, ResSet fps, ResSet ifps) {
672 this.setVars = setVars;
673 this.fps = fps;
674 this.ifps = ifps;
675 }
676
677 int IComparer.Compare(object a, object b) {
678 return Compare((QueryStatement)a, (QueryStatement)b);
679 }
680
681 public int Compare(QueryStatement a, QueryStatement b) {
682 int optional = a.Optional.CompareTo(b.Optional);
683 if (optional != 0) return optional;
684
685 int numvars = NumVars(a).CompareTo(NumVars(b));
686 if (numvars != 0) return numvars;
687
688 int complexity = Complexity(a).CompareTo(Complexity(b));
689 return complexity;
690 }
691
692 private int NumVars(QueryStatement s) {
693 int ret = 0;
694 if (s.Subject.IsVariable && !setVars.ContainsKey(s.Subject.VarIndex))
695 ret++;
696 if (s.Predicate.IsVariable && !setVars.ContainsKey(s.Predicate.VarIndex))
697 ret++;
698 if (s.Object.IsVariable && !setVars.ContainsKey(s.Object.VarIndex))
699 ret++;
700 return ret;
701 }
702
703 private int Complexity(QueryStatement s) {
704 if (s.Predicate.IsVariable) return 2;
705 if ((!s.Subject.IsVariable || setVars.ContainsKey(s.Subject.VarIndex))
706 && fps.Contains(s.Predicate.Anchor))
707 return 0;
708 if ((!s.Object.IsVariable || setVars.ContainsKey(s.Object.VarIndex))
709 && ifps.Contains(s.Predicate.Anchor))
710 return 0;
711 return 1;
712 }
713 }
714
715 private QueryStatement[] InitBuildNode(ArrayList statements, Hashtable setVars) {
716 // Get the best statements to consider
717 // Because we can consider statements in groups, we need
718 // a list of lists.
719 QueryStatementComparer comparer = new QueryStatementComparer(setVars, fps, ifps);
720 ArrayList considerations = new ArrayList();
721 for (int i = 0; i < statements.Count; i++) {
722 QueryStatement next = (QueryStatement)statements[i];
723 int comp = 1;
724 if (considerations.Count > 0) {
725 QueryStatement curcomp = (QueryStatement) ((ArrayList)considerations[0])[0];
726 comp = comparer.Compare(curcomp, next);
727 }
728
729 if (comp < 0) // next is worse than current
730 continue;
731
732 if (comp > 0) // clear out worse possibilities
733 considerations.Clear();
734
735 // next is equal to what we have. we can either
736 // group it with an existing statement, or make
737 // a new group out of it.
738
739 bool grouped = false;
740 foreach (ArrayList g in considerations) {
741 // We can group next in g, if the only
742 // unset variables in next are the only
743 // unset variables in the statements in g.
744 // AND if nothing else is a variable,
745 // because of having multiply-bound variables
746 // with FindEntities. And none may be optional.
747 QueryStatement s = (QueryStatement)g[0];
748 int su = InitBuildNodeGetUniqueUnsetVar(s, setVars);
749 int nu = InitBuildNodeGetUniqueUnsetVar(next, setVars);
750 if (su == nu && su != -1 && s.NumVars() == 1 && next.NumVars() == 1
751 && !s.Optional && !next.Optional) {
752 g.Add(next);
753 grouped = true;
754 break;
755 }
756 }
757 if (grouped) continue;
758
759 // we didn't group it with anything existing,
760 // so make a new group
761
762 ArrayList group = new ArrayList();
763 group.Add(next);
764 considerations.Add(group);
765 }
766
767 // Pick the group with the most number of statements.
768 ArrayList bestgroup = null;
769 foreach (ArrayList g in considerations) {
770 if (bestgroup == null || bestgroup.Count < g.Count)
771 bestgroup = g;
772 }
773
774 foreach (QueryStatement qs in bestgroup)
775 statements.Remove(qs);
776
777 return (QueryStatement[])bestgroup.ToArray(typeof(QueryStatement));
778 }
779
780 int InitBuildNodeGetUniqueUnsetVar(QueryStatement s, Hashtable setVars) {
781 int ret = -1;
782 if (s.Subject.IsVariable && !setVars.ContainsKey(s.Subject.VarIndex))
783 ret = s.Subject.VarIndex;
784 if (s.Predicate.IsVariable && !setVars.ContainsKey(s.Predicate.VarIndex)) {
785 if (ret != -1) return -1;
786 ret = s.Predicate.VarIndex;
787 }
788 if (s.Object.IsVariable && !setVars.ContainsKey(s.Object.VarIndex)) {
789 if (ret != -1) return -1;
790 ret = s.Object.VarIndex;
791 }
792 return ret;
793 }
794 }
795
796 public abstract class QueryResultSink {
797 public virtual void Init(Entity[] variables) {
798 }
799
800 public abstract bool Add(VariableBinding[] result);
801
802 public virtual void Finished() {
803 }
804 }
805
806 public struct VariableBinding {
807 Entity v;
808 Resource t;
809
810 internal VariableBinding(Entity variable, Resource target) {
811 v = variable;
812 t = target;
813 }
814
815 public Entity Variable { get { return v; } internal set { v = value; } }
816 public Resource Target { get { return t; } internal set { t = value; } }
817 }
818 }
819
A Beagle Git Repo