A Relational View of the Semantic Web
by Andrew Newman
|
Pages: 1, 2, 3, 4
Relational SPARQL Operations
Given that RDF can be represented using a flexible, untyped relational model what modifications to relational operations are needed and how do they relate to SPARQL operations? A subset of SPARQL operations will be covered including: JOIN ("."), UNION, and OPTIONAL and a modified relational algebra will be given to support these operations.
The first modification required, one suggested by Richard Cyganiak [3], is an untyped join (SPARQL's JOIN). An untyped join allows tuples in relations to be successfully joined except if a value in one relation conflicts with the value in the other. If a value is unbound in one tuple but is bound in another then the bound value is added to the result tuple.
A formal definition of an untyped JOIN (based on Date's definition of Join [4]):
Let r and s have attributes X1,X2,...,Xm, Y1,Y2,...,Yn, Z1,Z2,...,Zp. Where Y's are the common attributes, X's are other attributes of r and Z's are the other attributes of s. The untyped JOIN of r and s is a relation t with a heading that is the set theoretic union of the headings r and s {X, Y, Z} and a body that consists of the set of all tuples {X x, Y y, Z z} such that a tuple appears in r with X value x or no value for X and Y value y and a tuple appears in s with Y value y and Z value z or no value for Z. Y values for r and s may both be unbound or either maybe unbound - this does not lead to a successful join. A successful join occurs if at least one Y value y for r and s are equal and are not unbound.
This is different to SQL and some definitions of relational algebra where NULL values (NULL being considered equivalent to an unbound value) cause join failure. This behavior of joining shared attributes in r and s is shown in Table 7. An example of an untyped join of relation r (Table 8) and relation s (Table 9) is shown in Table 10.
|
Values of Shared Attributes |
Typed Join |
Untyped Join |
|
r{Y = y}, s{Y = y} |
Joined |
Joined |
|
r{Y = y}, s{Y = x} |
Rejected |
Rejected |
|
r{Y = {}}, s{Y = y} |
Rejected |
Y = y if Joined |
|
r{Y = y}, s{Y = {}} |
Rejected |
Y = y if Joined |
|
r{Y = {}}, s{Y = {}} |
Rejected |
Y = {} if Joined |
Table 7. Results of a Shared Attribute (Y) of Two Relations r and s
|
SNO |
sno |
SNAME |
Name |
|
S1 |
"Smith" |
||
|
S2 |
"Jones" |
||
|
S3 |
"Blake" |
||
Table 8. Relation r
|
SNO |
sno |
SNAME |
name |
STATUS |
integer |
CITY |
char |
|
S1 |
"Smith" |
20 |
"London" |
||||
|
S2 |
"Jones" |
10 |
|||||
|
S3 |
"George" |
||||||
|
SNO |
sno |
SNAME |
name |
STATUS |
integer |
CITY |
char |
|
S1 |
"Smith" |
20 |
"London" |
||||
|
S2 |
"Jones" |
10 |
|||||
Table 10. Result of Untyped Join of r and s
The second untyped operation takes the proposal by César Galindo-Legaria [6] for an outer union operator and its use in the definition of left outer join (which is analogous to SPARQL's UNION and OPTIONAL respectively). OUTER UNION provides the same semantics as SPARQL's UNION operation while being formally defined and grounded in the relational model. Furthermore, SPARQL's OPTIONAL operation can be composed of outer union and set difference, project, and untyped join.
A formal definition of OUTER UNION:
The outer union of relations r and s is the set theoretic union of the headings of r and s with a body consisting of all tuples t such that t appears in r or s or both. It does not require that r and s have the same attributes (types) as specified by the regular relational union.
Table 11 shows the result of performing an outer union of relations r and s from Tables 8 and 9.
|
SNO |
sno |
SNAME |
name |
STATUS |
integer |
CITY |
char |
|
S1 |
"Smith" |
20 |
"London" |
||||
|
S2 |
"Jones" |
10 |
|||||
|
S3 |
"Blake" |
||||||
|
S1 |
"Smith" |
||||||
|
S2 |
"Jones" |
||||||
|
S3 |
"George" |
||||||
Table 11. Result of Outer Union of r and s
