Questions tagged [relational-algebra]

the study of relations (i.e., database tables) and relational operators (join, selection, projection, etc.) as a kind of algebraic structure.

Filter by
Sorted by
Tagged with
0 votes
1 answer
300 views

SQL, optimizing a select statement in relational algebra

is it possible to rewrite the following sql statement $\pi_{R.a,S.d} (\sigma_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}((R\times S)\times T))$ ? My problem is, i dont know if it is possible to ...
2 votes
1 answer
133 views

What do the commas separating atomic events in a Relational Calculus formula means?

For instance, take the example of this book here on page 30. About the formula $$ Q(x,x') = R(x), S(x,y), S(x',y), R(x') $$ described there, what do the commas mean? Is it the same as an "and" ...
0 votes
1 answer
210 views

Relational division

I try to understand how the relational division can be expressed by primitive operations of the relational algebra. So, I found this formula (I writed it such as I found it in the same format): $A \...
2 votes
1 answer
427 views

Type Theory and Principia Mathematica Part IV "Relation Arithmetic"

As type theory is a principle focus of modern computer science, its origins are in Bertrand Russel's theory of types, Principia Mathematica is both the origin of and is expressed in the theory of ...
4 votes
1 answer
618 views

Difference between the Cartesian product in set theory and in relational algebra

What's the difference between the Cartesian product in set theory and in relational algebra? The Cartesian product in set theory is defined as: $$A \times B = \{(a, b) \mid (a \in A) \land (b \in B)\...
5 votes
4 answers
5k views

When should you use the existential and universal quantifiers for Relational Calculus?

Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus? Given this schema: Hotel(hotelNo, hotelName, city) ...
0 votes
0 answers
24 views

How many passes does it take to join 2 relations of fixed size with M buffer blocks?

So let's say 2 relations, B(R) = 200,000 and B(S) = 300,000. The memory buffer is M = 400 blocks. How many passes would this take to join? Notation:
1 vote
0 answers
387 views

Relational algebra for multiple legs of a flight

I'm trying to write the relational algebra for a problem related to this schema: I want to do the following: For each flight list the departure airport code for the first leg of the flight and the ...
1 vote
0 answers
169 views

How to find the least optimised database query?

A library uses a relational database to store data about library books, their members and lending (books, which are currently borrowed). The database relations of this system are given below. Lengths ...
2 votes
2 answers
6k views

Finding the Candidate Keys of a Relation Using the FD's

I have definitely checked out many different related posts. I have also done different sample problems from online sources as well from a similar problem. However, I am stuck on the problem below ...
0 votes
1 answer
449 views

Joining tables with minimum number of joins

I am working on a generalized problem where I am given only schema definition of multiple tables that i have. Now i have to retrieve certain columns by joining multiple tables such that number of ...
1 vote
1 answer
70 views

Can a $k$-ary relation have polymorphisms of arity greater than $k$?

To quote Hubie Chen's A Rendezvous of Logic, Complexity, and Algebra (2009) on constraint satisfaction and complexity, An operation $f : D^m \to D$ is a polymorphism of a relation $R \subseteq D^k$ ...
3 votes
1 answer
391 views

Smallest set of features that would make relational algebra Turing complete

I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete. Probably just recursion (something like "MY_QUERY(param) = select * from param UNION ...
0 votes
0 answers
53 views

Proof of RAP-derivation sequence for a set of functional dependencies in relational databases

I'm reading David Maier's outstanding but out-of-print book on relational databases (the book,"The Theory of Relational Databases", is available online from the author's website http://web.cecs.pdx....
-1 votes
1 answer
6k views

Count in relational algebra using Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }

schema(author)={name, newspaper} The table contains a list of authors. Each author works for a newspaper. So a single newspaper may employ multiple authors. How ...
0 votes
3 answers
169 views

Relational query for universally quantified formula

My university is participating in the implementation of a library borrowing managing system at Richelieu National Library in France. I received the order to formulate the query: "find all users ...
4 votes
1 answer
1k views

NL and NP compute different binary relations, so what?

Let the binary relation computed by a nondeterministic transducer be the relation between input strings and the possible output strings the transducer can produce (and accept) for the given input ...
2 votes
1 answer
53 views

Combinations of elements with mutual relationships

I need to create the combination of 3 elements from a array of given n elements, however every of those 3 el. has to be in "relationship" with each other. Here is an example I can describe my issue ...
2 votes
0 answers
266 views

Using cross-products with relational algebra

I have some questions about something that I'm working on in an assignment for my database class. Here is the schema for the questions I'm working on, so that you know what to refer to: ...
8 votes
1 answer
749 views

A relational algebra extended to model the full DML ("CRUD") domain

There are multiple references about the relational algebra for modeling queries (SELECT) but I have found very very little on the expanded algebra that would ...
0 votes
0 answers
457 views

Algorithm to test dependency preservation

Is there an algorithm to test whether the decomposition of relation $R$ into relations $R_1,\dots,R_n$ is dependency-preserving? In more detail, I am given a relation $R(x_1,\dots,x_m)$ on $m$ ...
1 vote
0 answers
134 views

Is existential quantifier redundant

I was reading Tuple Relational Calculus from a textbook. I came across this query: For every project located in 'Stafford', list the project number, the controlling department number, and the ...
0 votes
0 answers
155 views

Relational Algebra - Mistake in the quiz?

I've just done a mini test and scored 9/10, however, from my understanding, I think this question is incorrect. Here is the only question which I don't understand how it can be correct: So I joined ...
0 votes
0 answers
903 views

convert domain relational calculus with two same tuples to relational algebra

Given two relations $R(A, B)$ and $S(A, C)$. I can understand the early part is the projection of attribute $A$ from $S$, which could be written as $π_a(S)$, but later part is confusing and not ...
0 votes
1 answer
2k views

Resolving many to many relationships?

I'm trying to separate a weird relationship. It goes like this: One waiter can serve more than one kind of drink and one kind of drink can be served by more than one waiter. One waiter can wear more ...
1 vote
0 answers
27 views

In search for toy relations to test relational algebra

Does anybody know any toy database / relations that are particularly good and also complete to demonstrate and test relational algebra concepts? I'm hoping some database researchers should have ...
1 vote
1 answer
193 views

What does superscript + mean in relational algebra?

What does superscript + mean in relational algebra? Suppose $A$ is a subset of attributes of all attributes in a relation $R$. What does $A^+$ mean?
1 vote
1 answer
45 views

Finding representatives of equivalence classes

I have a table of pairs of objects, which defines an equivalence relation. How can I extract a single object from each of the equivalence classes using relational algebra? It can easily be done with ...
2 votes
1 answer
582 views

Equivalence relation Mathematical base In Computer science

I have this equivalence relation problem: Let $R$ and $S$ be two equivalence relations on the same set $A$. Define a new relation $U$ such that $U(x,y) \leftrightarrow [R(x,y) \text{ or } S(x,y)]$. ...
29 votes
3 answers
2k views

Do subqueries add expressive power to SQL queries?

Does SQL need subqueries? Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL ...
4 votes
2 answers
13k views

"At least one" clause in Relational Algebra

I'm fairly new to the syntax of relational algebra, and I'm having a hard time understanding how I could set a "at least one" clause. Example: I have: a table with books (listing the title, year ...
19 votes
2 answers
1k views

Does the 'difference' operation add expressiveness to a query language that already includes 'join'?

The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases ...
0 votes
1 answer
212 views

relational algebra and SQL

Using the following relations: ...
4 votes
1 answer
280 views

Computing number of block reads given relational algebra statement

So I'm just starting to learn about query processing and such in databases and I'm having some trouble. I don't really understand how to compute the minimum number of block reads given a relation and ...
4 votes
1 answer
158 views

Origin of theta-joins

I've taken an introductory database course where like many good database courses, they taught relational algebra, including $\theta$-joins. However, I've recently read E. F. Codd's 1970 paper, A ...
4 votes
1 answer
2k views

What is OUTER UNION and why is it partially compatible

I am trying to understand how a OUTER UNION $∪^✳$ works, and why it is only partially compatible. I am aware this operation was created to take union of tuples ...
6 votes
2 answers
136 views

Optimizing a join where each table has a selection

Consider the following query: ...

1
2