Tree-Witness Rewriting

The tree-witness rewriter is a component of the ontology-based data access framework -ontop-. This page summarises the results of experiments with the tree-witness rewritings of the standard ontologies and queries. A standalone version of the rewriter is available to download from: tw-rewriting.jar.

The tree-witness rewriting separates the topology of the query from the taxonomy defined by the ontology: the output is a union of CQs (the rewriting over H-complete ABoxes) and a set of rules defining the taxonomy.

LUBM-ex-20

The ontology and queries R1-R5 and Q1-Q6 are taken from http://informatik.uni-bremen.de/~clu/combined.

query	atoms	tws	tw-rewritingss over ABoxes
			H-complete		arbitrary
			CQs	atoms	CQs	total CQs
R1	2	0	1	2	2	2
R2	3	0	1	1	1	1
R3	6	0	1	4	23	23
R4	3	0	1	2	2	2
R5	4	0	1	2	2×5	10
Q1	8	1	2	3	23	3,887
				6	2×21×4×23
Q2	4	1	2	2	1	2
				4	1
Q3	6	0	1	5	5×36×4×21	15,120
Q4	8	1	2	5	4×4×30	14,880
				8	4×4×30×30
Q5	5	0	1	4	30×23	690
Q6	8	0	1	6	4×8×23×4×8	23,552
Q7	13	0	1	12	2×30×2×30×2×30	216,000
Q8	13	3	1	6	1	1
Q9	34	1	1	32	2×2×4	16

University

The ontologies and queries taken from http://www.cs.ox.ac.uk/projects/requiem.

query	atoms	ontology					X-ontology
		tws	tw-rewritingss over ABoxes				tws	tw-rewritingss over ABoxes
			H-complete		arbitrary			H-complete		arbitrary
			CQs	atoms	CQs	total CQs		CQs	atoms	CQs	total CQs
R1	2	0	1	2	2	2	0	1	2	2	5
R2	3	0	1	1	1	1	0	1	1	1	1
R3	6	0	1	4	4	4	0	1	4	3×4	12
R4	3	0	1	2	2	2	0	1	2	5	5
R5	4	0	1	2	2×5	10	0	1	2	5×5	25

Adolena

The ontologies and queries taken from http://www.cs.ox.ac.uk/projects/requiem; note that the OWL files had to be modified to replace the URL prefixes "file:/" with "file:///"; for otherwise, SPARQL queries would not refer to the same symbols.

query	atoms	ontology					X-ontology
		tws	tw-rewritingss over ABoxes				tws	tw-rewritingss over ABoxes
			H-complete		arbitrary			H-complete		arbitrary
			CQs	atoms	CQs	total CQs		CQs	atoms	CQs	total CQs
A1	2	1	2	1	25	27*	1	2	1	25	57*
				2	26×2				2	27×16
A2	3	1	2	1	2	50*	1	2	1	2	1,530*
				3	26×2				3	27×16×4
A3	5	0	1	5	2×2×26	104	0	1	5	11×16×27	4,752
A4	3	1	2	1	8	224*	1	2	1	8	3,522*
				3	26×2×8				3	27×16×16
A5	5	0	1	5	6×2×26×2	624	0	1	5	16×11×27×16	76,032

* means that the total number of CQs is smaller than the sum of the numbers of CQs for the two components of the rewriting over H-complete ABoxes (due to CQC subsumption)

Stockexchange

The ontology and queries S1-S5 are taken from http://www.cs.ox.ac.uk/projects/requiem.

query	atoms	tws	tw-rewritingss over ABoxes
			H-complete		arbitrary
			CQs	atoms	CQs	total CQs
S1	1	0	1	1	6	6
S2	3	0	1	1	2	2
S3	5	0	1	2	2×2	4
S4	5	0	1	2	2×2	4
S5	7	0	1	3	2×2×2	8
S6	4	1	1	3	2×6×3	36
S7	5	1	2	2	1	25
				5	2×2×6

Vicodi

The ontology and queries V1-V5 are taken from http://www.cs.ox.ac.uk/projects/requiem.

query	atoms	tws	tw-rewritingss over ABoxes
			H-complete		arbitrary
			CQs	atoms	CQs	total CQs
V1	1	0	1	1	15	15
V2	3	0	1	3	10	10
V3	3	0	1	3	3×24	72
V4	3	0	1	3	5×37	185
V5	7	0	1	7	2×3×5	30

Path

The ontology and queries P1-P5 are taken from http://www.cs.ox.ac.uk/projects/requiem.

query	atoms	tws	tw-rewritingss over ABoxes
			H-complete		arbitrary
			CQs	atoms	CQs	total CQs
P1	1	1	2	1	1	2
				1	1
P2	2	1	2	2	1	2
				2	1
P3	3	1	2	3	1	2
				3	1
P4	4	1	2	4	1	2
				4	1
P5	5	1	2	5	1	2
				5	1

 

query	atoms	P5 ontology					P5X ontology
		tws	tw-rewritingss over ABoxes				tws	tw-rewritingss over ABoxes
			H-complete		arbitrary			H-complete		arbitrary
			CQs	atoms	CQs	total CQs		CQs	atoms	CQs	total CQs
P1	1	1	6	1	1	6	1	6	1	?	14
P2	2	2	4+6	1	1	10	2	4+6	1	?	25*
				2	1				2	?
P3	3	3	3+4+6	1	1	13	3	3+4+6	1	?	58*
				2	1				2	?
				3	1				3	?
P4	4	4	2+3+4+6	1	1	15	4	2+3+4+6	1	?	179*
				2	1				2	?
				3	1				3	?
				4	1				4	?
P5	5	5	1+2+3+4+6	1	1	16	5	1+2+3+4+6	1	?	718*
				2	1				2	?
				3	1				3	?
				4	1				4	?
				5	1				5	?