首页
网站开发
桌面应用
管理软件
微信开发
App开发
嵌入式软件
工具软件
数据采集与分析
其他
首页
>
> 详细
代做COMP3211、Python/Java程序代写
项目预算:
开发周期:
发布时间:
要求地区:
Coursework Specification
Late submissions will be penalised at 10% per working day.
No work can be accepted after feedback has been given.
You should expect to spend up to 37.5 hours on this assignment.
Please note the University regulations regarding academic integrity.
Module: COMP3211 Advanced Databases
Assignment: Database Programming Exercise Weighting: 25 %
Deadline: 16:00 Wed 8 May 2024 Feedback: Fri 17 May 2024
Instructions
In this assignment, you will build a query optimiser for SJDB, a simple RDBMS. Your optimiser should accept a
canonical query plan (a project over a series of selects over a cartesian product over the input named
relations) and aim to construct a left-deep query plan which minimises the sizes of any intermediate relations.
Part 1: Estimator.java
Before implementing an optimiser for query plans, you must first estimate the cost of the query plans.
In the first phase, you must create a class Estimator that implements the PlanVisitor interface and performs
a depth-first traversal of the query plan. On each operator, the Estimator should create an instance of Relation
(bearing appropriate Attribute instances and tuple counts) and attach to the operator as its output.
Some operators may require you to revise the value counts for the attributes on the newly created output
relations (for example, a select of the form attr=val will change the number of distinct values for that
attribute to 1). Note also that an attribute on a relation may not have more distinct values than there are
tuples in the relation.
Page 5 of this coursework specification lists the formulae that you should use to calculate the sizes of the
output relations, and to revise the attribute value counts. The supplied distribution of SJDB includes a
skeleton for Estimator, including an implementation of the visit(Scan) method.
Part 2: Optimiser.java
Once you have an estimator, you must create a class Optimiser that will take a canonical query plan as input,
and produce an optimised query plan as output. The optimised plan should not share any operators with the
canonical query plan; all operators should be created afresh.
In order to demonstrate your optimiser, you should be able to show your cost estimation and query
optimisation classes in action on a variety of inputs. The SJDB zip file contains a sample catalogue and
queries. In addition, the SJDB class (see page 3) contains a main() method with sample code for reading a
serialised catalogue from file and a query from stdin.
Part 3: Report
In addition to your estimator and optimiser, you should produce a short (maximum 500 word) report that
describes the optimisation strategy that you’ve adopted.
Note
You should not need to modify any of the provided classes or interfaces as part of your submission (aside
from Estimator), but if you think that you have a justifiable reason for doing so, please contact Nick for
permission first.
2
Submission
Please submit your files (Estimator.java, Optimiser.java and report.pdf) using the electronic hand-in system
(http://handin.ecs.soton.ac.uk/) by 4pm on the due date.
Late submissions will be penalised at 10% per working day and no work can be accepted after feedback has
been given.
You should expect to spend up to 37.5 hours on this assignment, and you should note the University
regulations regarding academic integrity:
http://www.calendar.soton.ac.uk/sectionIV/academic-integrity-statement.html
Relevant Learning Outcomes
1. The internals of a database management system
2. The issues involved in developing database management software
3. Demonstrate how a DBMS processes, optimises and executes a query
4. Implement components of a DBMS
Marking Scheme
Criterion Description Outcomes Total
Cost Estimator Implementation of the cost estimator 1,2,3,4 40 %
Optimiser Implementation of the query optimiser 1,2,3,4 40 %
Report Description of your query optimisation strategy 1,2,3 20 %
Note that partial credit will be given for incomplete solutions; for example, an optimiser that moves some
(but not all) selections down the query plan will still receive part of the total mark for the optimiser
component.
3
SJDB – A Simple Java Database
SJDB supports a limited subset of the relational algebra, consisting of the following operators only:
• cartesian product
• select with a predicate of the form attr=val or attr=attr
• project
• equijoin with a predicate of the form attr=attr
• scan (an operator that reads a named relation as a source for a query plan)
In addition, all attributes on all relations will be strings; there are no other datatypes available. Attributes also
have globally unique names (there may not be two attributes of the same name on different relations), and
self-joins on relations are not permitted.
The sjdb package contains the following classes and interfaces:
Relation an unnamed relation, contains attributes
NamedRelation a named relation
Attribute an attribute on a relation
Predicate a predicate for use with a join or select operator
Operator abstract superclass for all operators
UnaryOperator abstract superclass for all operators with a single child
Scan an operator that feeds a named relation into a query plan
Select an operator that selects certain tuples in its input, via some predicate
Project an operator that projects certain attributes from its input
BinaryOperator abstract superclass for all operator with two children
Product an operator that performs a cartesian product over its inputs
Join an operator that joins its inputs, via some predicate
Catalogue a directory and factory for named relations and their attributes
CatalogueException a failure to retrieve relations or attributes from the catalogue
CatalogueParser a utility class that reads a serialised catalogue from file
QueryParser a utility class that reads a query and builds a canonical query plan
PlanVisitor an interface that when implemented performs a depth-first plan traversal
Inspector a utility class that traverses an annotated plan and prints out the estimates
SJDB class containing main()
Test an example of the test harnesses used for marking
The SJDB class contains a main() method with skeleton code for reading catalogues and queries.
The system provides basic statistical information about the relations and attributes in the database, as below.
These are stored on the relations and attributes themselves, and not in the catalogue.
• the number of tuples in each relation
• the value count (number of distinct values) for each attribute
A sample serialised catalogue (cat.txt) and queries (q1.txt, etc) are available in sjdb/data.
4
Test Harness Notes
The file Test.java in the SJDB distribution contains an example of the test harness that I will be using to mark
your submissions. This example test harness manually constructs both plans and catalogues as follows:
package sjdb;
import java.io.*;
import java.util.ArrayList;
import sjdb.DatabaseException;
public class Test {
private Catalogue catalogue;
public Test() {
}
public static void main(String[] args) throws Exception {
Catalogue catalogue = createCatalogue();
Inspector inspector = new Inspector();
Estimator estimator = new Estimator();
Operator plan = query(catalogue);
plan.accept(estimator);
plan.accept(inspector);
Optimiser optimiser = new Optimiser(catalogue);
Operator planopt = optimiser.optimise(plan);
planopt.accept(estimator);
planopt.accept(inspector);
}
public static Catalogue createCatalogue() {
Catalogue cat = new Catalogue();
cat.createRelation("A", 100);
cat.createAttribute("A", "a1", 100);
cat.createAttribute("A", "a2", 15);
cat.createRelation("B", 150);
cat.createAttribute("B", "b1", 150);
cat.createAttribute("B", "b2", 100);
cat.createAttribute("B", "b3", 5);
return cat;
}
public static Operator query(Catalogue cat) throws Exception {
Scan a = new Scan(cat.getRelation("A"));
Scan b = new Scan(cat.getRelation("B"));
Product p1 = new Product(a, b);
Select s1 = new Select(p1, new Predicate(new Attribute("a2"), new Attribute("b3")));
ArrayList
atts = new ArrayList
();
atts.add(new Attribute("a2"));
atts.add(new Attribute("b1"));
Project plan = new Project(s1, atts);
return plan;
}
}
As can be seen in this test harness, I use the Inspector class (provided with the SJDB sources) to print out a
human-readable version of your query plans – your query plans must be able to accept this visitor without
throwing exceptions. Your estimator and optimiser need not (and should not) produce any data on stdout
(you should use the Inspector for this when testing).
Note also that you should manually construct plans that contain joins in order to test your Estimators.
Estimators and Optimisers that do not run without errors will be marked by inspection only, and will
consequently receive a reduced mark.
5
Cost Estimation
As described in lectures, the following parameters are used to estimate the size of intermediate relations:
• T(R), the number of tuples of relation R
• V(R,A), the value count for attribute A of relation R (the number of distinct values of A)
Note that, for any relation R, V(R, A) ≤ T(R) for all attributes A on R.
Scan
T(R) (the same number of tuples as in the NamedRelation being scanned)
Product
T(R × S) = T(R)T(S)
Projection
T(πA(R)) = T(R) (assume that projection does not eliminate duplicate tuples)
Selection
For predicates of the form attr=val:
T(σA=c(R)) = T(R)/V(R,A), V(σA=c(R),A) = 1
For predicates of the form attr=attr:
T(σA=B(R)) = T(R)/max(V(R,A),V(R,B)), V(σA=B(R),A) = V(σA=B(R),B) = min(V(R,A), V(R,B)
Join
T(R⨝A=BS) = T(R)T(S)/max(V(R,A),V(S,B)), V(R⨝A=BS,A) = V(R⨝A=BS,B) = min(V(R,A), V(S,B))
(assume that A is an attribute of R and B is an attribute of S)
Note that, for an attribute C of R that is not a join attribute, V(R⨝A=BS,C) = V(R,C)
(similarly for an attribute of S that is not a join attribute)
Further Reading
For further information on cost estimation, see §16.4 of Database Systems: The Complete Book
软件开发、广告设计客服
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-23:00
微信:codinghelp
热点项目
更多
cis432代做、代写python/java程...
2024-05-04
eeen3007j代写、c++程序设计代...
2024-05-04
代写data程序、代做c/c++, jav...
2024-05-04
comp2006代做、代写c++程序语言
2024-05-04
comp26020代做、java/c++设计编...
2024-05-04
csci251 advanced programming...
2024-05-03
cs 6290: high-performance co...
2024-05-03
assignment 2: executing and ...
2024-05-03
ecse427/comp310 programmin...
2024-05-03
cs 452 (fall 22): operating...
2024-05-03
comp9414 23t2 assignment 2 ...
2024-05-03
dpst1091 23t1 assignment 2 ...
2024-05-03
program代做、代写python设计编...
2024-05-03
热点标签
finm8007
comp2006
comp26020
comp1721
eeen3007j
cis432
csci251
comp5125m
com398sust
32022
mth6158
comp328
finn41615
2024
mec302
mgmt3004
mgt7158
com160
as.640.440
econ3016
finm7405
econ7021
fin600
infs4205/7205
mktg2510-
f27sb
csse2310/csse7231
rv32i
eecs 113
comp1117b
cs 412
comp 315
econ7300
comp2017
ecs 116
fit5046
com6511
comp30024
acs341
econ1020
isys3014
acc408
comp1047
csc 256
cs 6347
finm7008
comp34212
csmde21
estr2520
comp285/comp220
mds5130/iba6205
finc6010
is3s665
busi2194
125.785
iom209
msin0041
econ339
cmt218
mast10007
comp5349
ecx2953/ecx5953
bios706
comp3310
mth6150
comp30027
comp20005
eec286
busi2211
bff2401
fnce90046
visu2001
mang6554
finc6001
125785
data423-24s1
engi 1331
fint2100
(520|600).666
can202
cs 61b
mast20029
info20003
stat512
econ3208
cmpsc311
engg1340
ecmt1010
fit5216
basc0003
ee3121
acct2002
comp5313
busi2131
ise529
elec372/472
csit940/csit440
cenv6141
comp3027/comp3927
ftec5580
comp1433
msci223
mark203
en3098
eden1000
ece6483
econ4410
mats16302
cs 6476
com6521
comp222
comp3211
comp10002
csc1002
chc6186
cs 161
comp27112
comp282
swen20003
comm1190
elec9764
acfi3308
acct7101
fin6035
comp2048
geog0163
comp2013
coen 146
dts101tc
sehh2042
comp30023
comp4880/8880
cs 455
07
stat0045.
fil-30023
celen085
psyc40005
math40082
are271
comp9311
ee5311
imse2113
comp 2322
acct2102
fnd109
int102
is3s664
is6153
data4000
accfin5034
fit5212
cs536-s24
fit5225
ecos3006
mes202tc
finc5001
stat3061
csc171
cs1b
7ssmm712
bu.450.760
cs170
comp3411
swen90004
cpt206
comp5313/comp4313—large
bl5611
kxo206
comp532
elec207
kxo151
cs 2820
cpt108
math2319
dts204tc
qm222
comp2511
ccs599
infs1001
mat2355
eeee4123
25721
ifn647
pols0010
hpm 573
qbus6860
comp9417
csci 1100
stat0023
cse340
comp2003j
cs 2550
cs360
fin 3080
ierg 4080
cs6238
cit 594
finm7406
hw6
联系我们
- QQ: 9951568
© 2021
www.rj363.com
软件定制开发网!