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
0answers
16 views

Insert operation for two tables in Relational Algebra

The given schema is: Publisher(pid, name, location) Book(bid, title, author, page, price) Publish(bid, pid, publish_date) The RA question/query is: Insert new ...
0
votes
1answer
29 views

Incremental View Maintenance for projection

I was reading https://www2.cs.duke.edu/courses/spring02/cps296.1/lectures/08-view.pdf Or in the paper "Incremental Maintenance of Views with Duplicates," by Griffin and Libkin, SIGMOD, 1995. figure 2....
0
votes
1answer
208 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 ...
0
votes
0answers
40 views

How attributes helps us to allow column interchange in a relational database?

A relation on two sets $A$ and $B$ is defined as the subset of the cartesian product $$A\times B = \{(a,b),\ a \in A, b \in B\}$$ A database is also a relation and each entry is an ordered tuple ...
1
vote
1answer
44 views

Check if a relation is reflexive, symmetric and transitive

I want to better understand how this actually works, as my solutions are sometimes not 100% correct. I have the following relation: Check if the following relation is reflexive, symmetric, and/or ...
1
vote
0answers
23 views

Is Neo4J computationally equivalent to relational algebra

I am wondering whether Neo4j and the associated Cypher query language is computationally equivalent to relational algebra? Any ideas or papers on that topic?
1
vote
1answer
55 views

Functional dependencies on relational schema

Given a relational schema $R(V,W,X,Y,Z)$ with functional dependencies $F = \{VW \to X, X \to YZ, W \to VX, V \to W, Z \to XY\}$. What are the keys of $R$? Is the key just $V$? If so, is $\{ R_2(V,W,...
0
votes
0answers
49 views

How to find all tuples in which some attribute appears more than three times

im havin trouble with this exercise. I have a table like this and i can only use relational algebra without aggregate function like sum, count, etc. Name | x a ~~ 1 b ~~ 2 c ~~ 1 d ~~ ...
0
votes
0answers
469 views

Using count() in Relational Algebra

Sell (Bar, Beer) I want a table in which the first column has the name of the beer and the second has the total number of bars which sell that beer, but I have no idea how to use count () in the right ...
1
vote
1answer
56 views

Are intersection and union redundant? Possibility to get smaller output without negation?

I've just started learning relational algebra, so I'm reading a lot of articles for this topic. Not so long ago I've encountered two statements that seem to be quite weird to me. ∩ and ∪ (...
1
vote
1answer
64 views

Need help in understanding these relational algebra queries

I just finished reading about operators in relational algebra and tried to solve this problem. But I dont even understand what the first statement is doing. From what I know, $π$ (project) is a unary ...
0
votes
1answer
63 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) FROM ...
0
votes
0answers
19 views

Relation Closure for F+

$A \rightarrow B C$ $C D \rightarrow E$ $B \rightarrow D$ $E \rightarrow A$ I have these Relations for R={A,B,C,D,E} Now I have to calculate the closure $F^+$ and give the candidate keys I came ...
-2
votes
1answer
24 views

Relational Algebra Queries look same

Query A and Query C seem to be the same.But given answer is query A. Can someone help me to find the difference between queries A and C ?
0
votes
1answer
235 views

Is relational algebra a procedural, imperative, and/or declarative language?

In Database System Concepts 6ed, 6.2 The Tuple Relational Calculus When we write a relational-algebra expression, we provide a sequence of procedures that generates the answer to our query. The tuple ...
1
vote
0answers
104 views

Using relational algebra to express all with a condition

I encountered this question while revising for my finals exam on database theory. The following database contains information about car repair workshops. The following tables are used: $$Workshop(\...
0
votes
1answer
25 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
1answer
179 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)...
12
votes
1answer
687 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
1answer
560 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]...
5
votes
1answer
74 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
171 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
73 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, ...
1
vote
1answer
147 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 ...
-1
votes
2answers
964 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
808 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
231 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)$$
-2
votes
1answer
423 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 ...
1
vote
1answer
227 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 understanding ...
-1
votes
1answer
315 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 ?
0
votes
1answer
274 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 ...
0
votes
1answer
272 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 ...
3
votes
0answers
520 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 ...
1
vote
1answer
3k views

relational algebra to get unique pairs

Let's say we are given this table of the relation Person(name, hobby) ...
0
votes
0answers
36 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
130 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
994 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
165 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 ...
4
votes
2answers
558 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?
2
votes
1answer
43k 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
1answer
217 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
77 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
1answer
172 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
1answer
387 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 ...
3
votes
2answers
10k 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 ...
4
votes
1answer
514 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
4answers
4k 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
0answers
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
0answers
251 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 ...