Questions tagged [relation-algebra]

For questions about the algebra used for modeling the data stored in relational databases.

Filter by
Sorted by
Tagged with
2
votes
2answers
70 views

Is there a name for this sort-of-inverse function?

I'm looking for the mathematical name of a particular function which is available in several functional programming languages. If $f$ is a function $f:X\to Y$, then define $g : Y \to 2^X$ as follows. ...
0
votes
0answers
15 views

Disapprove equivalence between relational algebra statements

Consider the "semi-difference" relational algebra operator, defined as $$\begin{eqnarray*} R\triangleleft S & = & \{r\in R\mid \not\exists s\in S(r\bowtie s\in R\bowtie S)\}\\ &=&R-(R\...
0
votes
0answers
9 views

Attribute set closures

Consider the following relationship with its attributes: $$R( V, W, X, Y, Z )$$ This relationship has the following functional dependencies: $$FD: \{ XY \rightarrow W; V \rightarrow Y; Z \rightarrow ...
1
vote
2answers
50 views

Why are homomorphisms of graphs/relations defined the way they are?

Dealing with relations and functions in a set theoretic context i.e. as just sets of ordered pairs, note for any relations $R$ and $L$ that for any given function $f$ we have: $$\forall x,y\in \text{...
0
votes
0answers
129 views

Stanford Online Course Relational Algebra - Set Difference Operator

Problem: Consider a relation R(A) with r tuples, all unique within R, and a relation S(A) with s tuples, all unique within S. Let t represent the number of tuples in R minus S. Which of the following ...
0
votes
0answers
15 views

Domain relational calculus

There are 2 relations: Prediction(cname, etype) Measures(etype, provider) cname - city name of predicted future disaster. etype - event type. earthquake, tsunami... provider - police, ambulance......
0
votes
0answers
26 views

Find Projection of the n-ary relation when specified fields are deleted

I know that projection is used to extract information based on certain attributes or say columns. But what if those columns or fields are deleted, what does the projection operator return? I am ...
0
votes
1answer
32 views

How to find exactly $2$ events that from events list that meet certain criteria in tuple relational calculus?

Given the follow ing table definition: event(event-id, course-id, sem-id, day, duration, reg) which represents recurring events in some university (sem_id is semester id, reg is registered ...
0
votes
1answer
25 views

Such thing as inverse/undo “search” or “filter” operator

For common operators like $+$ the inverse is $-$, and $\times$ it is $\div$. Wondering if a "search" or "filter" on a set can have an inverse. $$B = \{a \in \mathbb{Z} \mid a < 10 \land a > 5\}$...
0
votes
0answers
31 views

Is it legal to use the cardinality of a universal quantifier in relational calculus?

For example, if I wanted to make a set of all $x$'s that satisfied some predicate function $f(x, y)$ with exactly 2 different values of $y$, is this a legal statement: $\{x |\ |(\forall y)(f(x, y))|=...
0
votes
0answers
132 views

Relational Algebra Operator Tree

Context: All customer pairs (C1,C2) such that C1 likes some pizza that C2 does not like. LikeDislike(cname, cname2): Question: Find all customer pairs (C1,C2) such that C1 < C2 and they like ...
1
vote
0answers
31 views

Equivalence between Basic Relational Algebra

The following relation schema: R(A,C), S(A,D), T(X,Y). Primary key attributes bolded Would like to know why the following two are not equivalent queries $Q_1 = π_A (σ_{C<10}(R))$ and $Q_2 = σ_{C&...
0
votes
1answer
176 views

Relational Algebra, find every author who co-authored with every other?

So in a DB course I am taking there is a practice problem, which states "Which authors co-authored at least 1 paper with every other author (without using aggregate functions)?" The relations given ...
0
votes
1answer
70 views

Equivalence Rules Proofs

I've been reading about the relational algebra equivalence rules as we see them Here or Here and also I have been looking for proofs of those rules everywhere. I see there are some ways such as truth ...
1
vote
0answers
43 views

Must relational algebra use tuples?

Please excuse me if I make glaring mistakes below – I'm a software engineer rather than a mathematician or logician, but I'm trying! My understanding of relational algebra is that relation headings ...
0
votes
0answers
705 views

What is the cartesian product of two relations with a common attribute

What I know about the Cartesian Product I just learned about the cartesian product in my introduction to Databases. The example that was provided was pretty clear. For a relation A with n tuples and ...
0
votes
1answer
29 views

Find transitive sub-relations of a non-transitive relation

Given a relation $R$ that is not transitive, I want to find subsets of $R$ that are actually transitive. What is the name of this operation and how this can be done?
-1
votes
2answers
205 views

covering relation question. [closed]

How can i show that "a partial order on a finite set is uniquely determined by its covering relation"?
1
vote
1answer
514 views

Associativity of natural join

A 'relation' is an object with a body that's a set of tuples, and a header that's a set of attribute identifiers. This sort of object is used in the theory of 'relational databases'. A relation is ...
0
votes
2answers
56 views

Proving that $R$ is a partial order on $X$

If I consider the relation $R$ on the set $X={3,5,30,45}$ and I define it by this statement: $\forall$ $m,n \in X$, $m$ $R$ $n$ if and only if there exists an integer $K$ such that $m=kn$. How could ...
0
votes
1answer
231 views

Why are quantifiers needed in Tuple Relational Calculus?

Why are quantifiers needed in Tuple Relational Calculus? Lets say I have this statement: {S.sname | S in Student and (exists G in Grade )(S.s# = G.s#)}; Why can't I just use this instead? {S....
0
votes
2answers
2k views

How to find the maximum in relational algebra?

This is my database course's homework. We have this relation. Trained(A, B) A trained B How can I figure out who has trained the most people by using relational algebra or it cannot be expressed in ...
0
votes
1answer
67 views

Relational algebra and union

Consider a database consisting of the relations, where the primary key of each relation is bolded. sailors (sid, sname, rating, age) boats (bid, bname, color) reserved (sid, bid, date) Find all ...
0
votes
1answer
77 views

Exclude the tuples of no interest in relational calculus

What is the meaning of the following expression (∀x)(¬P(x) OR ¬(x.Dnum=5)) As far as I know, it means for all x, P(x) is false, but in the book where I read this, it states that all tuples ...
1
vote
1answer
125 views

Prove the Relational Calculus logic equivalence

I encountered this in database subject which I am not able to understand even after lot of efforts. In relational calculus what do you mean by ¬(∀x)(¬P(x)) ? As ...
1
vote
2answers
43 views

A partition-generating algorithm

I come across this problem in designing a database, but it would seem to have basic application to networks: Given a set $J=\{j_1,j_2,\dots,j_k\}$, and a function $\mathscr M$ that maps each element ...
1
vote
1answer
80 views

Why study graph representations of equivalence relations?

What is the importance of representing a (an equivalence) relation using digraphs? Is there any geometric aspect to study relations using graphs (of vertices and edges)?
1
vote
3answers
710 views

$(\text{even}/\text{even})\times \text{even} = \text{odd}$? [closed]

Do even natural numbers $e_1,e_2,e_3$ exist with $\frac{e_1}{e_2}\cdot e_3=o$, such that $o$ is an odd natural number? If exist do they have any relation for this even tuple$(e_1,e_2,e_3)$?
1
vote
0answers
56 views

I am confused about this notation for matrix representation.

I am confused about this notation from the image below. How can you represent something like (1,2),1 as a 2D matrix? For S1 = (0,1,2) and S2 = (0,1) I would expect two matrices like: [(1,0),(1,0),(...
0
votes
1answer
54 views

Can a tuple be defined as an instance of a relationship?

SO let's say x and y are in relation. Is (x,y) a tuple and an instance of a relation ? Is a n-tuple an instance of a n-relation?
0
votes
1answer
49 views

Relational Aglebra, dont know what to do!

The following relational tables/schemes are given: In bold is the primary key, in Italics is foreign key: -City(Name,Country,Population) -Venue(VID,Capacity,Name) -Concert(KID,ID,DID,duration) -...
0
votes
0answers
136 views

E1 and E2 are equivalent then they are “almost equivalent”

Given : 2 statements E1, E2 in relational algebra are "almost equivalent" if every phase in the database D ,except finite number of D's E1(D)=E2(D). E(D) means the result of activating the statement E ...
1
vote
3answers
2k views

Proving equivalence relation for 7 | (3a + 4b)

I know this might be quite trivial, but I just can't seem to figure out how to prove $$R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} : 3a + 4b \text{ is divisible by } 7\}$$ is a symmetric relation, i....
1
vote
1answer
375 views

Converting between relational calculus and relational algebra

So I'm trying to get my head around relational algebra and calculus and converting between them. I understand that... $$\{ x\mid\exists y.F(x,y) \wedge G(x,y)\}$$ ...equates to $\pi_A F \cap G$ But ...
1
vote
0answers
9 views

Relational Database Reductions

So In the study guide for our Db Design final, the professor gave us this Information preserving logical design, Where bold is a primary key and italics are a foreign key. L1: Donor: D_ID, D_Name, [0,...
2
votes
0answers
2k views

Relational Algebra: Finding duplicates in a specific attribute of a relation

I have a relation $PC$, defined as: $$\textbf{PC} = \matrix{model & speed & ram & hd & price \cr 1001 & 2.66 & 1024 & 250 & 2114 \cr ...
1
vote
1answer
37 views

Finding a relation between several variables

I'm a bit at a loss here. I know that this seems a bit like a "here's my problem, now go solve it" thing, and I'm sorry about that, but I just want a nudge in the right direction since I've never ...
1
vote
1answer
2k views

Is my answer for the composite relation correct and not the textbook's?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 5 pg 593] Here is how my textbook's way of representing a relation with a matrix And the definition of a ...
2
votes
1answer
65 views

What do these sets mean? Relational Algebra

I'm in a databases class and this homework is due next week. I have been home sick for a couple days so I can't go to class to ask this question right now and I'd hate to waste time, so hopefully ...
1
vote
1answer
130 views

A counterexample for an equation between arbitrary relations

It seems that the following equation does not hold always for the arbitrary relations R1,R1 and R3: $R1.(R2\cap R3)=(R1.R2)\cap(R1.R3)$ Instead, the right axiom is the following: $R1.(R2\cap R3)...
1
vote
1answer
280 views

xor of three relations using Relation Algebra operations

Suppose I have three relations R1, R2, and R3. How can I specify xor of these three relations using relation algebra operations. How this scales up (for example, for four relations)? Thanks I add ...
1
vote
1answer
42 views

For a special group G described below, the order of G can only be $p_1p_2…p_k$ where $p_i$ s are prime.

I am just learning generators and relations basics. A clarification Let $G$ be a finite group in which every element(non-zero) is a possible candidate to be in the minimal generating set $S$ of the ...
1
vote
1answer
182 views

fastest and most efficent way to count all combinations in many sets and sum them together

I am a Java programmer who has reached the limits of brute computer power. My relational database (and non relational databases) is not producing results quick enough and I have hit a bottleneck in ...
0
votes
1answer
264 views

Relational Algebra : Cross Product of a Relation with Table-Dum & Table-Dee

I am wondering what would be the result of the following operation: Let $A$ be a relation with $n$ ($n > 0$) attributes and $t$ ($t > 0$) tuples. Let $TableDum$ be a relation with $0$ ...
1
vote
1answer
28 views

Functional dependency - adding any attribute to X will still yield a FD?

I have heard my professor saying that when X → Y is a functional dependency, adding any attribute to X or removing any attribute from Y will still yield a functional dependency. I do not understand ...
1
vote
1answer
77 views

Difference between $A\to B\to C$ and $A\to(B\to C)$

As the title says, what is the difference between $A\to B\to C$ and $A\to(B\to C)$? I have tried to reduce these expressions into $A\to B === (A\text{ OR } \text{NOT} B)$ form but didn't get anywhere. ...
2
votes
1answer
82 views

Help solving a challenge - relational algebra or second order logic

I am a self-taught man and I'm posting my first question here. I'm facing a challenge I'd like to solve. Based on what I know it fits propositional calculus (hope it is). Suppose 3 people: a ...
0
votes
3answers
89 views

How did I solve this problem?

While writing a SQL query I had to solve a problem I'd never dealt with before. It was trivial, but I cannot explain the solution without drawing lines on paper or making examples with actual numbers -...
0
votes
1answer
1k views

Proof - Projection distribution over set union

I've just started databases and have exercise to proof that projection$(\pi)$ is distributive over set union$(\bigcup)$. But I suck in proofs and don't really know how to proof that: $\pi_\alpha( R \...
1
vote
1answer
217 views

Relational Algebra: Showing equality using aggregate operator

The schemas are given here for relations $R$ and $S$: $$R(A,B)$$ $$S(C,D,E)$$ One can see that the following equality is true: $$\gamma_{B,sum(E)}(R\Join_{A=C}S) = \gamma_{B,sum(E)}(R\Join_{A=C} ({\...