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
1answer
16 views

Are entities in a many-to-many relation related individually?

I know in some many-to-many relationships, an entity is related to other entities on an individual basis. But is this always the case? For example, in the ...
0
votes
0answers
12 views

What is the difference between Instance of a relation and Instance of a relation schema?

Following question was asked in the exam. The correct answer to this question is 2. But, I feel that it is a wrong answer. Option 2 is an example of instance of a relation and not an example of ...
0
votes
0answers
30 views

For which instance are those relational queries equivalent?

I have the following problem and i hope you could help me. Given is the following database schema, Student($\underline{\text{MatNo}}$, SName) Course($\underline{\text{CNo}}$, CName) Took($\...
0
votes
0answers
39 views

Can I combine these two relations from the relational model?

I have the following task: Translate the following ER diagram to the relational model. Use as few relations as possible. Do not increase or decrease the capacity. How many relations does the ...
0
votes
0answers
55 views

Relational Algebra with only one operator?

There's a parlour game of inventing exotic operators for Relational Algebra, and thereby reducing the number of operators needed to be 'Relationally Complete'. A popular operator for this is 'Inner ...
0
votes
1answer
149 views

Why “ every non-prime attribute of R is non-transitively dependent on every key of R” in the original def of 3NF?

I have read the definition in of Third_normal_form here , which shows The third normal form (3NF) is a normal form used in database normalization. 3NF was originally defined by E.F. Codd in 1971.[2]...
0
votes
1answer
86 views

Is it possible to encode logical expression and interpret it with SQL?

Is it possible without any forms of eval or stored procedures to execute a query, which interprets logical expression, encoded in some way in a table (or two tables)...
0
votes
1answer
59 views

Finding the frequency of each unique value of an attribute in a relation (RELATIONAL ALGEBRA)

I am trying to figure out how I can use aggregate functions to solve this problem. For example if I had the table enrolled(student-id, course-id) 123 897 123 645 589 452 009 897 If I wanted to ...
5
votes
1answer
47 views

“Functional dependencies” with cardinality constraints

Let us write $\{ A_1, \ldots, A_k\} \rightrightarrows^n \{B_1, \ldots, B_m\}$ for a relation $R$ if for all $\langle a_1, \ldots, a_k\rangle$ we have $\left\lvert \pi_{B_1, \ldots, B_m} \sigma_{\...
0
votes
1answer
67 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
32 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
46 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
53 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
457 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
231 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
150 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
154 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
181 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 ...
3
votes
0answers
321 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
215 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
186 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
1k 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
123 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
528 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
140 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
176 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
406 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
129 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
173 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
1answer
62 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
312 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
354 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
143 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 \...
3
votes
2answers
6k 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
485 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{...
12
votes
1answer
548 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
23 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
209 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
134 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
157 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
284 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
48 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
37 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
1k 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
143 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
451 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
28 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
159 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
593 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 ...