A “Union” Algorithm for Cell Array Databases

Return to List of Lectures

Previous Lecture

• Misc
  • SOFIs
    • Fill them out via http://go.geneseo.edu/sofi_survey
    • Useful to me in improving courses
    • 5 responses so far
  • Final
    • Tuesday, May 12, 8:00 AM
    • Comprehensive, but emphasizing material since 2nd hour exam (e.g., cell arrays, strings, files, etc.)
    • Designed for 2 hours, you’ll have 3
    • Otherwise similar rules and format to hour exams
    • Donuts and cider
• Questions?
• Union Algorithm for Relations in Cell Arrays
  • Examples
    • Union of csContributions and physicsContributions
      • Result should be
        

        'Alan Turing', 'Computability', [1936]
        'Grace Hopper', 'COBOL', [1959]
        'John von Neumann','Stored-Program C...',[1945]
        'Isaac Newton', 'Laws of Motion', [1687]
        'Albert Einstein', 'Special Relativity', [1905]

    • Union of years projected from csContributions with years projected from mathContributions
      • This illustrates how you can build complicated expressions from basic operations on relations
      • This example also has a duplicate (1936 appears in each relation) that has to be removed
      • Result should be
        

        1936
        1959
        1945
        1666
        1675
        1931
        1930

  • Algorithm in English
    

    Display relation1
    Append any tuples from relation2 not in relation1

  • Pseudocode algorithm
    • What if the two input relations have different numbers of attributes?
      • Don’t have to worry about it—it’s not a valid union of relations because the result wouldn’t be a relation
        • (It can’t be formed as a cross product of any fixed number of sets)
          
      • Precondition: relation1 and relation2 have same size and structure tuples (i.e., are subsets of same cross product)
        

        result = empty cell array
        next = 1
        for i = 1 : size(relation1,1)
            for j = 1 : size(relation2,1)
                if {i,:,:} ~= {j,:,:}
                    result(next,:) = relation2(j,:)
                    next = next + 1

    • Mentally checking this algorithm against examples shows that it doesn’t work
      • It will put multiple copies of items from relation2 into the result, because everything in relation2 will not equal many things in relation1
      • So you need to somehow fix the loops and the way they control the comparison
      • But it’s much easier to do this in pseudocode than as a last-minute response to Matlab code that produces wrong answers
      • An advantage of writing—and checking—pseudocode algorithms before writing actual code
• Next
  • Grade relations / cell arrays lab by Thursday
  • Grade Mad Libs project by Tuesday May 12
  • Exam on Tuesday, May 12

(No Next Lecture)