Optimal RDF Access to Relational Databases

ns db=<http://localhost/OrderTracking#>
attach <http://www.w3.org/1999/02/26-modules/algae#dynamic> (
                    class="W3C::Rdf::SqlDB"
                    properties="../test/OrderTracking.prop")
ask (?o	       db:Orders_id		   ?orderId .
     ?o	       db:Orders_customer	   ?c .
     ?o	       db:Orders_orderDate	   20020907 .
     ?o	       db:Orders_product	   ?p .
     ?p	       db:Products_name		   ?productName .
     ?c	       db:Customers_givenName	   ?first .
     ?c	       db:Customers_familyName	   ?last .
     ?c	       db:Customers_billingAddress ?billAddr .
     ?billAddr db:Addresses_street	   ?billStreet .
     ?billAddr db:Addresses_city	   ?billCity .
     ?billAddr db:Addresses_state	   ?billState)
collect (?orderId ?productName ?first ?last
         ?billStreet ?billCity ?billState)

Following is a breakdown of the same query expressed in n3.

n3 distinguishes variables be explicitly listing existentials and universals. Following "log:forAll" is a list of universal quantifiers.

this log:forAll :o, :d, :p, :productName, :c, :first, :last, :billAddr, :billStreet, :billCity, :billState .

<sql://rdftest@swada.w3.org/OrderTracking/> is log:authoritativeService of
	Orders:id, Orders:customer, Orders:product, Orders:orderDate, 
	Products:id, Products:name, 
	Customers:id, Customers:familyName, Customers:givenName, Customers:billingAddress, 
	Addresses:id, Addresses:street, Addresses:city, Addresses:state.

This example query doesn't rely on any external schema definition; the external keys are associated with their table/primary key pairs with "log:pointsAt".

Orders:product log:pointsAt Products:id .
Orders:customer log:pointsAt Customers:id .
Customers:billingAddress log:pointsAt Addresses:id .

The graph constraints are expressed identically to the algae query above:

 :o Orders:id :orderId .
 :o Orders:customer :c .
 :o Orders:orderDate 20020907 .
 :o Orders:product :p .

 :p Products:name :productName .

 :c Customers:givenName :last .
 :c Customers:familyName :first .
 :c Customers:billingAddress :billAddr .   

 :billAddr Addresses:street :billStreet .
 :billAddr Addresses:city :billCity .
 :billAddr Addresses:state :billState .

Both of the implementations produce the following single SQL query:

SELECT Orders_0.id AS o_id,
       Customers_0.id AS c_id,
       Products_0.id AS p_id,
Products_0.name AS productName_name,
Customers_0.givenName AS first_givenName,
Customers_0.familyName AS last_familyName,
       Addresses_0.id AS billAddr_id,
Addresses_0.street AS billStreet_street,
Addresses_0.city AS billCity_city,
Addresses_0.state AS billState_state
FROM Orders AS Orders_0
     INNER JOIN Customers AS Customers_0 ON Orders_0.customer=Customers_0.id
     INNER JOIN Products AS Products_0 ON Orders_0.product=Products_0.id
     INNER JOIN Addresses AS Addresses_0 ON Customers_0.billingAddress=Addresses_0.id
WHERE Orders_0.orderDate="20020907"

Results
orderId	productName	first	last	billStreet	billCity	billState
"2185"	"pool"	"Biff"	"Thompson"	"123 Elm Street"	"EdgeCity"	"AV"
"2187"	"nose ring"	"Chip"	"Thompson"	"123 Elm Street"	"EdgeCity"	"AV"
"3183"	"other ring"	"Chip"	"Thompson"	"123 Elm Street"	"EdgeCity"	"AV"

Example 2 - OrderTracking Shipping Information (OUTER JOIN)

This example extends the OrderTracking JOIN example above by adding optional arcs for shipping address and contact (person to sign for the shipment). This demonstrates the algorithm's ability to manage multiple joins to the same table. See the example tables from which this data was taken, the algae script and the resulting graph.

ns db=<http://localhost/OrderTracking#>
attach <http://www.w3.org/1999/02/26-modules/algae#dynamic> (
                    class="W3C::Rdf::SqlDB"
                    properties="../test/OrderTracking.prop")
ask (?o		db:Orders_id		    ?orderId .
     ?o		db:Orders_customer	    ?c .
     ?o		db:Orders_orderDate	    ?d {?d >= 20020908000000 && ?d < 20020909000000} .
     ?c		db:Customers_givenName	    ?first .
     ?c		db:Customers_familyName	    ?last .
     ?c		db:Customers_billingAddress ?billAddr .
     ?billAddr	db:Addresses_street	    ?billStreet .
     ?billAddr	db:Addresses_city	    ?billCity .
     ?billAddr	db:Addresses_state	    ?billState .
     ~?o	db:Orders_shippingAddress   ?shipAddr .  
     ~?shipAddr	db:Addresses_street	    ?shipStreet .
     ~?shipAddr	db:Addresses_city	    ?shipCity .  
     ~?shipAddr	db:Addresses_state	    ?shipState . 
     ~?shipAddr	db:Addresses_contact	    ?signer .    
     ~?signer	db:Customers_givenName	    ?sFirst .    
     ~?signer	db:Customers_familyName	    ?sLast       )
collect (?orderId ?first ?last ?billStreet ?billCity ?billState
         ?sFirst ?sLast ?shipStreet ?shipCity ?shipState)

specifies that the Addresses table JOINed on the relvar Orders.shippingAddress, as well as the Customers table then joined on Addresses.contact, are JOINed with an OUTER join:

SELECT Orders_0.id AS o_id,
       Customers_0.id AS c_id,
       Orders_0.orderDate AS d_orderDate,
Customers_0.givenName AS first_givenName,
Customers_0.familyName AS last_familyName,
       Addresses_0.id AS billAddr_id,
Addresses_0.street AS billStreet_street,
Addresses_0.city AS billCity_city,
Addresses_0.state AS billState_state,
       Addresses_1.id AS shipAddr_id,
Addresses_1.street AS shipStreet_street,
Addresses_1.city AS shipCity_city,
Addresses_1.state AS shipState_state,
       Customers_1.id AS signer_id,
Customers_1.givenName AS sFirst_givenName,
Customers_1.familyName AS sLast_familyName
FROM Orders AS Orders_0
     INNER JOIN Customers AS Customers_0 ON Orders_0.customer=Customers_0.id
     INNER JOIN Addresses AS Addresses_0 ON Customers_0.billingAddress=Addresses_0.id
     LEFT OUTER JOIN Addresses AS Addresses_1 ON Orders_0.shippingAddress=Addresses_1.id
     LEFT OUTER JOIN Customers AS Customers_1 ON Addresses_1.contact=Customers_1.id     
WHERE Orders_0.orderDate>="20020908000000" 
  AND Orders_0.orderDate<"20020909000000"

yielding:

Results
orderId	first	last	billStreet	billCity	billState	sFirst	sLast	shipStreet	shipCity	shipState
"2185"	"Biff"	"Thompson"	"123 Elm Street"	"EdgeCity"	"AV"	NULL	NULL	NULL	NULL	NULL
"2187"	"Chip"	"Thompson"	"123 Elm Street"	"EdgeCity"	"AV"	NULL	NULL	NULL	NULL	NULL
"3183"	"Chip"	"Thompson"	"123 Elm Street"	"EdgeCity"	"AV"	"Eustis"	"Walker"	"245 King Street"	"EdgeCity"	"AV"

Similar tests demonstrated the rest of the features described in the language extents.

Example 3 - Product Review (query federation)

This example demonstrates a "join" between relational data and two other sources of input. The relational component comes from the Products table in the OrderTracking database, while two external documents provide an alternate price list and a set of customer reviews:

ns ot=<http://localhost/OrderTracking#>
attach <http://www.w3.org/2003/01/21-RDF-RDB-access/ns#dbs> ot:db (
                    properties="../test/OrderTracking.prop")
ask ot:db (
       ?p  ot:Products_partNo	   ?partNo .
       ?p  ot:Products_price	   ?price {?price >= 15.00 && 
					   ?price <= 50.00} .
       ?p  ot:Products_description ?description)
read <file:../test/Federate0-jwlry.n3> (inputLang="n3") 
ask ( ~?j ot:Products_partNo	   ?partNo .
      ~?j ot:Products_price	   ?jprice)
read <file:../test/Federate0-reviews.rdf> () 
ns rvw=<http://localhost/Reviews#>
ask ( ~?p rvw:rating		   ?rating .
      ~?p rvw:distribution	   ?dist)
collect (?description ?price ?jprice ?rating ?dist)

The SQL query is trivial:

SELECT Products_0.id AS p_id,
       Products_0.partNo AS partNo_partNo,
Products_0.price AS price_price,
Products_0.description AS description_description
FROM Products AS Products_0
WHERE Products_0.price>="15.00" 
  AND Products_0.price<="50.00"

The purpose of this example is to show the underlying motivation for expressing these SQL queries as RDF; that is, the ability to join with data in other formats via a uniform query language.

See "Case Study: FeDeRate for Drug Research" [7] for a pharmacology use case.

Cost/Efficiency

The above example SQL queries demonstrate how Federate transforms RDF queries into SQL queries as efficient as those tailored by an experience database programmer. The execution cost for the SQL query is identical (or better, if the RDF structure helps the querier tailor a better query) to those written into conventional data federation gateways.

Query transformation is accomplished in a parsing pass (yacc), linear-time compiled tree transformation, and a linear serialization of the compile-tree into an SQL string.

Passing the RDF query as a single SQL query over a normalized relational store is optimal in two regards: 1, it eliminates the network from the process of unification. 2, it operates on an application-optimized database instead of a generic triple store.

Migration Between RDF and Normalized Relations

One goal of Federate is to model data in RDF so that it can "round trip", that is, go from RDF statements to the normalized database and back again without changing. For this reason, it is important to distinguish the attributes in the database that represent attributes of the modeled entity from foreign keys, which are used to preserve the graph model in relational databases.

Suppose Chip places an order for a nose ring and we wish to store this in a generic triple store. This would be composed of the triples:

[ customer [ givenName "Chip" ] .
  product  [ name "nose ring" ] ] .

which implies the following triples, using _:<n> to represent an unnamed node in the graph:

_:1 customer _:2 .
_:2 givenName "Chip" .
_:1 product _:3 .
_:3 name "nose ring" .

If we wanted a normalized database to optimize storage and retrieval of this information, we could create an OrderTracking database:

Orders	Customers	Products
id customer product 2187 2 2004	id givenName 2 Chip	id name 2004 nose ring

In doing this, we must invent some integers (2187, 2, 2004) to use as identifiers for the rows in the tables. These enable use to store the relationships conveyed by _:1, _:2 and _:3 above. The id attribute for Orders, Customers and Products is not an attribute of the tuple or the entity that it describes, but an artifact of the mechanism for storing internal structure.

For consistency between the two expressions (RDF and normalized), it is necessary to treat all external keys (Orders.customer and Orders.product above) not as integers, but as references to the entity represented by the indicated row in some table. A consequence of this constraint is that a naive relational database that does not know the external keys, but instead treats all joins as being constrained on coincident attributes, will report the object of would-be foreign key arcs as an integer instead of a resource representing a tuple.

_:1 customer 2 .

This would be analogous to a generic triple store reporting that the object of an arc is some memory address instead of the node in the graph that was the true object of that arc.

When later informed of these external keys, the object will no longer be an integer, but instead an entity reference.

_:1 customer <http://...Customers#id.204> .

The value and even type of the object of the customer arc has changed. This is appropriate as this system is indeed inconsistent and reflects a change in the state of the microuniverse.

Frequently, large organizations assign identifiers to orders and products. These are seldom small integers that should be used as primary keys, but instead published alphanumeric strings appearing in catalogs or returned to the customer who has place an order.

Orders	Customers	Products
id customer product orderID 2187 2 2004 200303120001a	id givenName 2 Chip	id productID name 2004 nr21a.5 nose ring

This would add two triples to the above list.

_:1 customer _:2 .
_:2 givenName "Chip" .
_:1 product _:3 .
_:3 name "nose ring" .
_:1 orderID "200303120001a" .
_:3 prodID "nr21a.5" .

It is possible that a custodian of the relational store would choose to publish the external keys as order or product identifiers. In such a case, the primary key would be a published attribute of the entity represented by the table row. External keys would remain as opaque references to the entity.

_:1 customer _:2 .
_:2 givenName "Chip" .
_:1 product _:3 .
_:3 name "nose ring" .
_:1 orderID "2187" .
_:3 prodID "2004" .

The current implementations of Federate assign ids to rows in tables based on the primary key. This may not be good practice, but is temptingly convenient and useful.

Modeling n-ary Relations

A common criticism of RDF is the consequence of the decision to model relations as only binary. This requires additional entities to be created when modeling n-ary relations. For example, the common supplier scenario: