In-Memory Data Management 2015

Back to course details

Week 2

Solutions Assignment Week 2

Dear learning community,

as many of you asked for some more details on the correct answers for the closed assignments or access to the past questions if you missed them, we decided to put the solutions online in the respective week.

If there are any questions left, please do not hesitate to ask in the forum.

Best regards,
Ralf for the IMDB Teaching Team

Week 2
Question Name: Compression Techniques

Text: Which of the following is an actual compression technique?

Correct answer:

  • Prefix Encoding

Incorrect answers:

  • Line Width Encoding
  • Open Table Encoding
  • Red Blue Encoding


Question Name: Compression Example Run Length Encoding Assignment

Text: Suppose there is a table where all 14 million inhabitants of Blueland are assigned to their cities. The table is sorted by city. Blueland consists of about 3,000 cities (represented by 12 bit). Further assume that inhabitants are uniformly distributed across cities. Using Run Length Encoding with a start position vector, what is the size of the compressed city vector? Always use the minimal number of bits required for any of the values you have to choose and include all needed auxiliary structures. Further assume the following conversions: 1MB = 1,000 KB, 1KB = 1,000B

Correct answer:

  • 13.5 kB

Incorrect answers:

  • 6 kB
  • 20.5 kB
  • 2 MB

General explanation: We have to compute the size of a) the value array and b) the size of the start position array. The size of a) is the distinct number of cities (3,000) times the size of each field of the value array (log_2(3,000)). The size of b) is the number of entries in the dictionary (3,000) times the number of bits required to encode the highest possible number of inhabitants (log_2(14,000,000)). The total result is thus 12 bit times 3,000 (36,000) plus 24 bit times 3,000 (72,000), thus 108,000 bits (or 13.5 kB) in total.


Question Name: Suitable Use Cases for Column Layout

Text: A columnar layout is well suited to ...

Correct answer:

  • ... process sets and do full column scans

Incorrect answers:

  • ... transform data
  • ... handle insert operations
  • ... materialize full tuples

General explanation: A columnar layout is especially suited to do set operations and full column scans. The complexity of data transformation is not influenced by the chosen layout. Insert operations are more cumbersome in a columnar layout than in a row layout, since we have to distribute the values of a tuple over different columns and therefore place them in different memory regions. On top of that come auxiliary structures like dictionaries, which have to be kept up to date. These migth also be used on row layouts, so the layout is not the influencing part concerning to that. But in general, row layouts are better suited for inserts than columnar layouts. For the same reasons is tuple reconstruction easier on row layouts than on columnar layouts.


Question Name: Suitable partitioning strategy

Text: Assume a table with customer data. Three different units in a company do support for the customers but also have to provide analytics about the customers they handle. The table is distributed over several servers, each unit has a server. What partitioning type is suited best if the company decided that the first organizational unit should handle customers with last names A-G, the second unit customers with last names H - R, and the last unit customers with last names S- Z?

Correct answer:

  • Range Partitioning

Incorrect answers:

  • Hash Partitioning
  • Round Robin Partitioning

General explanation: Based on the decision to assign specifc ranges of names to specific organizational units, like the word says, range partitioning is most suited. Every organisational unit can have their primary data close to them, if we have a distributed server landscape. Hash partitioning could not guarantee the best locality. Of course, one could choose the first letter as the partitioning key, but at a closer look, this is range partitioning in disguise again. Round robin partitioning would clearly prohibit the locality advantage, since it would distribute the entries fairly over all servers, regardless of the actual information in the entries.


Question Name: Fast Execution

Text: Assume the following inserts in an empty dictionary-encoded column store table (without differential buffer):
A: INSERT INTO cars VALUES(‘Porsche’, ‘2011’, ‘Cayenne’);
B: INSERT INTO cars VALUES(‘Volkswagen’, ‘2014’, ‘Passat’);
C: INSERT INTO cars VALUES(‘Seat’, ‘2012’, ‘Leon’);
What execution order would work fastest?

Correct answer:

  • A, C, B

Incorrect answers:

  • B, C, A
  • A, B, C
  • C, A, B

General explanation: A, C, B is correct here. This way the new dictionary values could simply be appended. Therefore there is no need for resorting dictionaries and rebuilding attribute vectors.


Question Name: Dictionary reordering after updates

Text: Consider the world population table (first name, last name) that includes all people in the world: Angela Mueller marries Friedrich Schulze and becomes Angela Schulze. Should the dictionary for the last name column be reordered?

Correct answer:

  • No, because the value ‘Schulze’ is already in dictionary

Incorrect answers:

  • No, because ‘Schulze’ > ‘Mueller’ when compared lexicographically
  • Yes, because ‘Schulze’ is a new last name of Angela

General explanation: Mr. Friedrich Schulze is already in this table. Therefore ‘Schulze’ is in the last-name dictionary and its key can be taken to update the last name of Ms. Mueller (now Mrs. Schulze)


Question Name: Delete implementation for hospital

Text: Assume you have to setup a new database for a hospital which allows the hospital staff to keep track of all their patient records. Which delete implementation should be preferred for that use case?

Correct answer:

  • Logical delete

Incorrect answers:

  • Doesn’t matter
  • Physical delete
  • Depends on the number of patients

General explanation: Hospitals typically have very strict regulations for keeping patient data, regardless of their number of patients. They need to be able to look at patient histories for multiple years. When using only logical delete, the data is still available for queries concerning the past. A physical delete would not allow this.


Question Name: Point Representation

Text: Considering point representation and a table with one tuple, that was invalidated five times, how many tuples have to be checked to insert a new tuple?

Correct answer:

  • None, the tuple can just be inserted with the current time stamp

Incorrect answers:

  • Only one, that is, the most recent one
  • Five
  • Two, the oldest and the newest to determine the time stamp

General explanation: In point representation, only the tuple with the newest time stamp is valid. However, when inserting a new tuple, no other tuple must be checked, because the new one will always have the latest time stamp.


Question Name: Point Representation Selects

Text: Consider point representation and a table with only one tuple, that was invalidated three times. How many tuples have to be checked to find the most recent tuple?

Correct answer:

  • Four

Incorrect answers:

  • Only one, that is, the first which was inserted
  • Five
  • Two, the most recent one and the one before that

General explanation: Point representation has no valid_until timestamps, which means that all versions of an entry have to be checked to find the most recent tuple. If the entry was inserted and then invalidated 3 times, the total number of tuples is therefore 4.


Question Name: Time Travel Queries

Text: What is a time travel query?

Correct answer:

  • A query that enables the user to view the data as it was at a specified earlier point in time

Incorrect answers:

  • A query that inserts future time stamps
  • A query that automatically projects current developments into the future
  • A very short and therefore fast query

General explanation: Time travel queries allow users to easily query the database for historic data. They can state that they want to see the database "as it was on a certain point in time" and see exactly the results that were valid then. Future time stamps are never inserted in a database as creation or update timestamps, since they would contradict the integrity of the data. Queries that make analyses based on assumptions and project developments into the future are called "predictive queries". Short and fast queries have no special name.