Query Ledger

Or: How to SPARQL 100,000,000,000 statements from an old laptop that Kleine Piep peed on once?

This is ‘Kleine Piep’ btw…

Let's query the Web!

Let's query the Semantic Web!

	    
SELECT ?aap {
  SERVICE <http://factforge.net/sparql> { 
    ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
  }
}
            
          
Q: How do I know it's <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>?

A: It came to me in a dream

A: Ok… I used lodsearch.org for that

lodsearch.org

Let's query the Semantic Web!

	    
SELECT ?aap {
  SERVICE <http://factforge.net/sparql> { 
    ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
  }
}
            
          
Q: How do I know it's <http://factforge.net/sparql>?

A: Oops… I was bluffing indeed.

A: There's a list of 549 SPARQL endpoints over at SPARQLES

Let's extend the query with 549 SERVICE clauses!

	    
SELECT ?aap {
  {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  } UNION {
    SERVICE <http://factforge.net/sparql> { 
      ?aap a <http://sw.opencyc.org/2008/06/10/concept/Mx4rvVjta5wpEbGdrcN5Y29ycA>
    }
  }
}
            
          

Why is it so difficult?

  1. We must find the source data at query time
  2. We must replan the query
  3. The identity closure is huge (owl:sameAs)
  4. Computation must be efficient
  5. That laptop is really old!

[1] Find source data at query time

Use LOD Laundromat to find the source data for ‘Cyc Monkey’.

[2] Replan the query

Direct access to estimates

Dynamic replanning while executing

Pre-planning: estimate query permutations

SP²B query:

	    
SELECT ?yr {
  ?journal rdf:type bench:Journal .
  ?journal dc:title "Journal 1 (1940)"^^xsd:string .
  ?journal dcterms:issued ?yr 
}
	    
	  

Query ledger:

1726: BGP
  ├ 7: ?journal dc:title "Journal 1 (1940)" .
  ├ 109: ?journal a bench:Journal .
  └ 1610: ?journal dcterms:issued ?yr .
	    

[3] Huge identity closure (owl:sameAs)

~900M statements (RocksDB)

Replace all terms with identity set handles

Turn it into unification: (X ‘owl:sameAs’ Y) ⇒ (X = Y)

[4] Efficient computation

  • Header Dictionary Triples (Fernandez 2013)
  • Lock-free atom garbage collection (Wielemaker & Harris 2016)
  • Canonical literals
  • CLP(H)

Thank you!

WWW: wouterbeek.com

Mail: w.g.j.beek@vu.nl