### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# ICS 6b week 7 notes ICS 6B

UCI

GPA 3.9

### View Full Document

## 9

## 0

## Popular in BOOLEAN ALGEBRA

## Popular in Department

This 81 page Class Notes was uploaded by Apurva on Monday May 16, 2016. The Class Notes belongs to ICS 6B at University of California - Irvine taught by DILLENCOURT in Spring 2016. Since its upload, it has received 9 views.

## Similar to ICS 6B at UCI

## Popular in Subject

## Reviews for ICS 6b week 7 notes

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 05/16/16

RELA TIONS Chapter 6 Binary Relations •Let A and B be sets. Abinary relation from A to B is a subset of A x B •In other words a binary relation from A to B is a set R of ordered pairs where the first element of each ordered pair comes from A and the second element comes from B •If (a,b) ∈ R, we say that a R b. Representing relations Since relations are sets, we can represent them the same way we represent sets: •Roster method: R = {(1,4),(2,5),(3,6)} •Roster method with ellipses: S = {(1,4),(2,5),...,(97,100)} •Set Builder notation: S = {(x,y)| x ∈ {1,2,...,97}, y=x+3} More ways to represent relations We can represent a relation from A to B using an arrow diagram. • A is on the left • B is on the right • Each element of the relation is represented by an arrow Example: • A = {a 1 a2, a3} • B = {b 2 b 2 b3, b4, 5 } • R = {(a ,b ), (a ,b ), (a ,b ), (a ,b ), 1 2 2 1 2 3 2 4 (a3,b1), (a3,b3), (3 ,5 )} More ways to represent relations We can represent a relation from A to B using a matrix. • Rows represent the elements of the first set (A) • Columns represent the elements of the second set (B) • There is a 1 in the entry in the row for a and the column for b if a R b. Otherwise there is a 0. Example: • A = {a , a , a } 1 2 3 • B = {b 2 b 2 b3, b4, 5 } • R = {(a 1b 2, (a 2b 1, (a 2b 3, (a 2b 4, (a3,b1), (a3,b3), (3 ,5 )} More ways to represent relations In the special case of a relation between a set and itself, we can represent a relation from A to A using an arrow diagram with only one copy of A. Such an arrow diagram is also known as a directed graph or a digraph. Example: • A = {a,b,c,d} • R = {(a,b),(a,d),(b,b),(b,d),(c,a),(c,b),(d,b)} A relation between a set A and itself is called a relation on A. Properties of relations A relation R on a set A is called: • Reflexive if (a,a) ∈ A for all a ∈ R • Symmetric if (b,a) ∈ R whenever (a,b) ∈ R • Transitive if (a,c) ∈ R whenever (a,b) ∈ R and (b,c) ∈ R • Anti-reflexive if (a,a) ∉ A for all a ∈ R • Anti-symmetric if (b,a) ∈ R and (a,b) ∈ R imply that a=b To see why these are important properties, think about: = ≠ < ≤ (addressed in subsequent slides) There are examples in the text. Understand them! Properties of relations We can rewrite the definitions of these properties using predicate logic, where the domain of discourse is the set A. • Reflexive: ∀a (a,a) ∈ R • Symmetric: ∀a∀b (a,b) ∈ R → (b,a) ∈ R • Transitive: ∀a ∀b ∀c ((a,b) ∈ R ∧ (b,c) ∈ R) → (a,c) ∈ R • Anti-reflexive: ∀a (a,a) ∉ R • Anti-symmetric: ∀a ∀b ((a,b) ∈ R ∧ (b,a) ∈ R) → a=b Suggested exercise: Write the negations of these definitions using predicate calculus, without using the ¬ operator. For example, the negation of “R is reflexive” is: ∃ a (a,a) ∉ R Properties of relations The relations =, ≠, <, ≤ have the following combinations of properties: • = : reflexive, symmetric, transitive. Also anti -symmetric • ≠ : anti-reflexive, symmetric • < : anti-reflexive, anti-symmetric, transitive • ≤ : reflexive, anti-symmetric, transitive Properties of relations • ≤ : reflexive, not anti-reflexive, not symmetric, anti-symmetric, transitive. • Reflexive because for all a, a ≤ a • Not anti-reflexive because 2 ≤ 2 • Not symmetric: 2 ≤ 3 but it is not true that 3 ≤ 2 • Anti symmetric: for all a and b, if a ≤ b and if b ≤ a then a=b • Transitive: for all a, b, and c, if a ≤ b and if b ≤ c then a ≤ c Properties of relations • < : not reflexive, anti-reflexive, not symmetric, anti- symmetric, transitive. • Not reflexive because it is not true that 2 < 2 • Anti-reflexive because for all a it is not true that a < a . (Another way of saying this is that for alla, a ≥ a .) • Not symmetric: 2 < 3 but it is not true that 3 < 2 • Anti symmetric: for all a and b, if a < b and if b < a then a=b. (This is true vacuously : the hypothesis of the implication is always false.) • Transitive: for all a, b, and c, if a < b and if b < c then a < c Directed Graphs Read the text for definitions(Section 5.2). Here are some examples and illustrations of the definitions in the book with respect to the example directed graph. • Vertices: {a,b,c,d} • Edges: {(a,b),(a,d),(b,b),(b,d),(c,a),(c,b),(d,b)} • For edge (a,b): a is the tail and b is the head • The edge (b,b) is a self-loop • The in-degree of a is 1. The out-degree of a is 2. Directed Graphs More examples and illustrations of the definitions in the book with respect to the example directed graph. Note: these definitions vary from book to book. When you read a book about graphs, always review the definitions first. • <a,b,d,b > is a walk of length 3. <a,c,b,d,b> is not a walk. • <b,d,b,d,b> is a circuit of length 4. <c> is a circuit of length 0. <c,a,b,c> is not a circuit. Neither is <b,d,b,d> • <c,a,b,d> is a path of length 3. <a,b,d,b> is not a path. • <b,d,b> is a cycle of length 2. <a> is a cycle of length 0. <b,d,b,d,b> is not a cycle Composition of relations • If R and S are relations, their composition is: S ∘ R = { (a, c) :there is some b ∈ A, such that (a,b) ∈ R and (b,c) ∈ S • Note that the order of R and S may seem odd. It is consistent with the notation for function composition: 1. First apply R to find all elements b, 2. Then apply S to find all elements c. • Example: For R = {(1,1),(1,2),(2,1),(3,2)} S = {(1,3),(2,3),(3,1)} what is S ∘ R ? • Solution: S ∘ R = {(1,3),(2,3),(3,3)} Composition of relations Given the arrow diagrams of two relations, we can draw the arrow diagram for their composition: Example: For R = {(1,1),(1,2),(2,1),(3,2)} and S = {(1,3),(2,3),(3,1)} Arrow diagram for R Arrow diagram for S Arrow diagram for S ∘ R Intermediate step: Compose the two arrow diagrams., This is not yet an arrow diagram for S ∘ R Closures of Relations • Let R be a relation on a set A. R may or may not have some property P, such as reflexivity, symmetry or transitivity. • The closure of R with respect to P is the relation with property P that we can obtain by adding as few new pairs to A as possible. • Note that this could be A itself if A has property P. • In the important cases where property P is reflexivity, symmetry or transitivity, we talk about the reflexive closure, the symmetric closure, the transitive closure. Reflexive Closures of Relations Example: The relation R = {(1,1),(1,2),(2,1),(3,2)} on the set A={1,2,3} is not reflexive. How can we produce a smallest reflexive relation containing R? Solution:Add (2,2) and (3,3). Then we have the reflexive closure of R. Definition: For a given relation R on a set A, the reflexive closure of R is R ∪ {(a,a) | a ∈ A} Symmetric Closures of Relations Example: The relation R = {(1,1),(1,2),(2,1),(3,2)} on the set A={1,2,3} is not symmetric. How can we produce a smallest reflexive relation containing R? Solution:Add (2,3). Then we have the symmetric closure of R. Definition: For a given relation R on a set A, the symmetric closure of R is R ∪ {(x,y) | (y,x) ∈ R} Inverse of a Relation The inverse of a relation R is R = {(x,y) | (y,x) ∈ R}. Example: For R = {(1,1),(1,2),(2,1),(3,2)} , -1 R = {(1,1),(1,2),(2,1),(2,3)} . General rule for symmetric closure, restated: For a given relation R on a set A, the symmetric closure of R is -1 R ∪ R Reflexive and Symmetric Closures For a relation represented as a directed graph: • To form the reflexive closure: • Add a loop at each vertex if one is not already there • To form the symmetric closure: • For each edge, add the edge going in the opposite direction if it is not already there. Composition of relations • If R and S are relations, their composition is: S ∘ R = { (a, c) :there is some b ∈ A, such that (a,b) ∈ R and (b,c) ∈ S • Note that the order of R and S may seem odd. It is consistent with the notation for function composition: 1. First apply R to find all elements b, 2. Then apply S to find all elements c. • Example: For R = {(1,1),(1,2),(2,1),(3,2)} S = {(1,3),(2,3),(3,1)} what is S ∘ R ? • Solution: S ∘ R = {(1,3),(2,3),(3,3)} Composition of relations Given the arrow diagrams of two relations, we can draw the arrow diagram for their composition: Example: For R = {(1,1),(1,2),(2,1),(3,2)} and S = {(1,3),(2,3),(3,1)} Arrow diagram for R Arrow diagram for S Arrow diagram for S ∘ R Intermediate step: Compose the two arrow diagrams., This is not yet an arrow diagram for S ∘ R Transitive Closure If R is a relation on a set A (i.e., if R ⊆ A × A) we can compose R with itself. This means we can define powers of R, analogous to powers of multiplication in standard arithmetic: 1 • R = R • R = R ∘ R • R = R ∘ R = R ∘ R ∘ R 4 3 • R = R ∘ R = R ∘ R ∘ R ∘ R • ... To form the transitive closure of a relation R: + 1 2 3 • R = R ∪ R ∪ R ∪ ... Transitive Closure Example: Let R be the relation defined by a R b if a is a parent of b • R = R: parent • R = R ∘ R: grandparent • R = R ∘ R = R ∘ R ∘ R: great-grandparent 4 3 • R = R ∘ R = R ∘ R ∘ R ∘ R: great-great-grandparent • ... • R = R ∪ R ∪ R ∪ ... : ancestor Transitive Closure Example: R = {(a,b),(a,d),(b,b),(b,d),(c,a),(c,b),(d,b)} 1 • R = R = {(a,b),(a,d),(b,b),(b,d),(c,a),(c,b),(d,b)} • R = R ∘ R = {(a,b),(a,d),(b,b),(b,d),(c,b),(c,d),(d,b),(d,d)} • R = R ∘ R = {(a,b),(a,d),(b,b),(b,d),(c,b),(c,d),(d,b),(d,d)} = R 2 • Powers remain the same from this point on. • Transitive closure: + R = {(a,b),(a,d),(b,b),(b,d),(c,a),(c,b),(c,d),(d,b),(d,d)} k ( x,y) ∈R if there is a walk of length k from x to y in the diagraph for R. (x,y) ∈ R +if there is a walk of any positive length from x to y. R = R: R : R : Transitive Closure: Algorithmic note To find the transitive closure of a relation on a finite set, three possible approaches: 1. Compute R , R , R , ... until some R is equal to R k-1 and 1 2 3 k then take the union of R , R , R , ... R . • This may be done using Boolean matrix multiplication (see next few slides) 2. Repeat the following step until it cannot be repeated: • Find three elements a,b,c with (a,b)∈ R, (b,c)∈ R, (a,c) ∉ R and add the pair (a,c) to R 3. Use Warshall’s algorithm (not covered here). Transitive Closure: One more example Example: Let R be the relation on the integers defined by (a,b) ∈ R if a = b + 1 What is the transitive closure of R? 1 1 • R : (a,b) ∈ R if a = b + 1 • R : (a,b) ∈ R if a = b + 2 • R : (a,b) ∈ R if a = b + 3 4 4 • R : (a,b) ∈ R if a = b + 4 • ... So what is R ?+ + • (a,b) ∈ R if a > b Matrices • An n × m matrix over a set S is an array of elements from S with n rows and m columns. • Each element in a matrix is called an entry. • The entry in row i and column j is denoted by A . i,j • A matrix is called a square matrix if the number of rows is equal to the number of columns. • Examples: Adjacency Matrices and Directed Graphs Let G be a directed graph with n vertices. The adjacency matrix for G is an n × n matrix A such that: • A = 1 if there is an edge from vertex i to vertex j in G i,j • A i,j if there is not an edge from vertex i to vertex j in G Example: An adjacency matrix is a special type of matrix called a Boolean matrix ... Boolean Matrices • A Boolean matrix is a matrix such that every entry is either 0 are 1. • 0 corresponds to False and 1 corresponds to True • Boolean matrices can be added and multiplied using Boolean addition and Boolean multiplication • Note that Boolean addition and multiplication are different from the standard addition and multiplication used to add and multiply real numbers! Boolean Matrix Addition • The sum of two matrices, A and B, is well defined only if A and B have the same dimension(same number of rows, same number of columns) • Each entry of the matrix A + B is computed by taking the Boolean sum (disjunction, same as inclusive or) of the corresponding entries from A and B • Example: Boolean Matrix Multiplication • The product of two matrices,A and B, is well defined only if the number of columns in A is equal to the number of rows in B • Each entry of the matrix A × B is computed by taking the Boolean dot product of a row of A and a column of B • To compute the Boolean dot product of a row in one matrix with a column in another: • The row and the column must be to be the same length (otherwise, the dot product is not well defined.) • Compute the Boolean product (the conjunction, or and) of each corresponding pair • Compute the Boolean sum (the disjunction, or inclusive or) of all the pairs • When computing the conjunction and the disjunction, 0 corresponds to False and 1 corresponds to True Example on next slide BooleanMatrix Multiplication Example • To compute (AB) , t1,1entry in the first row and first column of the Boolean product, take the Boolean dot product of the first row of A with the first column of B: (AB) = 1 · 1 + 1 · 0 + 0 · 0 = 1 + 0 + 0 = 1 1,1 • More entries: (AB) 1,2= 1 · 0 + 1 · 0 + 0 · 1 = 0 + 0 + 0 = 0 (AB) 1,3= 1 · 1 + 1 · 1 + 0 · 1 = 1 + 1 + 0 = 1 • Result of Boolean matrix multiplication: Boolean matrix multiplication • Boolean matrix multiplication can be expressed using × or · or juxtaposition: A × B = A · B = AB • Boolean matrix multiplication is associative: A × (B × C) = (A× B) × C • Power notation can be used for repeated multiplication of a matrix by itself: • A = A 2 • A = A × A • A = A × A × A • … Union oftwo graphs / relations • If two directed graphs (relations) have the same vertex set (domain), then their union is the set of edges (pairs) that are in either one of the graphs (relations) or both. • Example: G1 G2 • Union is G1∪ G2 Graph Union and Matrix Boolean sum • If G1and G ar2 graphs with adjacency matrices A and 1 A , then the adjacency matrix of G ∪ G is A + A . 2 1 2 1 2 G1 G G ∪ G 2 1 2 A1 A2 A 1 A 2 Powers of a graph If G is a directed graph: • G = G • G is the graph with the same vertex set as G where there is an edge from vertex x to vertex y in G iff there is a walk of length 2 from x to y in G 2 • G is the graph with the same vertex set as G where there is an edge from vertex x to vertex y in G 3iff there is a walk of length 3 from x to y in G • ... k • G is the graph with the same vertex set asG where there is an edge from vertex x to vertex y in G kiff there is a walk of length k from x to y in G • Note that for k=1, this is G Examples on next slide Powers of a graph G G1 G2 G3 Graph powersandMatrix Boolean Product • If G is a graph with adjacency matrices A, then the adjacency matrix of G is Ak k 1 G =G G2 G3 1 2 3 A =A A A Computing Transitive Closure by Matrix Operations • Transitive closure of a graph G: G = G ∪ G ∪ G ∪ ...3 • Let A be the adjacency matrix for G. By what we have just + seen, the adjacency matrix for G is + 1 2 3 A = A + A + A + ... • We can stop the computation: 1. When adding a the next term to the sum doesn’t change the sum, or k-1 2. After adding A , where k is the number of vertices in G. Transitive Closure and Matrix Operations G =G 1 2 3 G G A =A1 A2 A3 G+ A+ Partial Orders • A relation R on a set S is called a partial ordering or partial order if it is: • reflexive • antisymmetric • transitive • A setS together with a partial ordering ≼ is called a partially ordered set or poset, and is denoted by (S, ≼). • The symbol ≼ is used to reflect the fact that a partial order acts like the relation ≤ • The expression a ≼ b can be read as • “a comes before b” • “a precedes or is equal to b” Partial Orders Example 1: Let A and R be the following relation on set A. A = {1,2,3,4} R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} R is a partial order because it is reflexive, antisymmetric, and transitive. Note that this example is just the relation ≤ on the set A Partial Orders Example 2: Let A be a finite subset of integers and define a ≼ b to mean that a evenly divides b. (This is usually written as a | b) For example, if A = {1,2,3,4,5,6,7,8} then the relation would be: {(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8).(2,2),(2,4),(2,6),(2,8), (3,3),(3,6),(4,4),(4,8),(5,5),(6,6),(7,7),(8,8)} This always results in a partial order because for any a,b,c: • a | a (reflexive) • if a | b and b | a then a = b(antisymmetric) • if a | b and b | c then a | c (transitive) Partial Orders In a partially ordered set (A, ≼), two elements x and y of A are comparable if either x ≼ y or y ≼ x. If two elements are not comparable they are incomparable A partial order is a total order if any two elements are comparable. • Example 1 is a total order. • Example 2 is a partial order because 2 and 3 are incomparable. (Neither divides the other) Partial Orders In a partially ordered set (A, ≼): • An element x is a minimal element if there is no element y ≠ x such that y ≼ x • An element x is a maximal element if there is no element y ≠ x such that x ≼ y In example 1: • 1 is the unique minimal element • 4 is the unique maximal element In example 2: • 1 is the unique minimal element • 5,6,7,8 are the maximal elements Partial Orders Example 3: Let X be any set. The relation defined on the power set of X by S ≼ T if S is a subset of T is a partial order . A more concise way of saying the same thing: For any set X, (P(X), ⊆)is a partial order The reason why this is true is that for any sets S,T,U: • S ⊆ S (reflexive) • if S ⊆ T and T ⊆ S then S = T (antisymmetric) • if S ⊆ T and T ⊆ U then S ⊆ U (transitive) Representing Partial Orders • One way to draw a partial order is as a digraph. • There is some redundancy in this representation because partial orders are by definition reflexive and transitive. • Because of this redundancy, a digraph representation of a partial order can become cluttered and hard to read. • The Hasse diagram is a way of graphically representing a partial order in a less cluttered fashion. Hasse diagrams Rules for drawing a Hasse diagram: • For any x and y such that x ≠ y: •If x ≼ y, then x is lower in the diagram than y. •If x ≼ y and there is no z such that x ≼ z and z ≼ y, then there is segment connecting x with y. Rules for reading a Hasse diagram : • The direction of an edge is always up, so there are no arrows on the edges. • Since any partially order is transitive: •If there is a path from x to y along segments that all travel upwards, then x ≼ y . • Since any partially order is reflexive: •It is always true that x ≼ x Hasse Diagrams Example 2 revisited: (A, | ) where A={1,2,3,4,5,6,7,8} Hasse Diagrams (P(X), ⊆ ) where X={1,2,3} One approach to Constructin gasseDiagrams • Start with the digraph of the partial order. • Remove the loops at each vertex. • Remove all edges that must be present because of the transitivity (i.e., derived from other edges) • Arrange each edge so that all arrows point up. • Remove all arrowheads. Strict Orders and Directed Acyclic Graphs Strict order vs. partial order: • A partial order acts similarly to ≤ • A strict order acts similarly to < A relation R on a set S is called a strict ordering or strict order if it is: • anti-reflexive • (anti-symmetric) • transitive Note: anti-symmetry follows from the other two properties, so it is usually not included as part of the definition If R is a strict order and (a,b) ∈ R, we write a ≺ b. This can be read as • “a is less than b” or • “a precedes b” Strict Orders • The digraph representation of a strict order is like the digraph representation of a partial order, • Difference: in a strict order, there are no self-loops Strict Orders Fact: If a relation R is anti-reflexive and transitive, then it is anti-symmetric. Proof: By contradiction. Assume thatR is anti-reflexive, transitive, and not anti-symmetric. We will show this leads to a contradiction. Since R is not anti-symmetric, there is some pair (a,b) with a≠b such that a R band b R a. Since R is transitive, this implies that a R a. But this contradicts the assumption that R is anti-reflexive Because of this fact, we define a strict order to be a relation that is • anti-reflexive • transitive Such a relation is necessarily anti-symmetric as well. Directed Acyclic Graphs A directed acyclic graph (DAG) is a directed graph that does not have any positive-length cycles • DAGs are useful for representing precedence relationships. • Note that there can be “hidden” precedence relationships not explicitly represented by arrows but implied by other arrows. So the relation specified by a DAG is not necessarily transitive • Example: e ≺ g Strict Orders and Directed Acyclic Graphs The relation between strict orders and DAGs is: + Thm 5.5.1: Let G be a directed graph. G is a DAG if and only if G is a strict order. Proof: In the online textbook. DAGS and precedence constraints • Complex tasks or projects are often decomposed into simpler tasks. • Usually there are precedence constraints: Task A must be completed before task B can be started • The precedence relations are anti-reflexive, anti-symmetric, and transitive • DAGs are useful for representing the precedence constraints among tasks • Examples: 1. Baking cookies (see online textbook) 2. Building a house (on following slide, taken from Rosen) • A Hasse diagram can also be used. The major difference is: • DAGs may or may not have edges that are implied by other edges and transitivity • Hasse diagrams cannot have such edges DAG for building a house Hasse diagram for building a house T opological sorting • A topological ordering or topological sort is a sequential listing of the ordering of the vertices in a DAG that is consistent with the precedence constraints represented by the DAG. • Useful if the DAG represents tasks and we want to perform the tasks one at a time. • There may be more than one possible topological ordering Example: 1. acbdefg 2. eacbfdg (There are other valid orderi)gs T opological sorting • The process of deriving a topological ordering from a DAG is called topological sorting • There is a simple, efficient algorithm for doing this: while there is a vertex in G with indegree 0 let v be a vertex with indegree 0 delete v and all edges going out of v from G • This algorithm is nondeterministic • This algorithm is correct: • If G is a DAG, it will produce a valid topological ordering • If G is not a DAG, it will terminate before all vertices have been processed acbdefg, ecabfdg, ... Equivalence relations As we have seen: • A partial order acts similarly to ≤ • A strict order acts similarly to < An equivalence relation acts similarly to = A relation R on a set S is called an equivalence relation if it is: • reflexive • symmetric • transitive A generic equivalence relation is sometimes represented using the symbol ~ Example: Define R as follows. The domain is a set of people. a R B if a and B have the same birthday. The relation R is an equivalence relation. Equivalence classes For an equivalence relation ~ on a set A, the equivalence class of an element a ∈ A is defined by: [a] = {x∈ A: a ~ x} Example: (Continues birthday example from the previous slide) If Y. D. Dandy was born on July 4, then [Y. D. Dandy] = {x: x was born on July 4} Theorem: Consider an equivalence relation on a set A. Let x,y ∈ A: • If x~y then [x]=[y] • If it is not the case that x~y, then [x] ∩ [y] =∅ In other words, the equivalence classes under ~ form a partition of A. Proof: See online textbook (this is theorems 5.6.1 and 5.6.2) Equivalence classes Example: Define the following relation on N, the set of natural numbers: x~y if 5 | (x-y) (i.e., if x-y is evenly divisible by 5 ) Exercise: Verify that this is an equivalence relation. Question 1: What is [3]? [3] = {3, 8, 13, 18, 23, …} Question 2: List all the equivalence classes [0] = {0, 5, 10, 15, 20, …} [1] = {1, 6, 11, 16, 21, …} [2] = {2, 7, 12, 17, 22, …} [3] = {3, 8, 13, 18, 23, …} [4] = {4, 9, 14, 19, 24, …} Equivalence classes Example: An undirected graph is similar to the directed graphs we have talked about, except that the edges are not considered to have directions. In an undirected graph, a walk can traverse an edge in either direction. We say that vertex x is reachable from vertex y if there is a walk from x to y. In an undirected graph, reachability is an equivalence relation. (Reachability is not an equivalence relation in a directed graph. Why not?) For the graph shown on this slide: Question 1: What is [a]? [a]= {a, b, c, d} Question 2: List all the equivalence classes {a, b, c, d} {g} {e,f} The equivalence classes of vertices in an undirected graph are called the connected components of the graph N-ary relations • We can generalize the definition of binary relations to n-ary relations. • A relation on sets A, A 1...,2 is ansubset of A x A x ...1x A .2 n th Each element of the relation is an n-tuple in which the i entry in the n-tuple is from A i • Example: 5 R={ (v,w, x, y, z) ∈ R | v + w + x = y + z} (1,3,5,2,7) is in this relation because 1 + 3 + 5 =9 = 2 + 7 (7,2,5,3,1) is not in this relation. N-ary relations, databases • A database is a large collection of data records that is searched and manipulated by a computer • The relational database model stores data records as relations • The type of data stored in each entry of the n-tuple is called an attribute • A query to a database is a request for a particular set of data. N-ary relations, databases A small airline database represented as a table: Flight Departure Arrival Date Departure Arrival Aircraft Number Airport Airport Time Time 1806 LAX DTW 06/19/2013 9:15AM 4:44PM Boeing 767-300 18 LAX DTW 06/19/2013 1:35PM 8:54PM Boeing 757 1719 DTW LAX 06/22/2013 12:05PM 1:51PM Boeing 737-800 2262 LAX JFK 07/02/2013 1:20PM 9:55PM Boeing 767-300 2262 LAX JFK 07/04/2013 1:20PM 9:55PM Boeing 767-300 2171 JFK LAX 07/07/2013 7:00AM 9:57PM Boeing 767-300 226 LAX SFO 07/07/2013 11:30PM 12:52PM CRJ 900 N-ary relations, databases • A key is an attribute or set of attributes that uniquely identifies an n-tuple in the database • In the flight example: • flight number alone won’t work • (flight number, date) would work • More realistic choice would be (flight number, data, departure city) The Select operation • The selection operation chooses n-tuples from a relational database that satisfy particular conditions on their attributes. • Examples: 1. Select[ Departure Airport = LAX ] 2. Select[ Departure Airport = LAX ∧ date = 07/04/2013 ] The Select operation The original database: Flight Departure Arrival Date Departure Arrival Aircraft Number Airport Airport Time Time 1806 LAX DTW 06/19/2013 9:15AM 4:44PM Boeing 767-300 18 LAX DTW 06/19/2013 1:35PM 8:54PM Boeing 757 1719 DTW LAX 06/22/2013 12:05PM 1:51PM Boeing 737-800 2262 LAX JFK 07/02/2013 1:20PM 9:55PM Boeing 767-300 2262 LAX JFK 07/04/2013 1:20PM 9:55PM Boeing 767-300 2171 JFK LAX 07/07/2013 7:00AM 9:57PM Boeing 767-300 226 LAX SFO 07/07/2013 11:30PM 12:52PM CRJ 900 The Select operation The result of Select[ Departure Airport = LAX ] Flight Departure Arrival Date Departure Arrival Aircraft Number Airport Airport Time Time 1806 LAX DTW 06/19/2013 9:15AM 4:44PM Boeing 767-300 18 LAX DTW 06/19/2013 1:35PM 8:54PM Boeing 757 2262 LAX JFK 07/02/2013 1:20PM 9:55PM Boeing 767-300 2262 LAX JFK 07/04/2013 1:20PM 9:55PM Boeing 767-300 226 LAX SFO 07/07/2013 11:30PM 12:52PM CRJ 900 The Select operation The result of Select[ Departure Airport = LAX ∧ date = 07/04/2013 ] Flight Departure Arrival Date Departure Arrival Aircraft Number Airport Airport Time Time 2262 LAX JFK 07/04/2013 1:20PM 9:55PM Boeing 767-300 The Project operation • The projection operation takes a specified subset of attributes and produces, for each n-tuple, a tuple containing just those attributes. It then removes all duplicate tuples. • Example: Project[ Departure Airport, Arrival Airport ] The Project operation The original database: Flight Departure Arrival Date Departure Arrival Aircraft Number Airport Airport Time Time 1806 LAX DTW 06/19/2013 9:15AM 4:44PM Boeing 767-300 18 LAX DTW 06/19/2013 1:35PM 8:54PM Boeing 757 1719 DTW LAX 06/22/2013 12:05PM 1:51PM Boeing 737-800 2262 LAX JFK 07/02/2013 1:20PM 9:55PM Boeing 767-300 2262 LAX JFK 07/04/2013 1:20PM 9:55PM Boeing 767-300 2171 JFK LAX 07/07/2013 7:00AM 9:57PM Boeing 767-300 226 LAX SFO 07/07/2013 11:30PM 12:52PM CRJ 900 The Project operation The result ofProject[ Departure Airport, Arrival :irport ] Departure Arrival Airport Airport LAX DTW DTW LAX LAX JFK JFK LAX LAX SFO Combining Operations • The selection and projection operations can be combined to answer queries.. • Example: From which airports does the Boeing 767-300 depart? •To answer this question: 1. Select[ Aircraft = Boeing 767-300] (result is just flights that use a Boeing 767-300 2. Project intermediate result onto Departure Airport Combined query example The original database: Flight Departure Arrival Date Departure Arrival Aircraft Number Airport Airport Time Time 1806 LAX DTW 06/19/2013 9:15AM 4:44PM Boeing 767-300 18 LAX DTW 06/19/2013 1:35PM 8:54PM Boeing 757 1719 DTW LAX 06/22/2013 12:05PM 1:51PM Boeing 737-800 2262 LAX JFK 07/02/2013 1:20PM 9:55PM Boeing 767-300 2262 LAX JFK 07/04/2013 1:20PM 9:55PM Boeing 767-300 2171 JFK LAX 07/07/2013 7:00AM 9:57PM Boeing 767-300 226 LAX SFO 07/07/2013 11:30PM 12:52PM CRJ 900 Combined query example Select[ Aircraft = Boeing 767-300] : Flight Departure Arrival Date Departure Arrival Aircraft Number Airport Airport Time Time 1806 LAX DTW 06/19/2013 9:15AM 4:44PM Boeing 767-300 1719 DTW LAX 06/22/2013 12:05PM 1:51PM Boeing 737-800 2262 LAX JFK 07/02/2013 1:20PM 9:55PM Boeing 767-300 2262 LAX JFK 07/04/2013 1:20PM 9:55PM Boeing 767-300 2171 JFK LAX 07/07/2013 7:00AM 9:57PM Boeing 767-300 Combined query example Project intermediate result onto Departure Airport Departure Airport LAX DTW JFK

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.