Merging two data sources in pseudocode

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which describes the basic merge algorithm for two data sources?

A Loop through one source and look up the record with the matching key in the other

B Join the two sources end to end without checking any keys

2. A student has two lists, students and results, both with a studentId. Which should be the key field for the merge?

A mark, because it is a number

B studentId, because it identifies the same person in both sources

3. A record in source A has key 7, but source B has no record with key 7. What should the merge do?

A Append the unmatched record to the merged result (or handle it by a clear rule)

B Ignore the problem and let the program crash

4. Which pseudocode line correctly tests whether two records match on the key?

A if a.id <- b.id then

B if a.id = b.id then

5. What is the risk if you append every record from source B without checking whether its key is already in the merged result?

A Duplicate keys appear in the merged result

B The result will be sorted in the wrong order

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1for each s in students		ABoth records are appended without matching on the key, so the same student appears twice with duplicate keys instead of one combined record
2if s.studentId = r.studentId then		Bif found = false then append s to merged
3A record with no match in the other source is appended to the merged result instead of being dropped		CLoops through every record in the first data source so each one can be checked against the second source
4Before adding a record, check that its key is not already in the merged result, so there are no duplicate keys		Dif key not in merged then append record to merged
5for each s in students append s to merged append r to merged		EThere is no handling for records with no match, so unmatched students are lost from the merged result
6for each s in students if s.studentId = r.studentId then append combined to merged endif next s		FMatches records from the two sources on the key field

Definitions

merge algorithm

Fill in the Blanks

Complete each line of code by filling in the missing parts.

for each a in sourceA for each b in sourceB if a.id _ b.id then

found ← false if found = _____ then append b to merged

if a.id = b.id then newRec ← _______(a, b) append newRec to merged

for each b in sourceB if ___ exists(b.id, merged) then append b to merged

merged ← [] ________ a in sourceA append a to merged

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A for each a in listA

B for each b in listB

C if a.id = b.id then

D a.score <- a.score

E end if

Question 2

A for each a in listA

B found <- false

C for each b in listA

D if a.id = b.id then

E found <- true

F end if

Question 3

A for each n in newList

B if n.id not in master then

C append n to newList

D end if

Question 4

A for each n in newList

B if n.id in master then

C append n to master

D else

E append n to master

F end if

Question 5

A merged <- empty array

B for each a in merged

C for each b in listB

D if a.id = b.id then

E append a + b to merged

F end if

Answer Key

Merging two data sources in pseudocode

Section A: Quick Questions

A — Loop through one source and look up the record with the matching key in the other

B — studentId, because it identifies the same person in both sources

A — Append the unmatched record to the merged result (or handle it by a clear rule)

B — if a.id = b.id then

A — Duplicate keys appear in the merged result

Section B: Match the Pairs

for each s in students → Loops through every record in the first data source so each one can be checked against the second source

if s.studentId = r.studentId then → Matches records from the two sources on the key field

A record with no match in the other source is appended to the merged result instead of being dropped → if found = false then append s to merged

Before adding a record, check that its key is not already in the merged result, so there are no duplicate keys → if key not in merged then append record to merged

for each s in students append s to merged append r to merged → Both records are appended without matching on the key, so the same student appears twice with duplicate keys instead of one combined record

for each s in students if s.studentId = r.studentId then append combined to merged endif next s → There is no handling for records with no match, so unmatched students are lost from the merged result

Section C: Definitions

merge algorithm — Loops through one data source, finds the record with the matching key in the other, then combines them or appends unmatched records, avoiding duplicate keys.

Section D: Fill in the Blanks

for each a in sourceA
  for each b in sourceB
    if a.id = b.id then

found ← false
if found = false then
  append b to merged

if a.id = b.id then
  newRec ← combine(a, b)
  append newRec to merged

for each b in sourceB
  if not exists(b.id, merged) then
    append b to merged

merged ← []
for each a in sourceA
  append a to merged

Section E: Spot the Error

D — The score must be copied from the matching record in the other source (b.score). Assigning a.score to itself changes nothing, so nothing is merged. It should be a.score <- b.score.

C — The inner loop must search the other data source, listB, for the matching key. Looping through listA again only compares listA with itself. It should be for each b in listB.

C — An unmatched record has to be added to the merged data source (master). Appending it to newList, the list being looped through, does not merge anything. It should be append n to master.

C — When the key already exists in master, appending the record creates a duplicate key. A matched record should update or combine with the existing record, for example update master record.

B — merged starts empty, so looping through it never runs and nothing is ever merged. The outer loop must go through the source data, for each a in listA.