CSCI 585 Exam 1 Sample Questions

(*20 points) The ER data model supports the concept of entities and relationships. What is the formal definition of an entity and a relationship? Provide an example to illustrate these two concepts.

An entity is a “thing” which can be distinctly identified. A specific person, company, or event is an example of an entity. A relationship is an association among entities. For instance, “father-son” is a relationship between two person ‘entities.’

(*15 points) An attribute has a formal definition in the ER data model. What is its definition?

An attribute is a function that maps from an entity or relationship set into a value set or a Cartesian product of a value set

(*20 points) State three similarities between Gamma and Grasper.

• Both hide parallelism using a query language.

• Both partition data across the nodes.

• Both support the concept of operators that process data in an overlapped processing manner, i.e., pipelined manner.

• Grasper's coordinator is similar to Gamma's scheduler. Both coordinate the execution of a query.

(*20 points) State three differences between Gamma and Grasper.

• Gamma replicates data using chained de-clustering to tolerate failures. Grasper does not have failure handling.

• Gamma uses a mass storage device such as a disk. Grasper is an in-memory system.

• Grasper uses specialized hardware such as RDMA. Gamma uses off-the-shelf hardware.

• Grasper uses work stealing to balance the load. Gamma does not have such a mechanism.

• Gamma supports SQL while Grasper supports Gremlin.

• Gamma targets the relational data model while Grasper targets the graph data model.

• Grasper caches data from other nodes to its node while Gamma ships a query to execute on the node with the relevant data - no caching.

  • Grasper has the master for load balancing. Gamma does not have this concept.

(*15 points) State two similarities between FoundationDB and Nova-LSM

• Both are key-value stores.

• Both have disaggregated hardware architecture.

• Both consist of individually scalable components.

• Both separate storage from processing.

• Both range partition data across their storage nodes.

(*15 points) State two differences between FoundationDB and Nova-LSM

• FDB implements the concept of transactions consisting of read and write sets.

• Nova-LSM's transactions are at the granularity of a one read or one write.

• FDB uses off-the-shelf hardware while Nova-LSM uses specialized hardware in the form of RDMA.

• The storage manager of FoundationDB is a plug-n-play component. Nova-LSM has a fixed storage component that cannot be changed.

• FDB may span multiple data centers. Nova-LSM is for one data center because it uses RDMA.

(*15 points) Name 3 factors that the Hybrid Range Partitioning Strategy uses to determine the number of records a fragment of a table should contain

• The resource requirements of the queries accessing the relation,

• The processing capability of the system,

• The overhead of using each additional processor to execute a query

• The cost of searching the range table constructed by the hybrid-range de-clustering strategy.

(*35 points) Consider a very selective query that fetches one record from a very large table (tens of Petabytes in size) using an index structure, say a B+-tree index. The table is partitioned across 200 nodes in a data center. What happens to the query response time and system throughput if this query is directed to all 200 nodes for processing? Make sure to explain your answer.

Increases response time by incurring the overhead of activating and deactivating the query across 200 nodes. By directing the query to a single node, the system incurs the overhead of activating and deactivating the query on a single node.

Reduces throughput by requiring 199 nodes to search their index structure to find no qualifying record. Searching an index uses system resources. If the query was directed to a single node then 199 nodes would save their resources to process other concurrent queries

What is the difference between an entity attribute and a relationship attribute? Provide one example of each.

An entity attribute is a value associated with a “thing”, the entity. An example is a ‘person’ entity can have the attribute ‘age = 21’.
A relationship attribute is a value associated with association between two entities. Do not confuse with a role. An example is an ‘family’ relationship can have the attribute ‘adopted = true’.

State 3 similarities between Gamma’s range partitioning and the Hybrid-Range partitioning Strategy

State 3 differences between Gamma’s range partitioning and the Hybrid-Range partitioning Strategy.

(5 points) What is the definition of BG’s unpredictable data?

Stale, inconsistent, or simply invalid data produced by a data store

(10 points) What is an example SLA?

SLA may require at least 95% of actions to be faster than 100ms with no more than 0.1% unpredictable data for 1 hour