Question 1 [Entity-Relation Design] (24%)
Please read the below background information of a simple blockchain data structure.
Background Information. A simple blockchain is a linked list of blocks as shown in the below figure, where each block contains a unique block ID, a hash (a unique string of characters), a hash of the previous block, and a creation time of the block. Each block is used to store transaction data, which are records of transferring digital currency. A unit of the digital currency is called a token. Each token can be uniquely identified by a token ID and has a market value.
Please read the below users’ requirements, and answer questions (a) and (b).
User Requirements. A HKU-DBMS team is building a transaction system by using blockchain.
– The main purpose of the system is to manage transactions of tokens between accounts.
– Each user in the system is identified by a unique username. Each user has a profile attribute,
which consists of a name, an email address, and the date the user joined the system.
– A user owns one or more accounts. Each account in the system is identified by a unique account
number, and an account must be owned by a user.
– There are two specifications of accounts, including token account and virtual account. An account
is either a token account or a virtual account.
– Token account is an account that keeps tokens in the system. Each token can be uniquely
identified by a token ID and has its market value.
– A token mush be owned by only one token account. A token account may or may not have one
or more tokens.
– Virtual account has no token by itself. Instead, it must be linked to one or more token accounts.
A token account may or may not have multiple virtual accounts.
– A transaction is initiated by specifying a total amount to be transferred from one account to
another account, for example, either from a token account to a virtual account or from a virtual account to a token account. Each transaction is uniquely identified by a transaction ID. It is possible to leave (attach) several messages along with the transaction.
– A transaction must be kept in only one block. Each block has a unique block ID and a creation time, and each block may or may not have multiple transactions. A hash value is calculated and recorded in each block.
– A block is always linked to only one previous block (except for the very first block in the system), in order to form a blockchain. The hash value of the previous block is also explicitly recorded in a block. It is possible that multiple blocks have the same previous block at the same time.
– In fact, each transaction is completed by using one or more internal transactions. An internal transaction has an internal ID, which can only uniquely identify each internal transaction when combining with the corresponding transaction ID.
– Each internal transaction is used to transfer one token from one token account to another token account.
Page 1 of 4
(a) (15%) Please model the above users’ requirements by drawing the corresponding E-R Diagram. • If a requirement is unclear, a reasonable assumption could be made. You must clearly
state all such assumptions.
(b) (9%) Please reduce your E-R Diagram into relational table schemas. For each relation, underline
the primary key and identify all foreign key(s), if any.
Question 2 [SQL] (16%) Given the below tables as examples, please write one SQL query for each of the following questions from (a) to (e). (Note: the primary key for each table is indicated in orange and the foreign keys are indicated by red arrows. Definitions of these tables are not the same as Question 1.)
(a) (2%) Find the hash value of the block(s) that has more than one next block.
(b) (3%) Find the transaction ID of the transaction(s) where the total token value does not match
with the transaction amount.
(c) (3%)Findinternaltransaction(s)thatisproducedby‘Alice’andthetransferredtokenvalueis
smaller than 100. Return internal ID and its token value.
(d) (4%) Find the token ID of the token(s) that has never been transferred.
(e) (4%) Show the username and the number of accounts the user owns for the user(s) that has
the greatest number of tokens with value greater than 100.
Question 3 [Relational Algebra] (20%)
(a) (3%)GiventhebelowrelationsR(A,B),R1(B),R2(B),andR3(B),showtheresultingtablesofR/R1, R/R2, and R/R3 respectively.
Page 2 of 4
(b) (4%) Let R and S be two relations, which have attribute set A and B respectively and B is a subset of A. Write two equivalent definitions of the division R/S.
(c) (4%) Please transform your SQL query for Question 2(c), i.e. “Find internal transaction(s) that is produced by ‘Alice’ and the transferred token value is smaller than 100. Return internal ID and its token value.”, to relational algebra expression and draw the corresponding expression tree. (Hint: you do not need to apply equivalence rules.)
(d) (9%) Apply at least 4 equivalence rules to optimize your relational algebra expression in (c), write the final relational algebra expression after optimization and draw the final optimized expression tree.
• Describe clearly your results and list the equivalence rules used step by step;
• Use the example tables in Question 2 to explain clearly the computational complexity
of the relational algebra expression in (d) compared to that in (c).
Question 4 [Functional Dependence (FD)] (20%) Please answer the below questions (a) and (b).
(a) Consider a relation R(A, B, C, D, E, F, G) that satisfies a set of FDs F = {A → BCD, BCE → DF, DEF → CG}.
(a.1) (4%) Give a formal proof whether ADE → CG is true. ++
(a.2) (4%) Find A and {B, C, E} .
(b) Consider a table R(A,B,C,D) with a set of FDs F = {A → BCD,B → C,B → D}.
(b.1) (6%) Find all candidate keys of R and explain clearly your results.
(b.2) (6%) Find the FD closure of F, i.e. F+. (Hint: for an attribute set with too many FDs, you don’t need to list them explicitly, but please explain clearly how many FDs you find and how to construct their LHSs and RHSs.)
Question 5 [Database Normalization] (20%) Given R = (A, B, C, D) and a set of FDs on R, F = {A → B,A → C,A → D,B → C,D → B}. Please answer questions (a) and (b).
(a) (5%) Is R in BCNF? Why?
Page 3 of 4
(b) (15%) Decompose R into relations that satisfy the below requirements. Explain clearly your results.
1) The decompositions must be a lossless-join decomposition;
2) The decompositions must preserve functional dependence;
3) All decomposed relations must be in BCNF.
END OF PAPER
Page 4 of 4