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.
86
questions
0
votes
0
answers
77
views
Can quantifiers be used on variables bound on the left side of the pipe in Tuple Relational Calculus?
Our professor has solved an example for us. They taught us it's incorrect to use a quantifier (exists or forall) with a variable ...
-1
votes
1
answer
35
views
0
votes
1
answer
63
views
Projection syntax - relational algebra
I'm trying to understand this paper and in Figure 1 page 389 there's a projection in the form of $\pi_{d.id : s.id}$. What does the colon mean? Because usually projections are simply $\pi_{name}(R)$
- 9
1
vote
0
answers
757
views
Is it possible to convert any relational algebra expression into a relational calculus expression?
Let's for the sake of simplicity only focus on tuple relational calculus.
Every relational algebra query can be broken down into the 5 atomic operations - projection, selection, set union, set ...
- 129
2
votes
1
answer
28
views
How to simplify the query qualification?
Given the following DB and query :
Now if we need to simplify the query qualification, here is the answer from the book (Principle of distributed database systems, third edition) :
My question is in ...
- 23
1
vote
0
answers
65
views
constant relation in the base case of relational algebra
in the base case of the inductive definition of the operations of the relational algebra there is also the so called "constant relation" (as for example found in the definition here https://...
- 155
1
vote
0
answers
38
views
Which of the query approaches are more efficient?
There are two relations, registered(participant,topic) and fee(participant,amount).
The primary key for registered is (participant, topic) and the primary key for fee is participant.
The premise is ...
2
votes
0
answers
27
views
Optional filters in relational database
I'm trying to create a procedure in MySQL/MariaDB with optional filters for each participating table. Assuming the tables are $A, B, C, \ldots$, each table may or may not be filtered, and the result ...
- 1,111
0
votes
0
answers
59
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 ...
- 33
1
vote
1
answer
170
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
...
- 113
1
vote
0
answers
32
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?
- 91
0
votes
0
answers
2k
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
1
vote
1
answer
197
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 ∪ (...
- 13
1
vote
2
answers
3k
views
how to get rows with more than 1 appearance of a specific column in relational algebra
I have a table like this:
...
- 13
0
votes
0
answers
97
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 ...
- 51
1
vote
1
answer
228
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,...
- 11
-1
votes
1
answer
53
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....
1
vote
1
answer
141
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 ...
- 125
-2
votes
1
answer
26
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
1
answer
1k
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 ...
- 4,825
1
vote
0
answers
273
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(\...
- 11
0
votes
1
answer
30
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 ...
- 165
0
votes
1
answer
1k
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]...
- 177
0
votes
1
answer
311
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)...
- 273
-1
votes
1
answer
387
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 ...
- 1
5
votes
1
answer
127
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_{\...
- 171
0
votes
1
answer
233
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,\...
- 67
0
votes
1
answer
101
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 ...
- 321
0
votes
1
answer
103
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, ...
- 321
-1
votes
2
answers
2k
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 ...
- 3
1
vote
1
answer
1k
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 ...
- 1,644
0
votes
1
answer
550
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 ...
- 1,637
0
votes
1
answer
469
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 ...
- 133
-2
votes
1
answer
765
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
0
answers
960
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 ...
- 2,163
0
votes
1
answer
237
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
-1
votes
1
answer
475
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 ?
- 21
1
vote
1
answer
4k
views
relational algebra to get unique pairs
Let's say we are given this table of the relation Person(name, hobby)
...
- 139
0
votes
0
answers
38
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 ...
- 101
2
votes
0
answers
138
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) ...
- 413
2
votes
2
answers
1k
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}(\...
- 65
0
votes
0
answers
240
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
1
answer
251
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 ...
- 161
4
votes
2
answers
720
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?
- 203
1
vote
1
answer
158
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 ...
- 815
0
votes
1
answer
288
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
128
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
1
answer
611
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)\...
3
votes
1
answer
419
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 ...
- 388
0
votes
1
answer
203
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 \...
- 113