Relational Databases
D r. B i l g i n A v e n o ğ l u
Three Revolution
Three Revolution
▪ The first revolution was driven by the emergence of the electronic computer,
▪ The second revolution by the emergence of the relational database.
▪ The third revolution has resulted in an explosion of nonrelational database
alternatives driven by the demands of modern applications that require global scope
and continuous availability.
Early Database Systems
▪ The term database entered our vocabulary only in the late 1960s.
▪ Collecting/organizing data - important in the development of human civilization and technology.
▪ Books
▪ Libraries and other indexed archives
▪ The emergence of electronic computers after World War II represented the first revolution in DBs.
▪ Early digital computers were created to perform purely mathematical functions
▪ Early DBs used paper tape initially and eventually magnetic tape to store data sequentially.
▪ It was possible to “fast forward” and “rewind” through these datasets.
▪ It was not possible until the the spinning magnetic disk in the mid-1950s
▪ Direct high-speed access to individual records became possible.
▪ Direct access allowed fast access to any item within a file of any size.
The First Database Revolution
▪ Requiring every application to write its own data handling code was clearly a productivity issue:
▪ every application had to reinvent the database wheel.
▪ Allowing multiple users to concurrently access or change data without logically or physically
corrupting the data requires sophisticated coding.
▪ It became desirable to externalize database handling logic from the application in a separate code
base.
▪ Early database systems enforced both a schema and an access path.
▪ These first-generation databases ran exclusively on the mainframe computer systems of the day
▪ By the early 1970s, two major models of DBMS were competing for dominance.
▪ The network model was formalized by the CODASYL standard and implemented in databases such as IDMS,
▪ The hierarchical model provided a somewhat simpler approach as was most notably found in IBM’s IMS
Which vendor supplied the iMac owned by Employee-391?
The Second Database Revolution
▪ No single person has had more influence over database technology than Edgar Codd
▪ In the late 1960s, Codd was working at an IBM laboratory, he felt that:
▪ Existing databases were too hard to use.
▪ Existing databases lacked a theoretical foundation.
▪ Existing databases mixed logical and physical implementations.
The First Relational Databases
▪ Initial reaction to the relational model was somewhat reluctant.
▪ IBM initiated a research program to develop a prototype RDBMS in 1974, called System R.
▪ System R demonstrated that relational databases could deliver adequate performance, and it
pioneered the SQL language.
▪ Codd specified that the relational system should include a query language,
▪ but did not mandate a specific syntax.
▪ Mike Stonebraker at Berkeley started work on a database system that eventually was called INGRES.
▪ INGRES was also relational, but it used a non-SQL query language called QUEL.
▪ Larry Ellison enters our story.
▪ Ellison was familiar both with Codd’s work and with System R, and he believed that relational
databases represented the future of database technology.
▪ In 1977, Ellison founded the company that would eventually become Oracle Corporation and
which would release the first commercially successful RDBMS.
Database Wars!
▪ By the mid-’80s, the benefits of the relational database had become widely understood.
▪ During the succeeding decades many new database systems were introduced.
▪ Sybase,
▪ Microsoft SQL Server,
▪ Informix,
▪ MySQL,
▪ DB2.
▪ While each of these systems attempts to differentiate by claiming superior performance,
availability, functionality, or economy, they are virtually identical in their reliance on
three key principles:
▪ Codd’s relational model.
▪ The SQL language.
▪ The ACID transaction model.
Relational Database
• The relational model describes how a given set of data should be
presented to the user, rather than how it should be stored on disk or
in memory.
• Key concepts of the relational model include:
• Tuples, an unordered set of attribute values.
• In an actual database, a tuple corresponds to a row, and an attribute to a column value.
• A relation, which is a collection of distinct tuples and corresponds to a table.
• Constraints, which enforce consistency of the database.
• Key constraints are used to identify tuples and relationships between tuples.
• Operations on relations such as joins, projections, unions, and so on.
• These operations always return relations.
• This means that a query on a table returns data in a tabular format.
Transaction Model
• Atomic: The transaction is indivisible; either all the statements in the
transaction are applied to the database or none are.
• Consistent: The database remains in a consistent state before and
after transaction execution.
• Isolated: While multiple transactions can be executed by one or more
users simultaneously, one transaction should not see the effects of
other in-progress transactions.
• Durable: Once a transaction is saved to the database (COMMIT), its
changes are expected to persist even if there is a failure of operating
system or hardware.
Structured Data
• After the requirements have
been collected and analyzed, the
next step is to create a
conceptual schema for the
database, using a high-level
conceptual data model.
• ER model is presented:
• basic data-structuring concepts
and constraints are determined.
Structured Data
Query Language - SQL
Relationships
• Associations between entities
• Different kinds:
• Binary relationships
• Unary relationships
• Ternary relationships
15
Binary Relationships
• Simplest kind of relationship
• Relationship between two entity types
• A salesperson “sells” products or products are “sold” by salespersons
16
Cardinality
• Represents the maximum number of entities that can be involved in
a particular relationship.
• One-to-One Binary Relationship
• One-to-Many Binary Relationship
• Many-to-Many Binary Relationship
17
Cardinality
18
Modality
• The minimum number of entity occurrences that can be involved in a
relationship.
• “inner” symbol on E-R diagram (“outer” symbol is cardinality)
19
Cardinality & Modality
20
Intersection Data
• Describes the relationship between two entities.
• Used with many-to-many relationships.
• Represented on E-R diagram as an “associative entity”
21
Many-to-Many Binary Relationship with
Intersection Data
• For example, we know not only that salesperson 137
sold some of product 24013 but also how many units
of that product that salesperson sold.
22
Associative Entity
• Entities can have attributes; many-to-many relationships can have attributes.
• Many-to-many relationship may be treated similarly to entities in an E-R diagram.
• The unique identifier of the associative entity is usually the combination of the
unique identifiers of the two entities in the many-to-many relationship.
23
Unary Relationships
• Associate occurrences of an entity type with other occurrences of the
same entity type.
• Cardinality:
• One-to-One Unary Relationship
• One-to-Many Unary Relationship
• Many-to-Many Unary Relationship
24
Unary
Relationships
(cont.)
25
Ternary Relationship
• Involves three different entity types.
26
• The General Hardware
Company E-R Diagram
• Customer Employee is a
dependent entity.
27
Good Reading Bookstores
28
World Music Association
29
Lucky Rent-A-Car
30
Normalization
• Levels of conformance to the
relational model are described in
the various “normal forms.”
• Third normal form is the most
common level.
Levels of Normalization
• Levels of normalization based on the amount of redundancy in the
database.
• Various levels of normalization are:
• First Normal Form (1NF)
• Second Normal Form (2NF)
Redundancy
Number of Tables
• Third Normal Form (3NF)
Complexity
• Boyce-Codd Normal Form (BCNF)
• Fourth Normal Form (4NF)
• Fifth Normal Form (5NF)
• Domain Key Normal Form (DKNF)
Most databases should be 3NF or BCNF in order to avoid the
database anomalies.
First Normal Form (1NF)
• A table is considered to be in 1NF if all the fields contain only scalar
values (as opposed to list of values).
ISBN Title AuName AuPhone PubName PubPhone Price
0-321-32132-1 Balloon Sleepy, 321-321-1111, Small House 714-000-0000 $34.00
Snoopy, 232-234-1234,
Grumpy 665-235-6532
0-55-123456-9 Main Street Jones, 123-333-3333, Small House 714-000-0000 $22.95
Smith 654-223-3455
0-123-45678-0 Ulysses Joyce 666-666-6666 Alpha Press 999-999-9999 $34.00
1-22-233700-0 Visual Roman 444-444-4444 Big House 123-456-7890 $25.00
Basic
Author and AuPhone columns are not scalar
1NF - Decomposition
• Place all items that appear in the repeating group in a new table
• Designate a primary key for each new table produced.
• Duplicate in the new table the primary key of the table from which
the repeating group was extracted or vice versa.
ISBN AuName AuPhone
0-321-32132-1 Sleepy 321-321-1111
ISBN Title PubName PubPhone Price 0-321-32132-1 Snoopy 232-234-1234
0-321-32132-1 Balloon Small House 714-000-0000 $34.00 0-321-32132-1 Grumpy 665-235-6532
0-55-123456-9 Main Street Small House 714-000-0000 $22.95 0-55-123456-9 Jones 123-333-3333
0-123-45678-0 Ulysses Alpha Press 999-999-9999 $34.00 0-55-123456-9 Smith 654-223-3455
1-22-233700-0 Visual Big House 123-456-7890 $25.00 0-123-45678-0 Joyce 666-666-6666
Basic
1-22-233700-0 Roman 444-444-4444
Second Normal Form (2NF)
• For a table to be in 2NF, there are two requirements
• The database is in first normal form
• All nonkey attributes in the table must be functionally dependent on the
entire primary key
• Note: Remember that we are dealing with non-key attributes
Example 1 (Not 2NF) (Convert to 2NF)
Scheme → {Title, PubId, AuId, Price, AuAddress} Old Scheme → {Title, PubId, AuId, Price, AuAddress}
[Link] → {Title, PubId, AuId}
New Scheme → {Title, PubId, AuId, Price}
2.{Title, PubId, AuID} → {Price}
New Scheme → {AuId, AuAddress}
3.{AuID} → {AuAddress}
[Link] does not belong to a key
[Link] functionally depends on AuId which is
a subset of a key
Third Normal Form (3NF)
• This form dictates that all non-key attributes of a table must be
functionally dependent on a candidate key
• i.e. there can be no interdependencies among non-key attributes.
• For a table to be in 3NF, there are two requirements
• The table should be second normal form
• No attribute is transitively dependent on the primary key
Example (Not in 3NF) Example 1 (Convert to 3NF)
Scheme → {Title, PubID, PageCount, Price }
Old Scheme → {Title, PubID, PageCount, Price }
[Link] → {Title, PubId}
2.{Title, PubId} → {PageCount} New Scheme → {PageCount, Price}
3.{PageCount} → {Price} New Scheme → {Title, PubID, PageCount}
[Link] Price and PageCount depend on a key hence 2NF
[Link] {Title, PubID} → {Price} hence not in 3NF
Object-oriented Programming and the OODBMS
▪ Shortly after the client-server revolution,
▪ In traditional “procedural” programming languages, data and logic were essentially separate.
▪ Procedures would load and manipulate data within their logic, but the procedure itself did not
contain the data in any meaningful way.
▪ Object-oriented programming (OOP) merged attributes and behaviors into a single object.
▪ OOP represented a huge gain in programmer productivity, application reliability, and performance.
▪ OOP developers were frustrated by the mismatch between the object-oriented representations of their
data within their programs and the relational representation within the database.
▪ When an object was stored into or retrieved from a relational database, multiple SQL operations would be
required to convert from the object-oriented representation to the relational representation.
OODBMS
▪ Database vendors primarily Oracle, Informix, Sybase, and IBM
▪ rapidly scrambled to implement OODBMS features within their RDBMS.
▪ By the end of the decade, OODBMS systems had completely failed to gain market share.
▪ Mainstream database vendors such as Oracle and Informix had successfully
implemented many OODBMS features, but even these features were rarely used.
▪ OO programmers became resigned to the use of RDBMS systems to persist objects,
▪ The pain was somewhat alleviated by Object-Relational Mapping (ORM) frameworks
(Hibernate) that automated the most tedious aspects of the translation.
Online Transactional Processing (OLTP)
• OLTP enables the rapid, accurate data processing behind ATMs and
online banking, cash registers and e-commerce, and scores of other
services we interact with each day.
• OLTP, enables the real-time execution of large numbers of database
transactions by large numbers of people, typically over the internet.
• A database transaction is one of CRUD operations.
Characteristics of OLTP
• Process a large number of relatively simple transactions
• Enable multi-user access to the same data, while ensuring data
integrity
• Emphasize very rapid processing, with response times measured in
milliseconds
• Are available 24/7/365
Online Analytical Processing (OLAP)
• OLAP is software for performing multidimensional analysis at high speeds
on large volumes of data
• from a data warehouse, data mart, or some other unified, centralized data store.
• The OLAP cube is an array-based multidimensional database that makes it
possible to process and analyze multiple data dimensions much more
quickly and efficiently than a traditional relational database.
• OLAP cube extends the single table with additional
layers,
• each adding additional dimensions—usually the next level in
the “concept hierarchy” of the dimension.
OLTP vs. OLAP
• OLTP systems use a RDBMS • OLAP systems use a
• a large number of concurrent users, multidimensional database
• frequent queries and updates, • created from multiple relational
• supporting very fast response times, DBs,
• queries are simple one or a few • complex queries from current and
records, historical data,
• transaction and query response • queries are complex involving
times are lightning-fast, large numbers of records,
• modify data frequently, • response times are very slow,
• involve balance of read and write, • do not modify data,
• require relatively little storage space, • workloads are read-intensive,
• require frequent or concurrent • enormous data sets and typically
backups. have significant storage space,
• backed up far less frequently.
The Relational Plateau
▪ In fact, for a period of roughly 10 years (1995–2005),
▪ No significant new databases were introduced:
▪ There were already enough RDBMS systems to saturate the market
▪ No non-relational alternatives emerged.
The Third Database Revolution
▪ By 2005, Google was by far the biggest website in the world.
▪ When Google began, well established RDBMSs were inadequate to deal with the volumes
and velocity of the data confronting Google.
▪ The challenges that enterprises face with “big data” today are problems that Google first
encountered almost 20 years ago.
▪ Google had to invent new hardware and software architectures to store and process the
exponentially growing quantity of websites it needed to index.
▪ In 2003, it revealed distributed file system GFS - a foundation for its storage architecture.
▪ In 2004 it revealed details of the distributed parallel processing algorithm MapReduce
▪ In 2006, Google revealed details about its BigTable distributed structured database
▪ These concepts, together with other technologies, many of which also came from Google,
formed the basis for the Hadoop project, which matured within Yahoo! and which
experienced rapid uptake from 2007 on.
What is the problem for RDBMS?
▪ Google have an overall scale of operation and data volume way beyond that of any
other web company
▪ Websites dedicated to online e-commerce—Amazon, for example—had a need for a
transactional processing capability that could operate at massive scale.
▪ Early social networking sites such as MySpace and eventually Facebook faced similar
challenges in scaling their infrastructure from thousands to millions of users.
▪ Even the most expensive commercial RDBMS such as Oracle could not provide
sufficient scalability to meet the demands of these sites.
▪ Oracle’s scaled-out RDBMS architecture (Oracle RAC) attempted to provide a
roadmap for limitless scalability, but it was economically unattractive and never
seemed to offer the scale required at the leading edge.
Types of Databases
• Relational databases • Cloud databases
• Object-oriented databases • Multimodal databases
• Distributed databases • Document databases
• Data warehouses • Time Series databases
• NoSQL databases • In-memory databases
• Graph databases • Columnar databases
• Key-Value databases
THE END
Questions & Answers
D r. B i l g i n A v e n o ğ l u