Represent a Subquery in Relational Algebra

Represent a subquery in relational algebra

You would just rewrite that as a join.

I'm not sure how widely used the syntax I learned for Relational Algebra is so in words.

  1. Take a projection of anotherNumber from anotherStack
  2. Rename anotherNumber from the result of step 1 as number
  3. Natural Join the result of step 2 onto collection
  4. Take a final projection of number from the result of step 3

Convert SQL Query to Relational Algebra

Your SQL code will result in duplicate columns for CustomerCode and the use of SELECT [ALL] is likely to result in duplicate rows. Because the result is not a relation, it cannot be expressed in relational algebra.

These problems are easily fixed in SQL:

SELECT DISTINCT * 
FROM Customer NATURAL JOIN Appointment
WHERE Appointment.ServerCode IN
(
SELECT ServerCode FROM Appointment WHERE CustomerCode = '102'
)
;

You didn't specify which relational algebra you are intereted in. Date and Darwen proposed an algebra named A, specified an A language named D, and designed a D language named Tutorial D.

Tutorial D uses operators JOIN for natural join, WHERE for restriction and MATCHING for semijoin, The slight complication is the comparison in SQL:

CustomerCode = '102'

The comparison of a CustomerCode value to a CHAR value in SQL is possible because of implicit coercion. Tutorial D is stricter -- type safe, if you will -- requiring you to overload the equality operator or, more practically, define a selector operator for CHAR, which would typically have the same name as the type.

Therefore, the above (revised) SQL may be written in Tutorial D as:

( Customer JOIN Appointment ) 
MATCHING ( ( Appointment WHERE CustomerCode = CustomerCode ( '102' ) ) { ServerCode } )

Relational Algebra equivalent of SQL NOT IN

In relational algebra, you can do this using a carthesian product. Something like:

R - ρa1,a2a11,a21A11 = A22a11,a21(R) x ρa12, a22(R))))

  • rename the columns of R, f.e. from a1 to a11 (left hand) and a12 (right hand)
  • take the cross product of the R's with renamed columns
  • select rows where a11 equals a22
  • project out a12 and a22 and keep a11 and a21
  • rename to a1 and a2

That gives you the rows that were matched. Subtract this from R to find the rows that where not matched.

Is it possible to decorrelate all correlated SQL subqueries?

First of all, it is possible to express correlated sub queries (-> dependent joins) in relational algebra and also aggregates.

You might be interested in this: http://www.btw-2015.de/res/proceedings/Hauptband/Wiss/Neumann-Unnesting_Arbitrary_Querie.pdf

I haven't read the entire paper, but I attended a class with Professor Neumann. He claimed that you can decorrelate arbitrary queries.
However there are some limitations I believe.

select *
from T1
where T1.a = (select T2.a from T2 where T2.b = T1.b)

In principle it would be easy to decorrelate this query and I after looking at the query plan I believe the database system at their chair is able to do that (https://hyper-db.de/interface.html). I think you could not express that in SQL though, since here you get a runtime error if the subquery does not return a scalar (https://blogs.msdn.microsoft.com/craigfr/2006/09/27/scalar-subqueries/).

How to convert JOIN SQL query to relational algebra?

Maybe you need some looks like:

SELECT
staff.STF_FirstNames AS `Doctor First Name`,
staff.STF_LastName AS `Doctor Last Name`,

patient.PAT_FirstNames AS `Patient First Name`,
patient.PAT_LastName AS `Patient Last Name`,

patient_makes_appointment.APP_DateTime AS `Appointment Time`

FROM staff, doctor, patient, patient_makes_appointment
WHERE staff.STF_ID = doctor.STF_ID
AND doctor.DOC_ID = patient.DOC_ID
AND patient.PAT_ID = patient_makes_appointment.PAT_ID

Simplify nested queries

I don't see how your question relates to regular expressions at all. If you want the names of the persons that co-authored with John Doe though, I would recommend joins:

select distinct pe2.name
from person pe1
inner join author au1 on au1.pid = pe1.pid
inner join author au2 on au2.aid = au1.aid and au2.pid <> au1.pid
inner join person pe2 on pe2.pid = au2.pid
where pe1.name = 'John Doe'

The query starts from person John Doe, and brings the corresponding rows in author; then, it searches for all co-authors, and finally brings their names.

How to represent relational division(basic algebra expression) in terms of SQL

Given this DDL for tables corresponding to your relevant relations:

create table Boats(
bid int,
bname varchar(50),
color varchar(50)
);

create table Reserves(
sid int,
bid int,
day date
);

You can transliterate the division formula (3) into Oracle SQL syntax fairly straightforwardly, though it's verbose:

-- All sailors who reserved at least one boat
SELECT DISTINCT sid
FROM Reserves

MINUS

-- All sailors who reserved at least one boat, but not all of them
SELECT sid
FROM (
-- all combinations of a sailor who reserved any boat with any boat
-- available to be reserved:
SELECT Reserves.sid, Boats.bid
FROM
Reserves
CROSS JOIN
Boats

MINUS

-- all combinations of sailor and boat for actual reservations made
SELECT sid, bid
FROM Reserves
) sids

As specified, that uses only the CROSS JOIN and MINUS operations, so as to correspond directly to the relational algebra formula. In a real-world database application, however, one would surely obtain the same result via an altogether different query.

Note also that SQL databases can and do violate the principle of formal relational algebra that relations do not contain duplicate tuples. That is the reason for SELECT DISTINCT in the first subquery. Distinct selection applied strategically elsewhere in the query might make it more efficient, but would not alter the result.



Related Topics



Leave a reply



Submit