Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
24 views

Doubt regarding foreign key and referential integrity

I am studying database from Database System Concepts. The author was explaining foreign keys and referential integrity with the help of following schemas: $$ instructor(\underline{ID},\space name,\...
0
votes
1answer
20 views

Whether same output is obtained for the two queries

Consider the following SQL Queries executed on the relation Employee: Employee (Eid, Ename, sal) Eid is the primary key Queries: S1:SELECT count (*) FROM Employee; S2: SELECT count (Eid)...
0
votes
1answer
34 views

Normal form of relation R

It is given that for a relation R all the attributes of the relation appear in some of the candidate keys. It is also given that there is only one compound candidate key which exists for a relation, ...
0
votes
0answers
40 views

Query Optimisation (Relational Algebra)

A generic SQL statement like the following can be translated directly to a relational algebra expression: SELECT A1, A2, …, An FROM T1, T2, …, Tm WHERE C ...
-1
votes
2answers
52 views

Is it possible to do a NULL comparison in Relational Algebra?

Please consider the following question given in a booklet: I have read about databases from Database System Concepts - by Henry F. Korth, but never saw an instance where we could do a NULL comparison ...
1
vote
1answer
62 views

Relational calculus to SQL

I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a ...
0
votes
1answer
83 views

Use of existential quantifier in tuple relational calculus

It is somewhat confusing to me when to use quantifiers in tuple relational calculus (TRC). I stumbled upon following problem and I am still scratching my head thinking why not TRC query can be ...
0
votes
1answer
51 views

How to print all pairs of ID numbers such that the corresponding people don't belong to the same socieities

I want to express the following in relational algebra: Given a table of PEOPLE: ID, SocietyName Where the combination of ID and SocietyName form a key such that ...
-2
votes
1answer
60 views

Query Super Type and Subtype in Mysql

Assuming I have a schema depicted in the image , showing relationships(specialization) between Staffs, Academic Staffs and Non Academic Staffs. Is it possible to have a query that retrieves the ...
2
votes
0answers
196 views

Algorithm for segmenting input query into query/join tree

Wondering what algorithms look like for implementing a complex JOIN query handler. Taking a look at this paper Building Query Compilers they talk about Query Graphs ...
0
votes
1answer
155 views

How to prove/disprove distribution of division over union

How can I prove distribution of division over union in relational algebra, i.e. the following: $$(R \cup S) / X \overset{?}{=} (R / X) \cup (S / X)$$
-1
votes
1answer
103 views

What is the equivalent form of full outer join in relational algebra?

Considering only basic relational algebra operations, how can we implement the full outer-join ?
1
vote
1answer
381 views

relational algebra to get unique pairs

Let's say we are given this table of the relation Person(name, hobby) ...
0
votes
0answers
33 views

finding third functional dependency and its candidate keys

i'm solving a multi part question regarding candidate keys and functional dependencies. now i've already found 2 dependencies(the canonical covering of the functional dependencies contains only 3 ...
2
votes
0answers
110 views

Two related partial order relations

We will consider a set whose elements I call "precedences". Precedences are related by two relations: "is subclass of" and "higher than", which are specified by some pairs (given on algorithm input) ...
2
votes
2answers
230 views

Max() in Domain Relational Calculus

I was looking through my notes on domain relational calculus, and noticed an interesting result in a question about finding the most expensive pizza(s), given a pizza table with schema $\text{pizza}(\...
0
votes
0answers
96 views

Domain relational calculus to relational algebra

I have an expression in DRC $\{\langle a,b,c \rangle \mid \langle a,b \rangle \in r \land \langle a,b \rangle \in s\}$, where $r = (A,B)$ and $s = (A,C)$. I want to convert it onto relational algebra ...
1
vote
1answer
119 views

Automatically merging relational data

Background Semiautomated file merging is a critical part of version control systems (all the ones I've used anyway!). This is usually accomplished on textual source code without the tool ...
4
votes
2answers
349 views

Relational algebra and indexes

How might indexes be represented in the context of relational algebra? How would an optimizer transform a query to use indexes?
1
vote
1answer
88 views

Is Datalog negation and the built-in predicate $ \neq $ similar?

I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking ...
0
votes
1answer
147 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 ...
3
votes
1answer
57 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" ...
4
votes
1answer
225 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)\...
2
votes
1answer
327 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 ...
0
votes
1answer
105 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
2answers
3k views

Expressing division in relational algebra in terms of other operations

So, I've been conferred upon the opinion that: Union, difference, cross product, selection, projection form the "complete set of relational operations". That is, any other relational operation ...
0
votes
1answer
245 views

How are quantifiers meant to be used in tuple-relational calculus?

(apologies for the incorrect tag, there was no relational-calculus tag) In this lecture video the following tuple-relational calculus formula is given: $\{ P | \exists S \in \text{Sailors} ( S.\text{...
11
votes
1answer
418 views

Is there an isomorphism between (subset of) category theory and relational algebra?

It comes from big data perspective. Basically, many frameworks (like Apache Spark) "compensate" lack of relational operations by providing Functor/Monad-like interfaces and there is a similar movement ...
0
votes
0answers
22 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
0answers
161 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 ...
2
votes
0answers
96 views

Relational Algebra obtaining a list of duplicates

I've tried researching, and my best strategy I've got is to attempt to pull out data from the table, and then push the data against itself in order to remove all duplicates, ending up with a table of ...
1
vote
0answers
115 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 ...
0
votes
1answer
215 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
1answer
45 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$ ...
0
votes
0answers
36 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....
0
votes
1answer
799 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
3answers
129 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
1answer
290 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
1answer
27 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
0answers
112 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: ...
6
votes
1answer
565 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
0answers
286 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$ ...
2
votes
2answers
5k 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 ...
5
votes
4answers
2k 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) ...
1
vote
0answers
77 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
0answers
107 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 ...
2
votes
1answer
22k views

Use count() in relational algebra

Person(name, phone) Mike 456-789 Mike 123-456 John 230-785 $\dots \dots$ How to get those people who have more than one phone numbers with relational algebra? This sounds simple, but I am ...
0
votes
0answers
712 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 ...
1
vote
0answers
24 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
1answer
98 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?