Return to RDFViewS: View Selection in Semantic Web Databases

RDFViewS Experiments

Note: You need an SVG-enabled browser to view the following pages.

Cost reduction for various strategies

The following table shows cost reduction curves over time for various strategies (DFS-AVF-STV, GSTR-AVF-STV, Heuristic). Search times were limited to 3h, however charts have been generated at various granularities (1 min, 5 min, 1h, 3h). We used synthetic workloads of 5 to 200 queries of various shapes and commonality. Each query is made of 10 atoms.

1 minute 5 minutes 1 hour 3 hours
5 queries relative
absolute
relative
absolute
relative
absolute
relative
absolute
10 queries relative
absolute
relative
absolute
relative
absolute
relative
absolute
20 queries relative
absolute
relative
absolute
relative
absolute
relative
absolute
50 queries relative
absolute
relative
absolute
relative
absolute
relative
absolute
100 queries relative
absolute
relative
absolute
relative
absolute
relative
absolute
200 queries relative
absolute
relative
absolute
relative
absolute
relative
absolute

Cost reduction for varying cost function weights

In this experiment, we run DFS-AVF-STV searches for 5 min, on synthetic workloads of 5 to 200 queries of different shapes and commonality. Each query is made of 5 atoms. The cost is computed as follows:

c(S) = cs * VSO(S) + cr * REC(S) + cm * VMC(S)
The weights were set by default as follows
cs = 1.0, cr = 1.0 and cm = 0.5, (i.e. cm = |D| x 1.0E-8, where |D| is the dataset size).
We varied the cost function weights in 4 different ways:

  • * Starting from the default weights, each cost component’s weights was alternatively set to 0.0.
    Then, the same was done for all component’s pairs.
  • VSO: cs weight varies from 0.1 to 0.9, others are fixed.
  • REC: cr weight varies from 0.1 to 0.9, others are fixed
  • VMC: cm weight varies from 5.0E6 to 5.0E-1, others are fixed
* VSO REC VMC
5 queries 5-atom queries 5-atom queries 5-atom queries 5-atom queries
10 queries 5-atom queries 5-atom queries 5-atom queries 5-atom queries
20 queries 5-atom queries 5-atom queries 5-atom queries 5-atom queries
50 queries 5-atom queries 5-atom queries 5-atom queries 5-atom queries
100 queries 5-atom queries 5-atom queries 5-atom queries 5-atom queries
200 queries 5-atom queries 5-atom queries 5-atom queries 5-atom queries

Cost reduction for pre-/post-reformulation

The following table shows the evolution of cost over time using real-world queries. The Barton dataset was used, and reasoning was performed using the MODS3 schema.

1 minute 5 minutes 1 hour 3 hours
5 queries relative/absolute relative/absolute relative/absolute relative/absolute
10 queries relative/absolute relative/absolute relative/absolute relative/absolute

Permanent link to this article: https://team.inria.fr/oak/projects/rdfvs/rdfviews-experiments/

_5a_all-weights

Evolution of cost over 5min of search 5 atoms per query 5 queries of 5 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Tue Jul 5 09:55:28 CEST 2011 10 queries of 5 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Tue Jul 5 09:55:33 CEST 2011 …

_5a_qpc-weights

Evolution of cost over 5min of search 5 atoms per query 5 queries of 5 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Fri Jul 8 23:36:02 CEST 2011 10 queries of 5 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Fri Jul 8 23:36:09 CEST 2011 …

_5a_vso-weights

Evolution of cost over 5min of search 5 atoms per query 5 queries of 5 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Fri Jul 8 23:35:20 CEST 2011 10 queries of 5 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Fri Jul 8 23:35:27 CEST 2011 …

-JC-VB-SC-JC-1h

Evolution of cost over 1h of search 10 atoms per query All charts below show relative costs. See absolute costs. Jump to workload :5 queries 10 queries 20 queries 50 queries 100 queries 200 queries 5 queries of 10 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Thu Mar 31 18:04:21 …

-JC-VB-SC-JC-1h0

Evolution of cost over 1h of search 10 atoms per query All charts below show absolute costs. See relative costs. Jump to workload :5 queries 10 queries 20 queries 50 queries 100 queries 200 queries 5 queries of 10 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Thu Mar 31 18:11:01 …

-JC-VB-SC-JC-3h

Evolution of cost over 3h of search 10 atoms per query All charts below show relative costs. See absolute costs. Jump to workload :5 queries 10 queries 20 queries 50 queries 100 queries 200 queries 5 queries of 10 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Thu Mar 31 18:04:28 …

-JC-VB-SC-JC-3h0

Evolution of cost over 3h of search 10 atoms per query All charts below show absolute costs. See relative costs. Jump to workload :5 queries 10 queries 20 queries 50 queries 100 queries 200 queries 5 queries of 10 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Thu Mar 31 18:11:07 …

C-VB-SC-JC-1min

Evolution of cost over 1min of search 10 atoms per query All charts below show relative costs. See absolute costs. Jump to workload :5 queries 10 queries 20 queries 50 queries 100 queries 200 queries 5 queries of 10 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Thu Mar 31 18:04:09 …

C-VB-SC-JC-1min0

Evolution of cost over 1min of search 10 atoms per query All charts below show absolute costs. See relative costs. Jump to workload :5 queries 10 queries 20 queries 50 queries 100 queries 200 queries 5 queries of 10 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Thu Mar 31 18:10:47 …

C-VB-SC-JC-5min

Evolution of cost over 5min of search 10 atoms per query All charts below show relative costs. See absolute costs. Jump to workload :5 queries 10 queries 20 queries 50 queries 100 queries 200 queries 5 queries of 10 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Thu Mar 31 18:04:15 …

C-VB-SC-JC-5min0

Evolution of cost over 5min of search 10 atoms per query All charts below show absolute costs. See relative costs. Jump to workload :5 queries 10 queries 20 queries 50 queries 100 queries 200 queries 5 queries of 10 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Thu Mar 31 18:10:54 …

oning_10q_index

Evolution of cost with pre/post-reformulation (10 queries) Relative Absolute 1min 5min 1h 3h Last generated : Tue Jun 28 09:55:46 CEST 2011

s_5a_ds-weights

Evolution of cost over 5min of search 5 atoms per query 5 queries of 5 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Tue Jul 5 09:58:07 CEST 2011 10 queries of 5 atoms each HIGH LOW STAR CHAIN RANDOM_THIN RANDOM_DENSE MIXED Last generated : Tue Jul 5 09:58:13 CEST 2011 …

soning_5q_index

Evolution of cost with pre/post-reformulation (5 queries) Relative Absolute 1min 5min 1h 3h Last generated : Tue Jun 28 10:21:49 CEST 2011