Status of this Document

This document contains working notes for a heterogenous RDF database. It is not endorsed by the W3C in any way.

RDF -> SQL Query Converstion

description algae query SQL query
graph parse tree constraints parse tree OrderTracking4-queryGraph-img OrderTracking4-query-img OrderTracking4-compiledGraph-img OrderTracking4-compiled-img OrderTracking8-queryGraph-img OrderTracking8-query-img OrderTracking8-compiledGraph-img OrderTracking8-compiled-img


The task is to transform the faux SQL compile tree (called so because it is an attempt at looking like what you get when you parse the SQL) into a valid SQL query string. State stored by the altae tree to SQL tree transformer and potentially by the SQL tree to query string transformer tells the results interpreter how fields should be interpreted as literals, or uris or parts the a table key. Ideally, each result from the SQL engine will result in a result in the RDF ResultSet, bit is possible to impose constraints on the returned tuples from he query.

One pproach is to walk the top-level conjunctions of the SQL tree for join candiates. Each attribute-binding constraint has a WHERE clause and a set of aliases that it binds together. A spanning tree can tell us if all aliases are bound against the others. Higher level constraints can keep a list of all the aliases which are mentioned in any branch of contained disjunctions, and those constrained definitively (by not being in a disjunction or by being constrained definitively in all branches of a disjunction). I suspect this algorithm is used for SQL interpreters for validating well formed formulae, but I've never written one and would like help here.

query 8 presents a difficult case where different sides of a disjunction entail different aliases. Since no path of the disjunction may chose not to bind aliases that another binds, the aliases not in common must be outer joined on the appropriate alias.attributes for the defining disjunction branch. It is important that this join, when applies to the corresponding alias/attributes on the unrelated branches of the disjunction present at most one answer (none, resulting in no bindings in the RDF graph, is far preferable).

Working this problem from a different angle, we can solve the different joins problem:

SQL Joins on Disjunctions With Different Table Bindings

Example 1: disjunctive query where left side has two terms and right side has three

Algae2 Query
(?n1 p1 ?n2.
 ?n2 ?pz ?n3)
(?n1 ?px ?n2.
 ?n1 ?px ?n3.[?n3!=?n2]
 ?n3 p2 ?n4)
Algae (N3) Data
1n1 p1  1n2.
1n2 1pz 1n3.
2n1 2px 2n2.
2n1 2px 2n3.
2n3 p2  2n4.
SQL Data
CREATE TABLE S (s CHAR(4), p CHAR(4), o CHAR(4));
INSERT INTO S VALUES ('1n1', 'p1', '1n2');
INSERT INTO S VALUES ('1n2', '1pz', '1n3');
INSERT INTO S VALUES ('2n1', '2px', '2n2');
INSERT INTO S VALUES ('2n1', '2px', '2n3');
INSERT INTO S VALUES ('2n3', 'p2', '2n4');
SQL Query
       (a.p='p1' AND a.o=b.s) AS _disj1a, 
       (a.p=b.p AND a.s=b.s AND a.o!=b.o AND b.o=c.s AND c.p='p2') AS _disj1b
     INNER JOIN S AS b ON (a.o=b.s OR a.p=b.p)
     LEFT OUTER JOIN S AS c ON (b.o=c.s AND c.p='p2')
WHERE (a.p='p1' AND a.o=b.s) OR (a.p=b.p AND a.s=b.s AND a.o!=b.o AND b.o=c.s AND c.p='p2')
SQL Solutions
| s    | p    | o    | s    | p    | o    | s    | p    | o    | _disj1a | _disj1b |
| 1n1  | p1   | 1n2  | 1n2  | 1pz  | 1n3  | NULL | NULL | NULL |       1 |       0 |
| 2n1  | 2px  | 2n2  | 2n1  | 2px  | 2n3  | 2n3  | p2   | 2n4  |       0 |       1 |

See Also