Talk:Relational algebra

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Low Priority  Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.
This article is within the scope of WikiProject Databases.
??? This article has not yet received a rating on the assessment scale.
High rated as high-importance on the assessment scale

Contents

[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 think binary operator is a more generally understood term than dyadic operator. I would be in favor of changing that use of terminology back to the way it was. I do, however, agree that operator is more appropriate than operation. Davidfstr 18:48, 26 September 2007 (UTC)
  • 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)
I notice that this operator is strangely missing from the article. AndrewWarden 17:16, 31 January 2006 (UTC)
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)


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

Actualy Datalog is more expressive than relational algebra applyied to DB. This is due to the introduction of operators expressin the complement in term of negation as failure. Anyway it is true that Datalog is the logic programming language more close to relational algebra.

--Paolo Ceravolo

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

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)
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\bowtieS)

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}

\begin{matrix} R\ |\!>\!<\!|\ S \\ i\ \theta\ j \end{matrix}

  • It's called \bowtie.
  • JA: Thanx, and a tip o'th' hat! I knew what it was called, I just didn't know how to tie one! Jon Awbrey 22:24, 1 February 2006 (UTC)

[edit] left outer join

I think that results shown in example of left outer join in the table is wrong - two rows are missing - those with DeptName = "Sales"

[edit] Missing Symbols

Hello, I'm reading with IE7 (unusual?!) and many of the symbols do not appear.

eg In "Set operators", I see

  • R × S = {r BOX s| r BOX R, s BOX S}

(I guess that the last two boxes are espilons, but what is the first?)

In "Natural join", I see

R\bowtieS = { t BOX s : t BOX R, s BOX S, fun (t BOX s) }

And again in the equations throughout the article.

I would go through and fix this, but, as I say, I'm not sure what symbol was intended in some places (and mozilla's not working here at the moment). Sam Staton 20:51, 13 February 2007 (UTC)

I have tried to fix this problem wherever I could spot instances of it on the page. Hope this solves the problem for IE7 users.
--Dessources 13:21, 17 August 2007 (UTC)

[edit] Aggregation

I think the sentence "and we wish to find the branch name with the highest balance, we would write Branch_NameGMax(Balance)(Account)" is incorrect. From what I understand, this will find the max balance in each branch. —The preceding unsigned comment was added by 72.94.106.67 (talk) 03:15, 19 February 2007 (UTC).

Agree, and changed it (revision 10:01, 21 April 2008). Jonas Wagner

[edit] Division Results

Why is Eugene missing? --Weedrat 14:18, 6 May 2007 (UTC)

The division (Completed ÷ DBProject) gives the Students who have entries (in the Completed table) for all the tasks in the DBProject table. In this case the DBProject table only contains two tasks: Database1 and Database2. You see that (Fred, Database1) and (Fred, Database2) are both in the Completed table, therefore Fred is in the result. Similarly, (Sara, Database1) and (Sara, Database2) are both in the Completed table, therefore Sara is in the result. Eugene doesn't have an entry for Database2, so Eugene is not in the result. Egriffin 22:01, 9 November 2007 (UTC)

[edit] Semi Join and anti join

Shouldn't the "Manager" column be there as well or am I wrong here? -Weedrat 13:34, 8 May 2007 (UTC)

[edit] Unicode code points

Is the code point for a bowtie really notable? It's the only occurrence of "Unicode" and "U+" in the article. Should we mention code points for every symbol used? I don't think it belongs in an article about mathematics — I can't recall other articles about maths mentioning code points (equally we could have "In LaTeX, it's \bowtie"). ⇌Elektron 14:44, 13 September 2007 (UTC)

[edit] SQL Analogies

Relational algebra has numerous analogies in SQL implementations. As a large number of database developers are well-versed in the SQL language, and that it's likely that this page would be visited by people who are very familiar with industry language knowledge, it would be useful, where direct analogies exist, to add SQL equivalents to the relational algebra examples.

I would be happy to do this pending approval of each example here in "Talk."

Please note that this is a property of SQL itself, given the semantics of SQL, and not specifically of SQL implementations. The term "analogy" is a bit out of place. Languages like FORTRAN and Java incorporate operations from arithmetic like addition and multiplication; these are not "analogies" of the arithmetic operations. Likewise, SQL incorporates operations from the theory of relational databases, which is based on relational algebra.  --Lambiam 08:59, 17 January 2008 (UTC)