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
29
votes
3answers
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 ...
19
votes
2answers
903 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 ...
12
votes
1answer
708 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 ...
7
votes
1answer
650 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 ...
6
votes
2answers
122 views

Optimizing a join where each table has a selection

Consider the following query: ...
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) ...
5
votes
1answer
76 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_{\...
4
votes
2answers
581 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?
4
votes
1answer
532 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)\...
4
votes
1answer
195 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
1answer
1k 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 ...
4
votes
1answer
724 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 ...
4
votes
2answers
9k 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 ...
4
votes
1answer
125 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 ...
3
votes
3answers
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 ...
3
votes
1answer
394 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
1answer
267 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 ...
3
votes
0answers
565 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
votes
1answer
45k 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 ...
2
votes
2answers
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 ...
2
votes
2answers
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}(\...
2
votes
1answer
546 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)]$. ...
2
votes
1answer
36 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
1answer
12 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 ...
2
votes
1answer
80 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" ...
2
votes
1answer
119 views

Relational algebra statement for a query

For the following schema ...
2
votes
0answers
18 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 ...
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
0answers
208 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: ...
1
vote
1answer
910 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
vote
1answer
230 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
vote
1answer
53 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$ ...
1
vote
1answer
46 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
1answer
68 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 ...
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) ...
1
vote
1answer
148 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
vote
1answer
128 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
1answer
40 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 ...
1
vote
0answers
23 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://...
1
vote
0answers
16 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 ...
1
vote
0answers
25 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
61 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
2answers
316 views
1
vote
1answer
65 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,...
1
vote
0answers
119 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(\...
1
vote
0answers
254 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
0answers
161 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 ...
1
vote
0answers
115 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 ...
1
vote
0answers
25 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 ...
0
votes
1answer
344 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 ...