Ch 4. Relations
Ch 4. Solutions
1. a) [latex]\{ 1, 2, 3, 4, 5 \}[/latex], b) [latex]\{ 3 \}[/latex], c) [latex]\{ 1, 2 \}[/latex]
3. [latex]\{ a, b \} , \{ a, c \} , \{ a, b, c \} , \{ b, c \} , \{ b, d \} , \{ b, c, d \} , \{ c, d \} , \{ b, c, d \}[/latex]
5. [latex]\{ 1, 3, 5 \}[/latex]
9. No
15. [latex]\{ 3, 4 \}[/latex]
17. [latex]1 \rightarrow 2 \rightarrow 3 \rightarrow 1[/latex]; not strongly connected
19.
a) [latex]\begin{array}{c|cccc} & a & b & c & d \\ \hline a & 0 & 1 & 0 & 1 \\ b & 0 & 0 & 1 & 0 \\ c & 0 & 0 & 0 & 1 \\ d & 0 & 0 & 0 & 0 \end{array}[/latex]
c) Not transitive
21.
a) [latex]\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 1 & 0 & 1 \\ B & 0 & 0 & 1 & 0 \\ C & 1 & 0 & 0 & 0 \\ D & 0 & 0 & 0 & 0 \end{array}[/latex]
b) Not strongly connected
c) [latex]\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 1 & 1 & 1 & 1 \\ B & 1 & 1 & 1 & 1 \\ C & 1 & 1 & 1 & 1 \\ D & 0 & 0 & 0 & 0 \end{array}[/latex]
23
a) [latex]\{ (2, 1), (3, 2), (4, 3), (1, 4) \}[/latex]
c) [latex]R = \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & 0 & 1 & 0 & 0 \\ 2 & 0 & 0 & 1 & 0 \\ 3 & 0 & 0 & 0 & 1 \\ 4 & 1 & 0 & 1 & 0 \end{array}[/latex]
[latex]R^{-1} = \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & 0 & 0 & 0 & 1 \\ 2 & 1 & 0 & 0 & 0 \\ 3 & 0 & 1 & 0 & 0 \\ 4 & 0 & 0 & 1 & 0 \end{array}[/latex]
a) {{Read, Write, Delete}, {Read, Write}, {Read}}
b)
| User | Permissions |
|---|---|
| Aiden | Read, Write, Delete |
| Benjamin | Read, Write |
| Chloe | Read |
31.
a) [latex]\{ (1, x), (1, \{ y \} ), ( \{ 2 \} , x), ( \{ 2 \} , \{ y \} ) \}[/latex]; [latex]\{ (x, 1), (x, \{ 2 \} ), ( \{ y \} , 1), ( \{ y \} , \{ 2 \} ) \}[/latex]
b) No
33.
a) 8, b) 4, c) 0
35.
a) [latex]\emptyset[/latex], b) [latex]\emptyset[/latex]
39.
a) (ID, Name, Major, GPA, Status)
45.
b) 5000, c) 1000
47.
b) [latex]a \rightarrow b \rightarrow c \rightarrow a[/latex]
c) Yes
49.
a) [latex]\{ 1, 2, 3, 4, 5, 6 \}[/latex]
b) No
c) [latex](4, 4), (5, 5), (6, 6)[/latex]
51.
a) {Aiden, Benjamin, Chloe}; {Aiden, Benjamin, Chloe}; {Aiden, Benjamin, Chloe}
b) Not reflexive, not symmetric, not transitive
c) Add (Aiden, Chloe), (Benjamin, Aiden), (Chloe, Benjamin), (Aiden, Aiden), (Benjamin, Benjamin), (Chloe, Chloe)
55.
b) [latex]\{ (x, y), (y, x) \}[/latex]
c) [latex]\{ (x, x), (y, y), (z, z), (x, y) \}[/latex]
59. [latex]\{ (1, 2), (2, 3), (3, 4), (4, 1), (1, 3), (2, 4), (1, 4) \}[/latex]
63. No
c) [latex][0, \infty)[/latex] or [latex](- \infty, 0][/latex]
65.
a) No; not symmetric nor transitive; add [latex](3,2), (1,3), (3,1)[/latex]
67. Reflexive, not symmetric, not transitive
b) Add [latex](a, c), (c, b), (c, a)[/latex]
69.
a) Not reflexive, symmetric, not transitive
c) Yes
71. {Aiden, Benjamin, Chloe, Daniel}, {Eve}
77.
b) [latex][1] = \{ 1, 3 \} , [2] = \{ 2, 4 \} , [5] = \{ 5\}[/latex]
79. [latex]\{ \dots, –4, –2, 0, 2, 4, \dots \}, \{ \dots, –3, –1, 1, 3, 5, \dots \}[/latex]
81.
a) No
b) [latex]\{ \{ 1, 2 \} , \{ 3, 4, 5 \} , \{ 6, 7 \} \}[/latex]
c) [latex]\{ (1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (3, 5), (4, 3), (4, 4),(4, 5), (5, 3), (5, 4), (5, 5), (6, 6), (6, 7), (7, 6), (7, 7) \}[/latex]
83.
a) [latex]\{ (1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5), (2, 2), (2, 4), (2, 6), (4, 2), (4, 4), (4, 6), (6, 2), (6, 4), (6, 6) \}[/latex]
c) [latex]\begin{array}{c|cccccc} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 2 & 0 & 1 & 0 & 1 & 0 & 1 \\ 3 & 1 & 0 & 1 & 0 & 1 & 0 \\ 4 & 0 & 1 & 0 & 1 & 0 & 1 \\ 5 & 1 & 0 & 1 & 0 & 1 & 0 \\ 6 & 0 & 1 & 0 & 1 & 0 & 1 \end{array}[/latex]
85. [latex]\{ (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5) \}[/latex]
b) 6
d) [latex]\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 \\ 2 & 0 & 0 & 1 & 1 & 1 \\ 3 & 0 & 0 & 0 & 1 & 1 \\ 4 & 0 & 0 & 0 & 0 & 1 \\ 5 & 0 & 0 & 0 & 0 & 0 \end{array}[/latex]
91.
93
95.
97. R1 = Students join [Students.ID=Grades.ID] Grades
project [Name, Grade] (R1)
103. R1 = Students join [Students.ID=Grades.ID] Grades
R2 = select Course = ‘Math’ (R1)
project [Name, Grade] (R2)
