B561 Advanced Database

Concepts

§0 Introduction
Qin Zhang

1-1
Self introduction: my research interests

• Algorithms for Big Data:

streaming/sketching algorithms;
algorithms on distributed data;
I/O-efficient algorithms;
data structures;
• Complexity:
communication complexity.

I am a theoretician, and occasionally work on

databases and data mining

2-1
Self introduction: my research interests

• Algorithms for Big Data:

streaming/sketching algorithms;
algorithms on distributed data;
I/O-efficient algorithms;
data structures;
• Complexity:
communication complexity.

I am a theoretician, and occasionally work on

databases and data mining
You may ask: “why do you teach databases
(and probably make our lives harder)”?

2-2
Self introduction: my research interests

• Algorithms for Big Data:

streaming/sketching algorithms;
algorithms on distributed data;
I/O-efficient algorithms;
data structures;
• Complexity:
communication complexity.

I am a theoretician, and occasionally work on

databases and data mining
You may ask: “why do you teach databases
(and probably make our lives harder)”?
Hope you will not ask me again after this course :)
I am learning together with you.
2-3
What does a typical
undergrad database
course cover?

3-1
How to represent data?

How to represent the data in the computer?

Title Year Length Type Movie

Star Wars 1977 124 color
Mighty Ducks 1991 104 color
OR?
Wayne’s World 1992 95 color Sci-Fi Cartoon Comedy

Star Mighty Wayne’s

Wars, Ducks, World,
1977, 1991, 1992,
... ... ...

4-1
How to represent data?

How to represent the data in the computer?

Title Year Length Type Movie

Star Wars 1977 124 color
Mighty Ducks 1991 104 color
OR?
Wayne’s World 1992 95 color Sci-Fi Cartoon Comedy

Star Mighty Wayne’s

Wars, Ducks, World,
1977, 1991, 1992,
OR? ... ... ...

4-2
How to operate on data?

Given the data, say, a set of tables, how to answer queries?

Difficulty: Queries may depend crucially on the data in all tables.

Product
PName Price Category Manufacturer
Gizmo 19.99 Gadgets GizmoWorks
Powergizmo 29.99 Gadgets GizmoWorks
SingleTouch 149.99 Photography Canon
MultiTouch 203.99 Household Hitachi
Company
cName StockPrice Country
GizmoWorks 25 USA
Canon 65 Japan
Hitachi 15 Japan
Q: Find all products under price 200 manufactured in Japan?
5-1
How to operate on data? (cont.)
Product
PName Price Category Manufacturer
Gizmo 19.99 Gadgets GizmoWorks
Powergizmo 29.99 Gadgets GizmoWorks
SingleTouch 149.99 Photography Canon
MultiTouch 203.99 Household Hitachi
Company
CName StockPrice Country
• SQL GizmoWorks 25 USA
Canon 65 Japan
SELECT x.PName, x.Price Hitachi 15 Japan
FROM Product x, Company y
WHERE x.Manufacturer=y .CName
AND y .Country=‘Japan’
AND x.Price ≤ 200
• Relational Algebra
πPName, Price
(σPrice≤200∧Country=‘Japan’ (Product 1Manufacturer=CName Company))
6-1
How to speed up the operation?

How to speed up the operation?

Relational operations can sometimes be computed much

faster if we have precomputed a suitable data structure on
the data. This is called Indexing.

7-1
How to speed up the operation?

How to speed up the operation?

Relational operations can sometimes be computed much

faster if we have precomputed a suitable data structure on
the data. This is called Indexing.

Most notably, two kinds of index structures are essential to

database performance:
1. B-trees.
2. External hash tables.

For example, hash tables may speed up relational

operations that involve finding all occurrences in a relation
of a particular value.
7-2
How to make a good operation plan?

How to optimize the orders of the operations?

R(A, B, C , D), S(E , F , G )

Find all pairs (x, y ), x ∈ R, y ∈ S such that

(1) x.D = y .E , (2) x.A = 5 and (3) y .G = 9

σA=5∧G =9 (R 1D=E S) = σA=5 (R) 1D=E σG =9 (S)

Q: Use the LHS or RHS?

8-1
How to deal with transactions?

Transactions with the ideal ACID properties resolve the

semantic problems that arise when many concurrent users
access and change the same database.
• Atomicity (= recovery)
• Consistency
• Isolation (= concurrency control)
• Durability

9-1
How to deal with transactions?

Transactions with the ideal ACID properties resolve the

semantic problems that arise when many concurrent users
access and change the same database.
• Atomicity (= recovery)
• Consistency
• Isolation (= concurrency control)
• Durability

We will talk about how transactions are implemented using

locking and timestamp mechanisms.
This knowledge is useful in database programming, e.g., it
makes it possible in some cases to avoid (or reduce)
rollbacks of transactions, and generally make transactions
wait less for each other.
9-2
Summarize

Database =
Logic
(express the query)

System
(implementation)
Algorithm
(solve the query)

10-1
Summarize

Database =
Logic
(express the query)

System
(implementation)
Algorithm
(solve the query)

Implementation
Concept (our focus) (see B662 Database System
and Internal Design)
10-2
Summarize

Database =
Logic
(express the query)
Data Representation, Relational
Algebra, SQL (Datalog), etc. System
(implementation)
Algorithm
(solve the query)
Indexing, Query Optimization,
Concurrency Control, etc.
Implementation
Concept (our focus) (see B662 Database System
and Internal Design)
10-3
Summarize

Database =
And you need math!!
Logic
(express the query)
Data Representation, Relational
Algebra, SQL (Datalog), etc. System
(implementation)
Algorithm
(solve the query)
Indexing, Query Optimization,
Concurrency Control, etc.
Implementation
Concept (our focus) (see B662 Database System
and Internal Design)
10-4
What’s more in this course?

11-1
Advanced topics

Beyond ”SQL, Relational Algebra, Data Models,

Storage, Views and Indexing, Query Processing, Query
Optimization, Transaction Recovery, Concurrency
Control”

I will give you a taste of

1. Data Privacy (Data Suppression, Differential
Privacy)
2. External Memory a.k.a. I/O-Efficient
Algorithms (Sorting, List Ranking)
3. Streaming Algorithms (Sampling, Heavy Hitters,
Distinct Elements)
4. Data Integration / Cleaning (Deduplication)
5. MapReduce

12-1
Other important topics in databases

More but probably will not cover

1. Tree-based data models e.g., XML
2. Graph-based data models e.g., RDF
3. Spatial databases
4. Parallel and Distributed databases
partly covered in MapReduce
5. Social Networks
6. Uncertainty in databases
etc.

13-1
Tentative course plan

Part 0 : Introductions
Part 1 & 2 : Basics
– SQL, Relational Algebra
– Data Models, Storage, Indexing
Part 3 : Optimization
Part 4 : Trasactions
Part 5 : Data Privacy
Part 6 : I/O-Efficient Algorithms
Part 7 : Streaming Algorithms
Part 8 : Data Integration
Part 9 : MapReduce

14-1
Tentative course plan

Part 0 : Introductions
Part 1 & 2 : Basics
– SQL, Relational Algebra
– Data Models, Storage, Indexing
Part 3 : Optimization
Part 4 : Trasactions
Part 5 : Data Privacy
Part 6 : I/O-Efficient Algorithms
Part 7 : Streaming Algorithms
Part 8 : Data Integration
Part 9 : MapReduce

We will also have some student presentations at the end of the course

14-2
Resources

Main reference book (we will go beyond this)

• Database Systems: The Complete Book

by Hector Garcia-Molina, Jeff Ullman
and Jennifer Widom, 2nd Edition

Other reference books (undergrad textbooks ... )

• Database Management Systems
by Ramakrishnan and Guhrke, 3rd Edition

• Database System Concepts

by UllSilberschatz, Korth and Sudarshan,
6th Edition
15-1
Resources (cont.)

Other reference books (cont.):

• Readings in Database Systems “Red book”
Hellerstein and Stonebraker, eds., 4th Edition
(Will be one of our readings)

• Foundations of Databases: The Logical Level

“Alice book”
by Abiteboul, Hull, Vianu

• Concurrency Control and Recovery in Database

Systems a
by Bernstein, Hadzilacos, Goodman
a http://research.microsoft.com/en-us/people/philbe/

ccontrol.aspx
16-1
Resources (cont.)

Other reference books (cont.):

• Algorithms and Data Structures
for External Memory a
by Vitter
a http://www.ittc.ku.edu/
~jsv/Papers/Vit.IO_book.pdf
a
• Data Streams: Algorithms and Applications
by S. Muthukrishnan
a http://www.cs.rutgers.edu/ muthu/stream-1-1.ps

17-1
Resources (cont.)

Other reference books (cont.):

• Algorithms and Data Structures
for External Memory a
by Vitter
a http://www.ittc.ku.edu/
~jsv/Papers/Vit.IO_book.pdf
a
• Data Streams: Algorithms and Applications
by S. Muthukrishnan
a http://www.cs.rutgers.edu/ muthu/stream-1-1.ps

These are surely not enough, and sometimes dated. Do

you want to learn more? Reading original papers!
In fact, some of my slides are directly from VLDB toturials
17-2
Instructors

Instructor: Qin Zhang

Email: [email protected]
Office hours: Tuesday 2:45pm-3:45pm
(Lindley 215E temporary, then Lindley 430A)

Associate Instructors:
• Erfan Sadeqi Azer
• Le Liu
• Yifan Pan
• Ali Varamesh
• Prasanth Velamala
Office hours: Posted on course website

18-1
Grading

Assignments 50% : Three written assignments (each 10%).

Solutions should be typeset in LaTeX
(highly recommended) or Word.
And one reading assignment (20%)
(next slide for details)
Selected/volunteer students will give
presentations
Exams 50% : Mid-term (20%) and Final (30%).

19-1
Grading

Assignments 50% : Three written assignments (each 10%).

Solutions should be typeset in LaTeX
(highly recommended) or Word.
And one reading assignment (20%)
(next slide for details)
Selected/volunteer students will give
presentations
Exams 50% : Mid-term (20%) and Final (30%).

Use A, B, . . . for each item (assignments, exams). Final grade

will be a weighted average (according to XX%).
19-2
Reading assignment

One or a group of two read some (1 to +∞) papers/surveys/articles

and write a report (4 pages for one, and 8 pages for a group of two)
on what you think of the articles you read (not just a repeat of what
they have said).

Topics can be found in redbook

http://redbook.cs.berkeley.edu/bib4.html,
and more topics on the course website “More reading topics” (google
the papers / surveys yourself; contact AI if you cannot find it).

Selected students/groups (volunteer first) will give 25mins talks

(20mins presentation +5mins Q&A) in class. The best 1/3
individuals/groups will get a bonus in their final grades. A penalty
will be given if you agree to give a talk but cannot do at the end,
while the quality of the talk is irrelevant.

20-1
LaTeX

LaTeX: Highly recommended tools for

assignments/reports

1. Read wiki articles:

http://en.wikipedia.org/wiki/LaTeX
2. Find a good LaTeX editor.
3. Learn how to use it, e.g., read “A Not So Short
Introduction to LaTeX 2e” (Google it)

21-1
Prerequisite

Participants are expected to have a background in

algorithms and data structures. For example, have taken
1. C241 Discrete Structures for Computer Science
2. C343 Data Structures
3. B403 Introduction to Algorithm Design and Analysis
or equivalent courses, and know some basics of databases.

22-1
Frequently asked questions

Is this a course good for my job hunting in industry?

Yes, if you get to know some advanced concepts in databases, that
will certainly help.
But, this is a course on theoretical foundations of databases, but
not designed for teaching commercially available techniques
and not a programming language (SQL? PHP?) course,
and not a “hands on” course (this is not a course for professional
training; this is a graduate course in a major research university
thus should be much more advanced)

23-1
Frequently asked questions

Is this a course good for my job hunting in industry?

Yes, if you get to know some advanced concepts in databases, that
will certainly help.
But, this is a course on theoretical foundations of databases, but
not designed for teaching commercially available techniques
and not a programming language (SQL? PHP?) course,
and not a “hands on” course (this is not a course for professional
training; this is a graduate course in a major research university
thus should be much more advanced)

I haven’t taken B403 “Introduction to Algorithm Design

and Analysis” or equivalent courses. Can I take the
course? Or, will this course fit me?
Generally speaking, this is an advanced course. It will be difficult
if you do not have enough background. You can take into
23-2
consideration the touch-base exam.
The goal of this course

Open / change your

views of the world
(of databases)

24-1
The goal of this course

Open / change your

views of the world
(of databases)
Seriously, it is not just SQL programming.

Read “The relational model is dead, SQL is dead,

and I don’t feel so good myself”

24-2
Big Data

25-1
Big Data

Big data is everywhere

• : over 2.5 petabytes of sales transactions
• : an index of over 19 billion web pages
• : over 40 billion of pictures
• ...

26-1
Big Data

Big data is everywhere

• : over 2.5 petabytes of sales transactions
• : an index of over 19 billion web pages
• : over 40 billion of pictures
• ...

Magazine covers

Nature ’06 Nature ’08 CACM ’08 Economist ’10

26-2
Source and challenge

Source
• Retailer databases: Amazon, Walmart
• Logistics, financial & health data: Stock prices
• Social network: Facebook, twitter
• Pictures by mobile devices: iphone
• Internet traffic: IP addresses
• New forms of scientific data: Large Synoptic Survey Telescope

27-1
Source and challenge

Source
• Retailer databases: Amazon, Walmart
• Logistics, financial & health data: Stock prices
• Social network: Facebook, twitter
• Pictures by mobile devices: iphone
• Internet traffic: IP addresses
• New forms of scientific data: Large Synoptic Survey Telescope

Challenge
• Volume
• Velocity
• Variety (Documents, Stock records, Personal profiles,
Photographs, Audio & Video, 3D models, Location data, . . . )

27-2
Source and challenge

Source
• Retailer databases: Amazon, Walmart
• Logistics, financial & health data: Stock prices
• Social network: Facebook, twitter
• Pictures by mobile devices: iphone
• Internet traffic: IP addresses
• New forms of scientific data: Large Synoptic Survey Telescope

Challenge
• Volume
• Velocity
} The main technical challenges
• Variety (Documents, Stock records, Personal profiles,
Photographs, Audio & Video, 3D models, Location data, . . . )

27-3
What does Big Data really mean?

We don’t define Big Data in terms of TB, PB, EB, . . .

The data is too big to fit in memory. What can we do?

28-1
What does Big Data really mean?

We don’t define Big Data in terms of TB, PB, EB, . . .

The data is too big to fit in memory. What can we do?

Store them in the disk, and read/write a block of data each time

28-2
What does Big Data really mean?

We don’t define Big Data in terms of TB, PB, EB, . . .

The data is too big to fit in memory. What can we do?

Store them in the disk, and read/write a block of data each time
Processing one by one as they come,
and throw some of them away on the fly.

28-3
What does Big Data really mean?

We don’t define Big Data in terms of TB, PB, EB, . . .

The data is too big to fit in memory. What can we do?

Store them in the disk, and read/write a block of data each time
Processing one by one as they come,
and throw some of them away on the fly.

Store in multiple machines, which collaborate via communication

28-4
What does Big Data really mean?

We don’t define Big Data in terms of TB, PB, EB, . . .

The data is too big to fit in memory. What can we do?

Store them in the disk, and read/write a block of data each time
Processing one by one as they come,
and throw some of them away on the fly.

Store in multiple machines, which collaborate via communication

RAM model does not fit RAM

A processor and an infinite size memory

Probing each cell of the memory has a unit cost

CPU
28-5
Big Data:
A marketing buzzword??

29-1
Big Data:
A marketing buzzword??
A good reading topic

29-2
Popular models for big data
(see another slides)

30-1
Summary for the introduction

We have discussed topics that will be covered in this

course

We have introduced some models for big data

computation.

We have talked about the course plan and assessment.

31-1
Thank you!
Questions?
A few introductory slides are based on Rasmus
Pagh’s slides
http://www.itu.dk/people/pagh/ADBT06/

32-1