1 of 25

2 of 25

Is this really a line?

Linked Data Fragments World

SPARQL endpoints

Data �dumps

Triple patterns

Bindings-restricted

triple patterns

Linked-data�documents

Basic graph�patterns

...

Specific requests�Low server availability�High server effort

Generic requests�High server availability�High client effort

3 of 25

Is this really a line?

“Give me all the subjects and objects �of triples whose predicate is rdf:type”

SPARQL endpoints

Data �dumps

Triple patterns

Bind-restricted

triple patterns

Linked-data�documents

Basic graph�patterns

...

4 of 25

Is this really a line?

“Give me all persons reachable from Peter �following two foaf:knows links”

SPARQL endpoints

Data �dumps

Triple patterns

Linked-data�documents

5 of 25

A more fundamental �understanding of LDF interfaces

Can we analyze an interface before �actually implementing it?

What is the best way to use an interface �given a specific budget?

Server

Client

6 of 25

A Formal Framework to �Compare Linked Data Fragments

Olaf Hartig Ian Letter Jorge Pérez

7 of 25

Main contributions

Formal machine model for LDF settings�based on Turing Machines

Complete expressiveness lattice�considering several combinations of interfaces

Fine grained complexity analysis�classical complexity, # requests, data transferred

8 of 25

Linked Data Fragment Machine�(LDFM)

9 of 25

LDFM

G

answer

Client Oracle

Server Oracle

Turing Machine

query

...

(response containers)

(regular tapes)

response1

response2

responseK

...

server request

output expression

The main part of a LDFM is a TM with access to its regular tapes
But it also has access to two oracle “Server Oracle” and “Client Oracle”
Oracle are a technical way of saying that these are also Turing Machines but that I really don’t care about the resources used by those machines. I essentially write something in their input tape and in one step the Oracle gives me the input
The machine also has an unbounded number of internal response container that are “READ ONLY” from the point of view of the central machine
The computation starts with a query, and a graph G
Notice that the graph can be accessed only via the Server Oracle
When the computation starts the machine begin doing requests to the server
It writes a request for the server and in one step the server writes the response in one of the internal response containers
Then the machine can make another requests, and the oracle answer by writing in the next container and so on (one important thing is that the server oracle always write in a different container).
After some time the machine can decide that no other request is needed, and then writes a final “output expression”
Then the Client oracle evaluates the expression over the response containers (read only) and produces the answer

10 of 25

(L_CL_S)-LDFM

Client Oracle

Server Oracle

Turing Machine

...

(response containers)

(regular tapes)

...

server request

output expression

L_C

L_S

11 of 25

({⨝},TPF)-LDFM

G

answer

Client Oracle

Server Oracle

Turing Machine

(?X,a,?Y) AND (?X,b,?Y)

...

{⨝}

TPF

r1 = { u1, u2, … }

r2 = { v1, v2, … }

(?X,a,?Y)

r1 ⨝ r2

(?X,b,?Y)

12 of 25

(Ø,brTPF)-LDFM

G

answer

Client Oracle

Server Oracle

Turing Machine

(?X,a,?Y) AND (?X,b,?Y)

...

Ø

brTPF

r1 = { u1, u2,…, uK }

r2 = { v1, v2, … }

(?X,a,?Y)

r2

(?X,b,?Y), u1,u2,...,uK

13 of 25

What are the queries computed by�(L_CL_S) LDFMs?

(L_CL_S) ≡ (R_CR_S)

(L_CL_S) ≺ (R_CR_S)

14 of 25

Expressiveness Lattice

15 of 25

Client Languages

��

�

response combinations

Server Languages��

�

LDF interfaces

TPF

brTPF�BGP�SPARQL

subsets of�{ ∪, ⨝, ⟕, π }

16 of 25

(Ø,BGP) ≡ ({⨝},TPF)

({⨝},TPF)

({∪},TPF)

({∪,⨝,⟕,π},TPF)

(Ø,TPF)

17 of 25

({∪,⨝,⟕,π},brTPF)

({∪,⨝,⟕,π},brTPF) ≡ ({∪,⨝},brTPF)

({∪,⨝,⟕,π},brTPF) ≡ ({∪,⨝},brTPF)�({∪,⨝,⟕,π},SPARQL)

({∪},brTPF)

({⨝},brTPF)

(Ø,brTPF)

18 of 25

({∪,⨝,⟕,π},brTPF) ≡ ({∪,⨝},brTPF)�({∪,⨝,⟕,π},SPARQL)

(Ø,BGP) ≡ ({⨝},TPF)

({∪},brTPF)

({∪},TPF)

({∪,⨝,⟕,π},TPF)

({⨝},brTPF)

(Ø,brTPF)

(Ø,TPF)

19 of 25

Fine-Grained Complexity Analysis

20 of 25

# requests�comm. bandwidth

G

Client Oracle

Server Oracle

Turing Machine

query

...

response1

response2

responseK

...

server request

output expression

answer

21 of 25

(L_CL_S) ≺_T (R_CR_S)

in terms of K

(L_CL_S) ≺_R (R_CR_S)

22 of 25

({∪,⨝,⟕,π}, brTPF)

({∪,⨝}, brTPF)

({∪,⨝,⟕,π}, brTPF)

({∪,⨝}, brTPF)

(Ø,BGP)

({⨝},TPF)

(Ø,BGP)

({⨝},TPF)

R

T

R

T

23 of 25

A theory for comparing different

access protocols for SemWeb data

More fundamental understanding of �combinations of LDF interfaces

Machine model + first results on expressiveness and complexity

24 of 25

A theory for comparing different

access protocols for SemWeb data

Include new LDF interfaces�and client languages��Improve the machine model �and consider new metrics��Formal study of SemWeb query planning

25 of 25

A Formal Framework to �Compare Linked Data Fragments

Olaf Hartig Ian Letter Jorge Pérez

@olafhartig

@perez

Chilean Center�for Semantic Web�Research

Linköping University�