search

LinkedDataFragments / Client.js

[DEPRECATED] A JavaScript client for Triple Pattern Fragments interfaces.
http://linkeddatafragments.org/
Other
92 stars 35 forks source link

Query optimization #49

Closed cKlee closed 4 years ago

cKlee commented 6 years ago

In federated queries I wonder if the number of request can be reduced dramatically without extensive changes to the query algorithm. In a simplified example I have two data sources D1 and D2 and a query:

SELECT ?gnd WHERE {
  [] dc:subject ?gnd .
  ?gnd a gndo:CorporateBody .
}

The client requests the following

D1 ? dc:subject ? // 0 triples
D2 ? dc:subject ? // 500.000 triples

Now all 500.000 ?gnd bindings are requested for both! data source:

D1 <> rdf:type gndo:CorporateBody // 0 triples
D2 <> rdf:type gndo:CorporateBody // 0 triples
D1 <> rdf:type gndo:CorporateBody // 0 triples
D2 <> rdf:type gndo:CorporateBody // 0 triples
D1 <> rdf:type gndo:CorporateBody // 0 triples
D2 <> rdf:type gndo:CorporateBody // 1 triples
...

So there will be a million requests (plus the page requests on D1). But 500.000 requests on D1 are unnecessary. D1 will never return a triple, because there is no triple with gndo:CorporateBody as object (and probably no rdf:type as predicate). Could this be checked in advance?

Either

D1 ? rdf:type ? // 0 triples
D2 ? rdf:type ? // 15.000.000 triples

or

D1 ? ? gndo:CorporateBody // 0 triples
D2 ? ? gndo:CorporateBody // 1.500.000 triples

should be sufficient to never again make requests to D1. In scenarios with three, four or more data sources this will make a lot more sense.

I read http://linkeddatafragments.org/publications/eswc2015.pdf a long time ago and I'm not sure if this approach was mentioned.

mielvds commented 6 years ago

This is an example of local optimization turned sub-optimal, also called greedy. Low-hanging fruit though, would be easy to implement. I'll have a look if I can add it. Else, I put it on a list with future optimizations to implement them in a more sustainable way. Adding these adhoc will not last, especially because a new version of this client is out soon.

cKlee commented 6 years ago

Looking forward to it. Thanks!

rubensworks commented 4 years ago

This project has now been deprecated in favor of Comunica, if this issue is still relevant to you, feel free to open a new issue there.