Talk:Relational algebra

From Wikipedia, the free encyclopedia

You have new messages (last change).

1 Reworked Introduction
2 Split
3 Correspondence with first-order logic
4 Circular inclusion dependencies / foreign keys
5 Natural join symbol
6 Projection
7 Joins, natural and otherwise
8 Joins, natural or else
9 left outer join

[edit] Reworked Introduction

Today I pretty well completely rewrote the introduction. The most signficant changes I made are as follows:

I emphasise the possible use of relational algebra in database query languages (the previous introduction gave the impression it was only for internal purposes!), and I give examples of concrete syntaxes that have been devised and implemented on computers.

I hope this isn't controversial, but I changed all uses of "operation" to "operator" and "binary operation" to "dyadic operator". If it is controversial, I am willing to bow to a superior authority.

I tried to clarify Codd's contribution.

I mentioned the all-important connections with predicate calculus.

I partially corrected the previous statement about completeness with respect to predicate calculus, but I left behind the bit about Horn clauses without recursion and negation because I didn't understand it well enough to work out if it is correct. I believe it is not correct, because negation is supported to some extent (via minus) and also because I thought that recursion was missing from FOPC anyway! I will ask around about this and possibly revisit this section later.

Oh, and I made the Introduction into a section with that heading.

I would welcome comments on this work.

AndrewWarden 18:48, 2 February 2006 (UTC)

[edit] Split

Trying to split each of the operations into their own articles, as follows:

I notice that this operator is strangely missing from the article. AndrewWarden 17:16, 31 January 2006 (UTC)

Cartesian product (include example using relational algebra)
Set union (include example using relational algebra)
Set difference (include example using relational algebra)
Rename

I notice that this operator is strangely missing from the article. AndrewWarden 17:16, 31 January 2006 (UTC)

Expressive power
Set intersection (include example using relational algebra)
Natural join
Division (relational algebra)

I hope this won't give Codd's division, which turned out to be a degenerate case of a much more interesting operator, first defined by Stephen Todd for ISBL and further developed by C.J. Date and myself. AndrewWarden 17:16, 31 January 2006 (UTC)

Generalized selection
Theta join
Semijoin
Semiminus (a useful generalization of minus) AndrewWarden 17:16, 31 January 2006 (UTC)
Outer join (delete current redirect and create a formal article with the definition using relational algebra)
- Left outer join (sub-section of the Outer join article)
- Right outer join (sub-section of the Outer join article)

are you thinking of keeping this page as a good overview? this page was quiet helpful when I was going through intro to DB class.

I would like to support the comment above : the page as it is provides a very useful reference for students, especially those who have previously studied (but might now have forgotten) relational algebra.

I agree that having a central Relational algebra page is very useful. I wouldn't mind though if it gave only a brief overview of its key parts, linking to the above proposed articles for more in-depth coverage. Would this still be useful to students? -David Owen

Yeah, page stays as overview while each article of the different operations explains in depth. —Joseph | Talk 04:33, 11 October 2005 (UTC)

I agree having a brief overview page and seperate articles for sub-topics. Makes eveything easier to find and those who are just starting will get the overview using loose terms like "Relational Algebra" GarethWatson 13:34, 27 October 2005 (UTC)

I agree that it was right to move the primative operations to separate pages, but it makes the page hard to follow now. Plenty of Wikipedia pages have a short description accompanied by a link to the full page, and I think that that solution would be best here. 14:44, 4 March 2006 (UTC)

[edit] Correspondence with first-order logic

The statement currently describing the expressive power of the given operators where it equates these with First-order logic can not be true. Look at the page for First-order logic. You will find that First-order logic is undecidable. I believe that with the relational operators given we have something isomorphic to Datalog or first order logic without complex function symbols, i.e. only zero-ary function symbols.

--Gavin Mendel-Gleason

Satisfiability of relational algebra expressions is also undecidable in the sense that you cannot decide whether the result is always empty, but nevertheless you are right that the power of FOL with function symbols is greater than that of the relational algebra. -- Jan Hidders 10:34, 24 January 2006 (UTC)

I don't think it's incorrect, but could perhaps stand to be fleshed out/clarified. The full story requires talk about the interpretation/domain. In addition, a key element in the statement is the restriction to the "safe" parts of FOL (i.e. Codd's safety restrictions), although it is perhaps misleading to identify that restricted language as essentially the same as FOL.

--jkopena

A suitable relation algebra is known to be equivalent to FOL on infinite domains (this is a result of Tarski and Givant). However, the algebra described in this article is not the standard relation algebra used by mathematians; I'm not certain of the precise strength of this scheme. Randall Holmes 01:50, 28 January 2006 (UTC)

[edit] Circular inclusion dependencies / foreign keys

The first example given between the employee and dept is not that great: it suggest a loop in the dependencies for the foreign keys: employee depends on dept, dept depends on employee. Loops in dependencies have to be avoided as they make the entities hard to save and the foreign key fields have to be nullable in all but one entity participating in the loop depencency. Please correct this example, by for example removing Manager from Dept and adding a column 'ManagesDept' to Employee which is another FK to dept.

--Frans Bouma

These considerations don't seem very relevant to me. The purpose of the example is just to illustratie the operations, not how to model. Besides, avoiding circular dependencies is not really part of the theoretical model as it is an artefact of the limitations of certain SQL DBMSs. Moreover, your fix is actually not that uncontroversial either as it introduces a column that must have null values. -- Jan Hidders 10:34, 24 January 2006 (UTC)

[edit] Natural join symbol

The symbol of the natural join in this article doesn't appear correctly in some machines (it appears as a square), as the author initially used some special symbol fonts that some systems may not have. Perhaps the author should consider changing the natural join symbol into an image, so that it can be displayed correctly in all system (previous comment originally left on main article page by 137.132.3.6 (talk • contribs))

Or, we could use ×. It looks almost like the bow-tie symbol, and fits with the =×= syntax for outer joins. -- Mikeblas 00:39, 28 January 2006 (UTC)

[edit] Projection

JA: I just reorganized the gangly projection disambig page and chunked out projection (mathematics) to its own page. Jon Awbrey 17:32, 31 January 2006 (UTC)

But I still don't see a definition of the relational algebra operator called projection, which should be equated to existential quantification in predicate logic. AndrewWarden 18:52, 1 February 2006 (UTC)

JA: Yes, I did only the single (1-column) projection. Still working on it. Have dab*ed to projection (set theory) as projection (mathematics) is still too ambiguous. Jon Awbrey 19:10, 1 February 2006 (UTC)

AW: I've just noticed projection (relational algebra) for the first time, with a history indicating that it's been there for quite some time. I'm puzzled, as I couldn't find it until today. Sorry for any confusion. Now that I've seen it, I see that there are some minor changes I'd like to make. The SQL reference isn't quite right, and there ought to be a note about implementations of projection in computer languages (in particular, the possibility to mention the attributes to be excluded rather than those to be included, the exclusion case being slightly closer, psychologically, to existential quantification). But I'll hang fire until I hear that you've finished what you want to do.

JA: I don't think I'll be touching the relational algebra or relational model articles, except cosmetically, anytime soon, as I'm still refreshing my memory and reviewing newer literature on these more concrete aspects that I last worked with many odd years ago. The relation (mathematics), projection (set theory), and related articles will be pretty standard stuff, from a slightly combinatorial perspective, and so should be pretty independent of what you need here, though I will eventually want to think a little more about the relation between what I think of as "abstract types", that have shapes like X_1 x … x X_k, and "concrete types", where you have meaningful attributes to worry about. But it's way too soon for that. Jon Awbrey 16:22, 2 February 2006 (UTC)

[edit] Joins, natural and otherwise

From Right Outer Join: The right outer join can be simulated using the natural join and set union as follows:

R X= S = S ∪ (R $\bowtie$ S)

From Set Operators: Although three of the six basic operators are taken from set theory, there are additional constraints that are present in their relational algebra counterparts: for set union and set difference, the two relations involved must be union-compatible — that is, the two relations must have the same set of attributes.

The two clauses above are incompatible. What is the correct way of simulating the outer joins with the more primitive operators?

Jon Thoroddsen 14:42, 24 February 2006 (UTC)

$\triangleright \triangleleft$

$\triangleright\!\triangleleft$

Voila! Jon Awbrey 18:01, 31 January 2006 (UTC)

Use \bowtie: $\bowtie$ —Drowne | Talk 00:00, 7 July 2006 (UTC)

[edit] Joins, natural or else

JA: Here's the best that I could do for the θ-join after a day's fiddling with TeX. For some reason the negative space trick does not work in a matrix format, so the center does not hold the two vortices together!

$\begin{matrix}R\ \triangleright\!\triangleleft\ S \\ \ i\ \theta\ j \end{matrix}$