The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
23 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 ...
0
votes
0answers
11 views

confused on BCNF for given functional dependencies

if I have three non-trivial functional dependencies: a -> b c -> b ac -> b Is it in boyce-codd normal form (BCNF) ?
0
votes
0answers
34 views

What does the Dedekind Rule `say'?

In Relation Algebra, the modal law or dedekind rule $$R;S \,\cap\, T \;\subseteq\; (R \cap T;S^\circ);S$$ appears often and I wonder what is the motivation behind it. Moreoever, what does it "say". I ...
1
vote
0answers
49 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
33 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
32 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 ...
1
vote
0answers
43 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
37 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
0answers
40 views

Does R(5,7) hold or not in this relation?

This is the question: Let $A=\{1,...,7\}$ and let $R\subseteq A\times A$ be a relation which is symmetric and transitive. You have been given some partial information about the relation which is ...
1
vote
1answer
73 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
0answers
13 views

Optimization of a set-based invariant for a single element case

As I understand it, various algebras have useful identities. For example, in boolean algebra, !a & !b is equivalent to ...
0
votes
1answer
52 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$ ...
2
votes
1answer
22 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
67 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
53 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
68 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
118 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
77 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} ...
0
votes
0answers
98 views

Need review of Relational Algebra

These are technically homework but I'd like to have verified whether what I did is right or wrong, so I don't upright ask for a solution at least. • Find the names, street address, and cities of ...
1
vote
1answer
110 views

Forward and backward composition in relational algebra

Forward composition: $p\,;q$ $$\forall p,q\cdot p\in S\leftrightarrow T\land q\in T\leftrightarrow U\implies\\p\,;q=\{x\mapsto y\mid(\exists z\cdot x\mapsto z\in p\land z\mapsto y\in q)\}$$ ...
0
votes
1answer
30 views

Equivalence between relational algebra statements

This is a practice question for a relational algebra question which I don't understand. Consider two relations $R(A, B)$ and $S(B,C)$. Which of the following relational algebra expressions is not ...
0
votes
1answer
121 views

Relational Algebras and Relational Calculus

Suppose we have a statement $S$ such as "The number of people connected to Bob through any number of friends." Why is this statement expressible in relational algebra but not in relational calculus? ...
2
votes
0answers
101 views

How to denote the set of binary relations of which a particular ordered pair is a member?

Given a universe $U$ and two subsets $S$ and $T$ (also, both members of $U$), what is the name given to denote the set of all binary relations in $U$ where the ordered pair $(S,T)$ is a member? The ...
0
votes
2answers
86 views

“Het” ternary and n-ary relations in $\bf Rel$?

Are n-ary relations, with n > 2, in $\bf Rel$ - the category of sets as objects and relations as arrows? By "het" (heterogeneous) relations I mean relations between distinct sets, so $X \to Y$, as ...
1
vote
1answer
143 views

Relations as arrows and as objects - what are the arrows in the latter?

Since a relation $R$ from $X$ to $Y$ defined as a subset of $X \times Y$, the category of sets and relations is just that: the objects are sets and the arrows are the relations. Is there a generally ...
-1
votes
1answer
69 views

In relational algebra, what would be the result of $(R-S)\cup (S-R)?$

Suppose relation $R(A,B,C)$ has the following tuples: $X\;\;\;\; Y\;\;\;Z$ $1\;\;\;\;\; 2\;\;\;\;\; 3$ $4\;\;\;\;\; 2\;\;\;\;\; 3$ $4\;\;\;\;\; 5\;\;\;\;\; 6$ $2\;\;\;\;\; 5\;\;\;\;\; 3$ ...
3
votes
2answers
648 views

Distinguishing equality and isomorphism as relations

Is this relational characterization of equality in Wikipedia accepted? The identity relation is the archetype of the more general concept of an equivalence relation on a set: those binary ...
1
vote
0answers
159 views

Example relations: pairwise versus mutual

There are by now several questions on math.se asking about pairwise versus mutual relations, eg: • When does “pairwise” strengthen and when does it weaken? • Relation: pairwise and mutually • ...
3
votes
2answers
150 views

Categories of $n$-ary relations?

Arrows in the category $\bf Rel$ are binary (2-valued) relations between set objects. Do ternary, 4-term, $n$-term and variadic (2-valued) relations form categories? (Or perhaps one category?). It ...
3
votes
1answer
54 views

Category of Pointed Relations

There are the categories $\mathbf{Set}$ and $\mathbf{pSet}$; given the category $\mathbf{Rel}$, can we define an analogous category $\mathbf{pRel}$ as well? A relation $R \subseteq A \times B$ is said ...
1
vote
0answers
71 views

wikipedia relation algebra example #3

Wikipedia article gives the following relation algebra example: 3 An important generalization of the previous example is the power set $2^E$ where E ⊆ X² is any equivalence relation on the set X. ...
4
votes
1answer
329 views

Motivation behind Theory of Relations?

I looked through the nice paper by Tarski On the Calculus of Relations. In the beginning he touched a motivation behind Theory of Relations but this part was not clear to me (page 1, very beginning): ...
0
votes
2answers
347 views

Functional dependencies A->B and C->B, but not AC->B?

If I have a relation: A B C 1 2 3 4 5 6 7 2 8 Where $A\mapsto B$ and $C \mapsto B$. Doesn't that mean that $AC \mapsto B$? How can you even have this relation? ...
2
votes
1answer
178 views

What does Tarski mean by a “tautological operation” on a Boolean algebra?

I am reading Part II of Chin and Tarski's "Distributive and Modular Laws in the Arithmetic of Relation Algebras". In the beginning of section 4, the authors say "In general, if $\odot$ is a binary ...
1
vote
1answer
211 views

What does it mean for a relation algebra to be simple?

I am reading "Boolean Algebras with Operators part II" by Bjarni Jonsson and Alfred Tarski. On theorem 4.10 (p.132-133), they refer to a relation algebra $\mathfrak{A}$ being "simple" and proves that ...
0
votes
2answers
3k views

Equivalence Relations and Inverse Relations

Prove that if $R$ is an equivalence relation on a set $A$, then $R^{-1}$ is also an equivalence relation on $A$. Solution: We know that $\forall R\in A$, $$ R = \{(a, b) | (b, a)\in A\} $$ ...
1
vote
1answer
785 views

Software for testing relational algebra

Does anyone know of any software to let you test relational algebra queries? By this I don't mean a database such as MySQL, something where the query can be input in some for of mathematical notation ...
3
votes
1answer
202 views

What is the “Boolean algebra fragment of RA”?

The Wikipedia article on Relation Algebra notes that this is a formal system which has essentially the same expressive power as the three-variable fragment of first-order logic. Peano Arithmetic can ...
3
votes
3answers
156 views

Where can I find good information, tutorials and or examples on relational algebra queries?

Taken a break from my personal project and getting some work done. I would like to find some examples, tutorials on relation algebra. Anything with good examples will be very useful