Databases as RDF

trivial to dump RDB as RDF

test: is the graph query coherent (do generated node identifiers merge)?

ETL needs

?who mydb:fn ?name

?who foaf:name ?name

RDB2RDF Mission

The charter says to map RDBs to RDF/OWL.

• RDF Schema:
  • Table->Type maps
  • Column->preciate maps
• DDL to create a triples table:
  • create a triples view.
  • spec mapping
    triples to RDF.
• Normative RDF representation:
  • specify RDF view.
  • map to interface view
    via CONSTRUCT.

Standards Goal

clear algebra for:

• production of stem graph
• SPARQL->SQL
• SQL results->SPARQL results

SPARQL->SQL

Simple Mapping from RDB to RDF

• Following some linked data practices, a relational schema defines a StemMapping:
  

  RelSchema => StemMapping

• The StemMapping creates a graph from a stem URL and the relational data:
  

  StemMapping(stemURI, RelData) => StemGraph

• The StemMapping is composed of trivial TupleMappings, one for each table:
  

  StemMapping(stemURI, RelData) = TupleMapping1(stemURI, Table1)
  	                      + TupleMapping2(stemURI, Table2)...

• A LexicalMap converts Attributes (5, "Bob") in Table to lexical forms:
  

  LexicalMap(string) => string
  LexicalMap(numeric) => lexical form of numberic

• A LiteralMap converts Attributes to RDFLiterals with a lexical value and datatype:
  

  LiteralMap(string) => RDFLiteral(LexicalMap(string), xsd:String)
  LiteralMap(int) => RDFLiteral(LexicalMap(int), xsd:integer)
  LiteralMap(float) => RDFLiteral(LexicalMap(float), xsd:float)

• The TupleMapping creates one triple S P O per non-NULL attribute such that:
  

  S = <stemURI '/' Table '/' PrimaryKey(Table) '.' LexicalMap(Value(PrimaryKey(Table))) '#record' >
  P = <stemURI '/' Table '#' Attribute >
  O = attribute a FK to T2 ? <stemURI '/' T2 '/' PrimaryKey(T2) '.' LiteralMap(Value(PrimaryKey(T2))) '#record' >
      : LiteralMap(Value(Attribute)

test: does the StemGraph meet the same use cases as the relational data?

Virtualizing the StemGraph

• Given a StemQuery over the Stem Graph, create a RelQuery over the RelData:

  RelQuery(StemQuery) = set(AliasedJoin) + set(equivs)

• A SPARQL BGP matching the StemGraph is a list of TriplePatterns.
  TriplePattern S:(URI | VAR) P:URI O:(URI | VAR | Literal | STRING | NUMBER).
  Emit SQL as AliasedJoins (Table AS Alias) and equivs of FQAttributes (Alias.attribute).
  Given an initial set of 0 joins, 0 equivs and 0 varBindings, examine each triple:

  (Rel, Attr) = match(P, stemURI + '/' + (\w+) + '#' (\w+))
  some Alias = hash(Rel + S)
  join.insert(Rel AS Alias)
  pk = primary_key_attribute(Rel)
      match S with
        VAR -> if (bindings[S]) equivs.insert(Alias.pk= bindings[S])
               bindings[S] = Alias.pk
        URI -> (=Rel, PkAttr, PkValue) = match(S, stemURI + '/' (\w+) '/' (\w+) '.' (\w+) '#record')
               some PkAlias = hash(PkRel + S)
               joins.insert(PkRel AS PkAttr)
               =pk = primary_key_attribute(Rel)
               equivs.insert(PkAlias.PkPk= PkValue)
      match O with
        LITERAL -> equivs.insert(alias.attr= O)
        VAR -> if (bindings[O]) equivs.insert(Alias.Attr= bindings[O])
               bindings[O] = Alias.Attr
        URI -> (FkRel, FkAttr, FkValue) = match(S, stemURI + '/' (\w+) '/' (\w+) '.' (\w+) '#record')
               some FkAlias = hash(FkRel + O)
               joins.insert(FkRel AS FkAttr)
               FkPk = primary_key_attribute(FkRel)
               equivs.insert(FkAlias.FkPk= FkValue)
               equivs.insert(Alias.Attr= FkValue)

test: does RelQuery(RelData) == StemQuery(StemGraph)?

BGP Algebra factored

VARconstraint(VAR, FQAttribute):
    if bindings[VAR]) equivs.insert(FQAttribute= bindings[VAR]
    bindings[VAR]= FQAttribute
URIconstraint(URI) => Value:
    (Rel, Attr, Value) = match(URI, stemURI + '/' (\w+) '/' (\w+) '.' (\w+) '#record')
    some Alias = hash(Rel + URI)
    joins.insert(Rel AS Attr)
    pk = primary_key_attribute(Rel)
    equivs.insert(Alias.pk= Value)
    Value

(Rel, Attr) = match(P, stemURI + '/' + (\w+) + '#' (\w+))
some Alias = hash(Rel + S)
join.insert(Rel AS Alias)
pk = primary_key_attribute(Rel)
    match S with
      VAR -> VARconstraint(S, Alias.pk)
      URI -> URIconstraint(S)
    match O with
      LITERAL -> equivs.insert(alias.attr= O)
      VAR -> VARconstraint(O, Alias.Attr)
      URI -> equivs.insert(Alias.Attr= URIconstraint(O))

What's in the Algebra?

• BGP Mapping (above)
• conjunctions, disjunctions, optionals
• NULL guards
• predicate variables
  requires closure of attribute names.

Conjunction

Emp:id=1 emp:id 1 .             
Emp:id=1 emp:manager Emp:id=4 .	
Emp:id=1 emp:section "sales" .  
Emp:id=4 emp:id 4 .	        
                        	
Emp:id=4 emp:manager "exec" .   
	

_:t1 task.employee Emp:id=1 .
_:t1 task.lead Emp:id=2 .    
_:t1 task.name "widgets" .   
_:t2 task.employee Emp:id=4 .
_:t2 task.lead Emp:id=5 .    
_:t2 task.name "widgets".    
	

SELECT ?sec ?name
 WHERE { GRAPH<HQ>    { ?flunky emp:section ?sec OPTIONAL { ?flunky emp:manager ?boss } }
         GRAPH<Sales> { _:t task:employee ?flunky; task:lead ?boss; task:name ?task } }
      

OPTIONALs

• usual issues around NULL
• OPTIONALs must match entirely
• SQL equivalent is an leftJoin of a subselect
• leading OPTIONALs require leading 1-row table:
  bind a constant to a sacrificial attribute.

NULL guards

• closest correspondence is !BOUND
• doesn't bind in table joins
• does bind FQAttrs
• requires bookkeeping

Operators

• STR, isURI, isBLANK are fixed by schema
• datatypes per ISO SQL
• lang fixed by configuration

Interface Graph

• start with StemGraph
• SPARQL CONSTRUCT and Interface Graph
• push IFaceGraph queries to SQL using magic sets
• (DDL approach puts magic sets in SQL instead)

Performance

• SPARQL views approach queries conventional stores directly.
• no multi-source virtual views.
• parsing costs low (LALR1)
• transformation costs roughly linear over query + small hash-table (log n) factor
• performance consistent with that of conventional store

Integrity Constraints

CONSTRUCT { ?x shop:name ?name ; shop:price ?price }
    WHERE { ?x db:name ?name ; db:price ?price }

SELECT ?name
 WHERE { <...Items/id=5#record> shop:name ?name ; shop:price ?price }

• SELECT id_5.nm AS name FROM Items AS id_5 WHERE id_5.id=5

• SELECT id_5.nm AS name FROM Items AS id_5 WHERE id_5.id=5 AND id_5.price IS NOT NULL

Required Integrity Constraint

CONSTRUCT { ?x a shop:SaleItem ; shop:name ?name ; shop:price ?price }
    WHERE { ?x db:name ?name ; db:price ?price ; db:discount ?discount
            FILTER (?discount > 0.0) }

SELECT ?cost
 WHERE { <...Items/id=5#record> a shop:SaleItem ;
                                shop:name ?name ;
                                shop:price ?price }

• SELECT id_5.nm AS name FROM Items AS id_5 WHERE id_5.id=5

• SELECT id_5.nm AS name FROM Items AS id_5 WHERE id_5.id=5 AND id_5.discount > 0

Integrity Constraint Options

• anything with a constraint
• shortest path through vars?
• all paths through vars?
• syntactical hints?

  CONSTRUCT { ?x a shop:SaleItem ; ?x shop:name ?name ; shop:price ?price }
      WHERE { ?x db:name ?name { ?x db:price ?price ; db:discount ?discount } }

CONSTRUCT usefull elsewhere

HCLS Requirements

What requirements to we have?

• SPARQL 1.0 CONSTRUCT
• term rewriting

requirements feedback through:

• cross-membership
• wiki scratch space
• W3C process: Working Draft review by HCLS

tech space