Re: Can relational alegbra perform bulk operations?

From: Tegiri Nenashi <>
Date: Tue, 29 Sep 2009 14:49:44 -0700 (PDT)
Message-ID: <>

On Sep 29, 12:50 pm, Banana <> wrote:
> I suppose it's true that we can transform an expression into anything
> else and could conceivably add as many zeros for additive/subtractive
> operations or ones for multiplication/division operations and still have
> logically equivalent expressions, but such expansion would hardly be
> interesting in absence of further transformation.

I'm not following your "add zeroes" idea, but if you are saying that only those transformations that lead to "shorter" relational expressions make sense from optimization perspective, than this is not true. E.g. "magic" transformation.

> Even so, wouldn't it be fair to say that in order to optimize any given
> query upon relation, we would want to find the most simple (or maybe
> it's accurate to say 'concise') expression that is computationally
> simple to execute compared to other but equivalent expressions?

Are you familiar with cost based optimization? They basically throw in multiple equivalent expression and estimate cost of running each apriori.

> However, could I ask you to explain the statement that tuples aren't
> referred at all in relational algebra?

Simple. Take projection for example. It contains the pi symbol together with attributes names. Ditto selection and the others.

> Back to the r and s example, if I were to join them based on an
> attribute x, I would have to look at all possible values in attribute x
> of the relvar r then go to s and look up each tuples in relvar s and
> verify whether its attribute x has the same value and thus 'select' the
> tuple into the resultant output. I've just described an iterative manner
> of evaluating what tuples may participate in a join and that's precisely
> concerns me; was that actually necessary or does there exist an operator
> to process them in bulk?

That is called nested loops join. It is implementation; algebraically (natural) join is idempotent, symmetric, and associative operation.

> Or maybe to attempt an analogy, when we multiply two numbers, we need
> not add each number to itself as many times as specified by other
> operand. It's valid but not the only way to determine the product; we
> certainly can determine product by recalling the product from
> multiplication table and even for an arbitrarily large operands, use the
> same algorithm to quickly arrive at a product.. Does such concept exist
> for operating upon relations in like manner?

In this respect Bob's answer was spot on: while nested loops is quite inefficient operator, the indexed nested loops isn't. Received on Tue Sep 29 2009 - 23:49:44 CEST

Original text of this message