CSE510-Database-Management-System

发表于 | 分类于
按照要求实现Database Management System中的功能。

Goal

The version of the MiniBase I have distributed to you implements various modules of a relational database management system. Our goal this semester is to use these modules of MiniBase as building blocks for implementing a user preference sensitive DBMS to support e-commerce applications:

S. Borzsony, D. Kossmann and K. Stocker, “The Skyline operator,” Proceedings 17th International Conference on Data Engineering, Heidelberg, Germany, 2001, pp. 421-430, doi: 10.1109/ICDE.2001.914855.
Chomicki J., Godfrey P., Gryz J., Liang D. (2005) Skyline with Presorting: Theory and Optimizations. In: Kopotek M.A., Wierzcho S.T., Trojanowski K. (eds) Intelligent Information Processing and Web Mining. Advances in Soft Computing, vol 31. Springer, Berlin, Heidelberg.
K.L. Tan, P.K. Eng and B. C. Ooi. “Efficient Progressive Skyline Computation.” 27th Int. Conference on Very Large Data Bases (VLDB), Roma, Italy, 301-310, September 2001.

Project Description

The following is a list of tasks that you need to perform for this phase of the project: Note that getting these working may involve other changes to various modules not described below.

Task 1

Create a new tuple comparison method, Dominates,

1
2
3
4
5
6
7
8
static boolean Dominates(Tuple t1,
                         AttrType[] type1,
                         Tuple t2,
                         AttrType[] type2,
                         short len_in,
                         short[] str_sizes,
                         int[] pref_list,
                         int pref_list_length)

which returns

1 if t1 dominates t2 in the list of preference attributes
0 otherwise.
Create a new tuple comparison method, CompareTupleWithTuplePref,

1
2
3
4
5
6
7
8
static boolean CompareTupleWithTuplePref(Tuple t1,
                                         AttrType[] type1,
                                         Tuple t2,
                                         AttrType[] type2,
                                         short len_in,
                                         short[] str_sizes,
                                         int[] pref_list,
                                         int pref_list_length)

which returns

0 if they are equal
1 if the tuple, t1, is greater
-1 if the tuple, t1, is smaller
on the “sum” of their preference attributes.

Task 2

Modify Sort in such a way that the tuples are sorted according to the new CompareTupleWithTuplePref on their preference attributes:

1
2
3
4
5
6
7
8
SortPref(AttrType[] in,
         short len_in,
         short[] str_sizes,
         Iterator am,
         TupleOrder sort_order,
         int[] pref_list,
         int pref_list_length,
         int n_pages)

Here, pref list is the list of attributes that are going to be used for preference sorting, pref list length is the number of preference attributes, and n pages is the number of buffer frames (each of the size of a single disk page) allocated for this operation.

Task 3

Implement NestedLoopsSky BlockNestedLoopsSky and SortFirstSky iterators, which compute skylines

1
2
3
4
5
6
7
8
9
10
11
12
13
14
NestedLoopsSky(AttrType[] in1, int len_in1, short[] t1_str_sizes,
               Iterator am1, java.lang.String
               relationName, int[] pref_list, int pref_list_length,
               int n_pages)

BlockNestedLoopsSky(AttrType[] in1, int len_in1, short[] t1_str_sizes,
                    Iterator am1, java.lang.String
                    relationName, int[] pref_list, int pref_list_length,
                    int n_pages)

SortFirstSky(AttrType[] in1, int len_in1, short[] t1_str_sizes,
             Iterator am1, java.lang.String
             relationName, int[] pref_list, int pref_list_length,
             int n_pages)

Task 4

Implement a BTreeSky iterator which computes skylines using BTrees on individual preference attributes.

1
2
3
4
5
BTreeSky(AttrType[] in1, int len_in1, short[] t1_str_sizes,
         Iterator am1, java.lang.String
         relationName, int[] pref_list, int[] pref_list_length,
         IndexFile[] index_file_list,
         int n_pages)

Related publication [Borzsonyi et al. 2001]. This operator will assume that the BTree indexes on the preference attributes have already been created.

Task 5

Implement a BTreeSortedSky iterator which computes skylines using a combined BTree on preference attributes.

1
2
3
4
5
BTreeSortedSky(AttrType[] in1, int len_in1, short[] t1_str_sizes, int
               Iterator am1, java.lang.String
               relationName, int[] pref_list, int[]
               pref_list_length, IndexFile index_file,
               int n_pages)

Task 6

Implement a program which, given a data file [format described below], stores and indexes the data in
Minibase. The program should then let the user specify attributes that will be used for skyline computation and the number of memory pages available for the operation.

1
2
3
4
5
6
7
8
9
Input data format: # of attributes in the first line, followed by rows of values between 0.0 and 1.0. For example
4
0.4 0.6 0.2 0.8
0.3 0.4 0.2 0.4
..... or
3
0.100 0.345 0.3456
0.2345 0.222 0.347
....

The program should output both the resulting skylines and the number of read and write pages accesses during the operation (see Task 7).

Note: You may need to modify the Minibase BTree index structure to support creation of a combined BTree index on preference attributes.

Note: The operators that you are implementing cannot use more buffer frames than specified in the input.

Task 7

Modify Minibase disk manager in such a way that counts the number of reads and writes. One way to do this is as follows:

First create add pcounter.java, where

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package diskmgr;
public class PCounter {
	public static int rcounter;
	public static int wcounter;
	public static void initialize() {
		rcounter = 0;
		wcounter = 0;
	}

	public static void readIncrement() {
		rcounter++;
	}

	public static void writeIncrement() {
		wcounter++;
	}
}

into your code.

Then, modify the read_page() and write_page() methods of the diskmgr to increment the appropriate counter upon a disk read and write request.

Deliverables

You will be provided with a sample data set. You have to return the following before the deadline:
Your source code properly commented, tared and ziped.
The output of your program with the provided test data and the driver.
A report which describes who did what. This will be taken very seriously! So, be honest. Be prepared to explain on demand (not only your part) but the entire set of modifications. See the report specifications.
A confidential document (individually submitted by each group member) which rates group members’ contributions out of 10 (10 best; 0 worst). Please provide a brief explanation for each group member.