[Tockit-general] Relational algebras

[Peter Becker]

Hi again,

slightly different topic now: the plural version. I have implemented a
whole set of operators for relations in the form I like them (or better:
the form that I hope I will like once I use it). Here is a list in
alphabetical order with arity and constructor arguments:

- crossproduct: 2, ()
- drop columns: 1, (int[])
- identity: 1, ()
- intersection: 2, ()
- join: 2, (int[],bool,int[], bool) -- this one takes the columns to
join on and if they should be dropped for each side
- negation: 1, (Set[]) -- relations don't have signatures, so we need to
give the domains
- pick columns: 1, (int[]) -- allows permutations and repetitions
- selection: 1, (TuplePredicate) -- has two static methods for col=value
and col1=col2 checks
- union: 2, ()

I think this is enough to implement pretty much everything I can think
of. Thinking about it: I'll add a permutation operation for the same
reason I did the drop column one -- you don't want to specify every
column you want to keep. It'll take an int[], too -- with the usual
rotational semantics, i.e. [2,4,5] means (abcde) turns into (adceb)
(code: "new int[]{1,3,4}").

Of course it doesn't match any classical relational algebra (or at least
I wouldn't expect it to). To fix that problem, I plan to introduce
factories which give exactly the operations a particular algebra allows.
For example the factory method for a join could be:

public static BinaryRelationOperation getJoin(int[] leftColumns, int[]
rightColumns) {
return new JoinOperation(leftColumns, true, rightColumns, true);
}

for the PeirceAlgebra class and

public static BinaryRelationOperation getJoin(int[] leftColumns, int[]
rightColumns) {
return new JoinOperation(leftColumns, false, rightColumns, true);
}

for a more SQLish one (of course SQL uses names, but you know what I mean).

The question now is: what are the algebras we want to have? Can someone
give me a few references to relevant papers (ideally Citeseer links), so
I can create the factories matching the algebras presented?

Thanks,
Peter

[J. Hereth Correia]

Post by Peter Becker
Hi again,
slightly different topic now: the plural version. I have implemented a
the form that I hope I will like once I use it). Here is a list in
- crossproduct: 2, ()
- drop columns: 1, (int[])
- identity: 1, ()
- intersection: 2, ()
- join: 2, (int[],bool,int[], bool) -- this one takes the columns to
join on and if they should be dropped for each side

Two bool values don't make much sense - I don't know of any join
operation that keeps both columns. And if you keep only one, it should
be the same value anyway. (Or is this about the naming problem?). I
propose to keep only one bool value which defaults to false (the SQL
version)

And how about a simple version with int instead of int[]. In the algebra
you usually only two columns not more in one step.

Post by Peter Becker
- negation: 1, (Set[]) -- relations don't have signatures, so we need to
give the domains
- pick columns: 1, (int[]) -- allows permutations and repetitions

and projections, I suppose?

Post by Peter Becker
- selection: 1, (TuplePredicate) -- has two static methods for col=value
and col1=col2 checks
- union: 2, ()
I think this is enough to implement pretty much everything I can think
of. Thinking about it: I'll add a permutation operation for the same
reason I did the drop column one -- you don't want to specify every
column you want to keep. It'll take an int[], too -- with the usual
rotational semantics, i.e. [2,4,5] means (abcde) turns into (adceb)
(code: "new int[]{1,3,4}").
Of course it doesn't match any classical relational algebra (or at least
I wouldn't expect it to). To fix that problem, I plan to introduce
factories which give exactly the operations a particular algebra allows.
public static BinaryRelationOperation getJoin(int[] leftColumns, int[]
rightColumns) {
return new JoinOperation(leftColumns, true, rightColumns, true);
}
for the PeirceAlgebra class and
public static BinaryRelationOperation getJoin(int[] leftColumns, int[]
rightColumns) {
return new JoinOperation(leftColumns, false, rightColumns, true);
}
for a more SQLish one (of course SQL uses names, but you know what I mean).
The question now is: what are the algebras we want to have? Can someone
give me a few references to relevant papers (ideally Citeseer links), so
I can create the factories matching the algebras presented?

I don't have references handy. But from one of my papers, some
definitions for ... algebras over a set A:

(1) 0-ary \Delta:= \{ (a,a) | a \in A \}
(2) intersection
(3) cross product
(4) pr_I: projection on the columns in I
(5) permutation of coordinates
(6) union of relations of the same arity
(7) complementation

(1)-(5) is a relational algebra
(1)-(6) is a weak Krasner algebra
(1)-(7) is a Krasner algebra

This is according to R. Poeschel and L. Kaluznin, Funktionen- und
Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin, 1979,
Birkhaeuser Verlag Basel, Math. Reihe Bd. 67, 1979.

We're still discussing the base set of operations for the Peircean
Algebraic Logic, but I suppose it will be those I worte in my last mail.

I suppose, you will find another set of operations for Tarskis
Relational Algebra in:

A. Tarski, On the calculus of relations. J. Symbolic Logic 6, (1941), 73
89.

But he only considers binary relations.

HTH,

Jo

Post by Peter Becker
Thanks,
Peter
-------------------------------------------------------
This SF.Net email sponsored by: Free pre-built ASP.NET sites including
Data Reports, E-commerce, Portals, and Forums are available now.
Download today and enter to win an XBOX or Visual Studio .NET.
http://aspnet.click-url.com/go/psa00100003ave/direct;at.aspnet_072303_01/01
_______________________________________________
Tockit-general mailing list
https://lists.sourceforge.net/lists/listinfo/tockit-general

[Peter Becker]

Post by J. Hereth Correia

Post by Peter Becker
Hi again,
slightly different topic now: the plural version. I have implemented a
the form that I hope I will like once I use it). Here is a list in
- crossproduct: 2, ()
- drop columns: 1, (int[])
- identity: 1, ()
- intersection: 2, ()
- join: 2, (int[],bool,int[], bool) -- this one takes the columns to
join on and if they should be dropped for each side

Two bool values don't make much sense - I don't know of any join
operation that keeps both columns. And if you keep only one, it should
be the same value anyway. (Or is this about the naming problem?). I
propose to keep only one bool value which defaults to false (the SQL
version)
And how about a simple version with int instead of int[]. In the algebra
you usually only two columns not more in one step.

The implementations are made to give the most flexibility. If you keep
one column the question is: which one? With two bools that is easy to
model. Of course I could have done a three-valued version (none, left,
right -- skipping the both option), but using the bools seemed fair enough.

The actual signatures one would expect will be in static methods -- I
decided yesterday that it would be worthwhile having three ways of
access: (1) via the operation instances (2) via statics on the operation
classes and (3) via groupings in algebra specific factories. That
includes possible shortcuts like using int instead of int[]. I am going
to add the static methods soon, they are probably what most naive users
would use. You would e.g. call JoinOperation.join(left, leftCol, right,
rightCol). I need the instances so I can move operations around in my
programs.

Post by J. Hereth Correia

Post by Peter Becker
- negation: 1, (Set[]) -- relations don't have signatures, so we need to
give the domains
- pick columns: 1, (int[]) -- allows permutations and repetitions

and projections, I suppose?

of course. The drop supports only projections, this one does it all. It
actually does all the drop and the permute do, but you'd need to create
a suitable int[] based on the arity of the relation used. That is why I
have three operations now.

Post by J. Hereth Correia

Post by Peter Becker
- selection: 1, (TuplePredicate) -- has two static methods for col=value
and col1=col2 checks
- union: 2, ()
I think this is enough to implement pretty much everything I can think
of. Thinking about it: I'll add a permutation operation for the same
reason I did the drop column one -- you don't want to specify every
column you want to keep. It'll take an int[], too -- with the usual
rotational semantics, i.e. [2,4,5] means (abcde) turns into (adceb)
(code: "new int[]{1,3,4}").
Of course it doesn't match any classical relational algebra (or at least
I wouldn't expect it to). To fix that problem, I plan to introduce
factories which give exactly the operations a particular algebra allows.
public static BinaryRelationOperation getJoin(int[] leftColumns, int[]
rightColumns) {
return new JoinOperation(leftColumns, true, rightColumns, true);
}
for the PeirceAlgebra class and
public static BinaryRelationOperation getJoin(int[] leftColumns, int[]
rightColumns) {
return new JoinOperation(leftColumns, false, rightColumns, true);
}
for a more SQLish one (of course SQL uses names, but you know what I mean).
The question now is: what are the algebras we want to have? Can someone
give me a few references to relevant papers (ideally Citeseer links), so
I can create the factories matching the algebras presented?

I don't have references handy. But from one of my papers, some
(1) 0-ary \Delta:= \{ (a,a) | a \in A \}
(2) intersection
(3) cross product
(4) pr_I: projection on the columns in I
(5) permutation of coordinates
(6) union of relations of the same arity
(7) complementation
(1)-(5) is a relational algebra
(1)-(6) is a weak Krasner algebra
(1)-(7) is a Krasner algebra
This is according to R. Poeschel and L. Kaluznin, Funktionen- und
Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin, 1979,
Birkhaeuser Verlag Basel, Math. Reihe Bd. 67, 1979.
We're still discussing the base set of operations for the Peircean
Algebraic Logic, but I suppose it will be those I worte in my last mail.
I suppose, you will find another set of operations for Tarskis
A. Tarski, On the calculus of relations. J. Symbolic Logic 6, (1941), 73
89.
But he only considers binary relations.

Thanks for those.

What about Codd? How does he fit in? Is there some classic reference for
his work?

Peter

[Peter Becker]

J. Hereth Correia wrote:

[...]

Post by J. Hereth Correia

Post by Peter Becker
The question now is: what are the algebras we want to have? Can someone
give me a few references to relevant papers (ideally Citeseer links), so
I can create the factories matching the algebras presented?

I don't have references handy. But from one of my papers, some
(1) 0-ary \Delta:= \{ (a,a) | a \in A \}
(2) intersection
(3) cross product
(4) pr_I: projection on the columns in I
(5) permutation of coordinates
(6) union of relations of the same arity
(7) complementation
(1)-(5) is a relational algebra
(1)-(6) is a weak Krasner algebra
(1)-(7) is a Krasner algebra

I implemented those, calling the first BasicRelationlAlgebra. They are
classes with just static methods, so you can now call

KrasnerAlgebra.intersect(relation1, relation2);

Alternatively you can also use statics on the operations, e.g.:

JoinOperation.join(relation1, 3, relation2, 1);

which joins the two relations matching the fourth column of the first
relation with the second of the second, keeping the full left relation
and dropping column two of the right. If you add a "true" both will be
dropped. Of course int[]s are allowed, too.

This means the code now allows three ways to do things. Might be a bit
confusing, but I think only this way we get all we want. The particular
groupings into algebras give a very math point of view, the statics in
general allow easy access and the option to instantiate operations
allows me to attach them to bits of my code. Unary and binary relations
can also be concatenated into new operations.

Peter