Transcript Slides from Lecture 20 - Courses - University of California, Berkeley

Future of Database Systems
University of California, Berkeley
School of Information Management
and Systems
SIMS 257: Database Management
IS 257 – Fall 2005
2005.11.21 - SLIDE 1
Lecture Outline
• Review
– Applications for Data Warehouses
– Data Mining
• Thanks again to lecture notes from Joachim Hammer of the
University of Florida
• Future of Database Systems
• Predicting the future…
• Quotes from Leon Kappelman “The future is ours” CACM,
March 2001
• Accomplishments of database research over the
past 30 years
• Next-Generation Databases and the Future
IS 257 – Fall 2005
2005.11.21 - SLIDE 2
Lecture Outline
• Review
– Applications for Data Warehouses
– Data Mining
• Thanks again to lecture notes from Joachim Hammer of the
University of Florida
• Future of Database Systems
• Predicting the future…
• Quotes from Leon Kappelman “The future is ours” CACM,
March 2001
• Accomplishments of database research over the
past 30 years
• Next-Generation Databases and the Future
IS 257 – Fall 2005
2005.11.21 - SLIDE 3
What is Decision Support?
• Technology that will help managers and
planners make decisions regarding the
organization and its operations based on
data in the Data Warehouse.
– What was the last two years of sales volume
for each product by state and city?
– What effects will a 5% price discount have on
our future income for product X?
• Increasing common term is KDD
– Knowledge Discovery in Databases
IS 257 – Fall 2005
2005.11.21 - SLIDE 4
Conventional Query Tools
• Ad-hoc queries and reports using
conventional database tools
– E.g. Access queries.
• Typical database designs include fixed
sets of reports and queries to support
them
– The end-user is often not given the ability to
do ad-hoc queries
IS 257 – Fall 2005
2005.11.21 - SLIDE 5
OLAP
• Online Line Analytical Processing
– Intended to provide multidimensional views of
the data
– I.e., the “Data Cube”
– The PivotTables in MS Excel are examples of
OLAP tools
IS 257 – Fall 2005
2005.11.21 - SLIDE 6
Data Cube
IS 257 – Fall 2005
2005.11.21 - SLIDE 7
Operations on Data Cubes
• Slicing the cube
– Extracts a 2d table from the multidimensional
data cube
– Example…
• Drill-Down
– Analyzing a given set of data at a finer level of
detail
IS 257 – Fall 2005
2005.11.21 - SLIDE 8
Star Schema
• Typical design for the derived layer of a
Data Warehouse or Mart for Decision
Support
– Particularly suited to ad-hoc queries
– Dimensional data separate from fact or event
data
• Fact tables contain factual or quantitative
data about the business
• Dimension tables hold data about the
subjects of the business
• Typically there is one Fact table with
multiple dimension tables
IS 257 – Fall 2005
2005.11.21 - SLIDE 9
Star Schema for multidimensional data
Order
OrderNo
OrderDate
…
Customer
CustomerName
CustomerAddress
City
…
Salesperson
SalespersonID
SalespersonName
City
Quota
IS 257 – Fall 2005
Fact Table
OrderNo
Salespersonid
Customerno
ProdNo
Datekey
Cityname
Quantity
TotalPrice
Product
ProdNo
ProdName
Category
Description
…
City
CityName
State
Country
…
Date
DateKey
Day
Month
Year
…
2005.11.21 - SLIDE 10
Data Mining
• Data mining is knowledge discovery rather
than question answering
– May have no pre-formulated questions
– Derived from
• Traditional Statistics
• Artificial intelligence
• Computer graphics (visualization)
IS 257 – Fall 2005
2005.11.21 - SLIDE 11
Goals of Data Mining
• Explanatory
– Explain some observed event or situation
• Why have the sales of SUVs increased in California but not
in Oregon?
• Confirmatory
– To confirm a hypothesis
• Whether 2-income families are more likely to buy family
medical coverage
• Exploratory
– To analyze data for new or unexpected relationships
• What spending patterns seem to indicate credit card fraud?
IS 257 – Fall 2005
2005.11.21 - SLIDE 12
Data Mining Applications
•
•
•
•
•
•
Profiling Populations
Analysis of business trends
Target marketing
Usage Analysis
Campaign effectiveness
Product affinity
IS 257 – Fall 2005
2005.11.21 - SLIDE 13
Data Mining Algorithms
•
•
•
•
•
Market Basket Analysis
Memory-based reasoning
Cluster detection
Link analysis
Decision trees and rule induction
algorithms
• Neural Networks
• Genetic algorithms
IS 257 – Fall 2005
2005.11.21 - SLIDE 14
Market Basket Analysis
• A type of clustering used to predict
purchase patterns.
• Identify the products likely to be purchased
in conjunction with other products
– E.g., the famous (and apocryphal) story that
men who buy diapers on Friday nights also
buy beer.
IS 257 – Fall 2005
2005.11.21 - SLIDE 15
Memory-based reasoning
• Use known instances of a model to make
predictions about unknown instances.
• Could be used for sales forcasting or fraud
detection by working from known cases to
predict new cases
IS 257 – Fall 2005
2005.11.21 - SLIDE 16
Cluster detection
• Finds data records that are similar to each
other.
• K-nearest neighbors (where K represents
the mathematical distance to the nearest
similar record) is an example of one
clustering algorithm
IS 257 – Fall 2005
2005.11.21 - SLIDE 17
Link analysis
• Follows relationships between records to
discover patterns
• Link analysis can provide the basis for
various affinity marketing programs
• Similar to Markov transition analysis
methods where probabilities are calculated
for each observed transition.
IS 257 – Fall 2005
2005.11.21 - SLIDE 18
Decision trees and rule induction algorithms
• Pulls rules out of a mass of data using
classification and regression trees (CART)
or Chi-Square automatic interaction
detectors (CHAID)
• These algorithms produce explicit rules,
which make understanding the results
simpler
IS 257 – Fall 2005
2005.11.21 - SLIDE 19
Neural Networks
• Attempt to model neurons in the brain
• Learn from a training set and then can be
used to detect patterns inherent in that
training set
• Neural nets are effective when the data is
shapeless and lacking any apparent
patterns
• May be hard to understand results
IS 257 – Fall 2005
2005.11.21 - SLIDE 20
Genetic algorithms
• Imitate natural selection processes to
evolve models using
– Selection
– Crossover
– Mutation
• Each new generation inherits traits from
the previous ones until only the most
predictive survive.
IS 257 – Fall 2005
2005.11.21 - SLIDE 21
Lecture Outline
• Review
– Applications for Data Warehouses
– Data Mining
• Thanks again to lecture notes from Joachim Hammer of the
University of Florida
• Future of Database Systems
• Predicting the future…
• Quotes from Leon Kappelman “The future is ours” CACM,
March 2001
• Accomplishments of database research over the
past 30 years
• Next-Generation Databases and the Future
IS 257 – Fall 2005
2005.11.21 - SLIDE 22
• Radio has no future, Heavier-than-air
flying machines are impossible. X-rays will
prove to be a hoax.
– William Thompson (Lord Kelvin), 1899
IS 257 – Fall 2005
2005.11.21 - SLIDE 23
• This “Telephone” has too many
shortcomings to be seriously considered
as a means of communication. The device
is inherently of no value to us.
– Western Union, Internal Memo, 1876
IS 257 – Fall 2005
2005.11.21 - SLIDE 24
• I think there is a world market for maybe
five computers
– Thomas Watson, Chair of IBM, 1943
IS 257 – Fall 2005
2005.11.21 - SLIDE 25
• The problem with television is that the
people must sit and keep their eyes glued
on the screen; the average American
family hasn’t time for it.
– New York Times, 1949
IS 257 – Fall 2005
2005.11.21 - SLIDE 26
• Where … the ENIAC is equipped with
18,000 vacuum tubes and weighs 30 tons,
computers in the future may have only
1000 vacuum tubes and weigh only 1.5
tons
– Popular Mechanics, 1949
IS 257 – Fall 2005
2005.11.21 - SLIDE 27
• There is no reason anyone would want a
computer in their home.
– Ken Olson, president and chair of Digital
Equipment Corp., 1977.
IS 257 – Fall 2005
2005.11.21 - SLIDE 28
• 640K ought to be enough for anybody.
– Attributed to Bill Gates, 1981
IS 257 – Fall 2005
2005.11.21 - SLIDE 29
• By the turn of this century, we will live in a
paperless society.
– Roger Smith, Chair of GM, 1986
IS 257 – Fall 2005
2005.11.21 - SLIDE 30
• I predict the internet… will go
spectacularly supernova and in 1996
catastrophically collapse.
– Bob Metcalfe (3-Com founder and inventor of
ethernet), 1995
IS 257 – Fall 2005
2005.11.21 - SLIDE 31
Lecture Outline
• Review
– Object-Oriented Database Development
• Future of Database Systems
• Predicting the future…
• Quotes from Leon Kappelman “The future is ours”
CACM, March 2001
• Accomplishments of database research
over the past 30 years
• Next-Generation Databases and the
Future
IS 257 – Fall 2005
2005.11.21 - SLIDE 32
Database Research
• Database research community less than 40 years old
• Has been concerned with business type applications that
have the following demands:
– Efficiency in access and modification of very large amounts of
data
– Resilience in surviving hardware and software errors without
losing data
– Access control to support simultaneous access by multiple users
and ensure consistency
– Persistence of the data over long time periods regardless of the
programs that access the data
• Research has centered on methods for designing
systems with efficiency, resilience, access control, and
persistence and on the languages and conceptual tools
to help users to access, manipulate and design
databases.
IS 257 – Fall 2005
2005.11.21 - SLIDE 33
Accomplishments of DBMS Research
• DBMS are now used in almost every
computing environment to create, organize
and maintain large collections of
information, and this is largely due to the
results of the DBMS research community’s
efforts, in particular:
– Relational DBMS
– Transaction management
– Distributed DBMS
IS 257 – Fall 2005
2005.11.21 - SLIDE 34
Relational DBMS
• The relational data model proposed by
E.F. Codd in papers (1970-1972) was a
breakthrough for simplicity in the
conceptual model of DBMS.
• However, it took much research to actually
turn RDBMS into realities.
IS 257 – Fall 2005
2005.11.21 - SLIDE 35
Relational DBMS
• During the 1970’s database researchers:
– Invented high-level relational query languages
to ease the use of the DBMS for end users
and applications programmers.
– Developed Theory and algorithms needed to
optimize queries into execution plans as
efficient and sophisticated as a programmer
might have custom designed for an earlier
DBMS
IS 257 – Fall 2005
2005.11.21 - SLIDE 36
Relational DBMS
– Developed Normalization theory to help with
database design by eliminating redundancy
– Developed clustering algorithms to improve
retrieval efficiency.
– Developed buffer management algorithms to
exploit knowledge of access patterns
– Constructed indexing methods for fast access
to single records or sets of records by values
– Implemented prototype RDBMS that formed
the core of many current commercial RDBMS
IS 257 – Fall 2005
2005.11.21 - SLIDE 37
Relational DBMS
• The result of this DBMS research was the
development of commercial RDBMS in the
1980’s
• When Codd first proposed RDBMS it was
considered theoretically elegant, but it was
assumed only toy RDBMS could ever be
implemented due to the problems and
complexities involved. Research changed
that.
IS 257 – Fall 2005
2005.11.21 - SLIDE 38
Transaction Management
• Research on transaction management has
dealt with the basic problems of
maintaining consistency in multi-user high
transaction database systems
IS 257 – Fall 2005
2005.11.21 - SLIDE 39
No Transactions : Lost updates
•
•
•
•
•
John
Read account
balance (balance =
$1000)
Transfer $100 to Mel
Debits $100
SYSTEM CRASH
Read account
balance (balance =
$900)
IS 257 – Fall 2005
Mel
• Read account
balance (balance =
$1000)
• SYSTEM CRASH
• Read account
balance (balance =
$1000)
ERROR!
2005.11.21 - SLIDE 40
No Concurrency Control: Lost updates
John
• Read account
balance (balance =
$1000)
• Read account balance
(balance = $1000)
• Withdraw $200
(balance = $800)
• Withdraw $300 (balance
= $700)
• Write account
balance (balance =
$800)
• Write account balance
(balance = $700)
Marsha
ERROR!
IS 257 – Fall 2005
2005.11.21 - SLIDE 41
Transaction Management
• To guarantee that a transaction transforms
the database from one consistent state to
another requires:
– The concurrent execution of transactions
must be such that they appear to execute in
isolation.
– System failures must not result in inconsistent
database states. Recovery is the technique
used to provide this.
IS 257 – Fall 2005
2005.11.21 - SLIDE 42
Distributed Databases
• The ability to have a single “logical
database” reside in two or more locations
on different computers, yet to keep
querying, updates and transactions all
working as if it were a single database on
a single machine
• How do you manage such a system?
IS 257 – Fall 2005
2005.11.21 - SLIDE 43
Lecture Outline
• Review
– Object-Oriented Database Development
• Future of Database Systems
• Predicting the future…
• Quotes from Leon Kappelman “The future is ours”
CACM, March 2001
• Accomplishments of database research
over the past 30 years
• “Next-Generation Databases” and the
Future
IS 257 – Fall 2005
2005.11.21 - SLIDE 44
Next Generation Database Systems
• Where are we going from here?
– Hardware is getting faster and cheaper
– DBMS technology continues to improve and
change
• OODBMS
• ORDBMS
– Bigger challenges for DBMS technology
• Medicine, design, manufacturing, digital libraries,
sciences, environment, planning, etc...
IS 257 – Fall 2005
2005.11.21 - SLIDE 45
Examples
• NASA EOSDIS
– Estimated 1016 Bytes (Exabyte)
• Computer-Aided design
• The Human Genome
• Department Store tracking
– Mining non-transactional data (e.g. Scientific
data, text data?)
• Insurance Company
– Multimedia DBMS support
IS 257 – Fall 2005
2005.11.21 - SLIDE 46
New Features
•
•
•
•
•
•
New Data types
Rule Processing
New concepts and data models
Problems of Scale
Parallelism/Grid-based DB
Tertiary Storage vs Very Large-Scale Disk
Storage
• Heterogeneous Databases
• Memory Only DBMS
IS 257 – Fall 2005
2005.11.21 - SLIDE 47
Coming to a Database Near You…
•
•
•
•
•
•
•
•
Browsibility
User-defined access methods
Security
Steering Long processes
Federated Databases
IR capabilities
XML
The Semantic Web(?)
IS 257 – Fall 2005
2005.11.21 - SLIDE 48
Some things to consider
• Bandwidth will keep increasing and getting
cheaper (and go wireless)
• Processing power will keep increasing
– Moore’s law: Number of circuits on the most
advanced semiconductors doubling every 18 months
• Memory and Storage will keep getting cheaper
(and probably smaller)
– “Storage law”: Worldwide digital data storage capacity
has doubled every 9 months for the past decade
• Put it all together and what do you have?
– “The ideal database machine would have a single
infinitely fast processor with infinite memory with
infinite bandwidth – and it would be infinitely cheap
(free)” : David DeWitt and Jim Gray, 1992
IS 257 – Fall 2005
2005.11.21 - SLIDE 49
IS 257 – Fall 2005
2005.11.21 - SLIDE 50