-
Notifications
You must be signed in to change notification settings - Fork 1
/
2024-07-17-db-notes:-relational-model.html
264 lines (261 loc) · 12.2 KB
/
2024-07-17-db-notes:-relational-model.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="description" content="This is a personal note for the [[https://www.youtube.com/watch?v=uikbtpVZS2s&list=PLSE8ODhjZXjaKScG3l0nuOiDTTqpfnWFf&index=2][CMU 15-445 L1 video]] and [[https://15445.courses.cs.cmu.edu/fall2022/notes/01-introduction.pdf][CMU 15-445 L1 notes]]">
<link rel="alternate"
type="application/rss+xml"
href="https://chenyo.me/rss.xml"
title="RSS feed for https://chenyo.me">
<title>CMU 15-445 notes: Relational Model & Algebra</title>
<script type="text/javascript"
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'],['\\(','\\)']]}});
</script>
<meta name="author" content="chenyo">
<meta name="referrer" content="no-referrer">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" href="assets/style.css" type="text/css"/>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css"/>
<link rel="favicon" type="image/x-icon" href="favicon.ico">
<script src="assets/search.js"></script></head>
<body>
<div id="preamble" class="status">
<header>
<h1><a href="https://chenyo.me">Chenyo's org-static-blog</a></h1>
<nav>
<a href="https://chenyo.me">Home</a>
<a href="archive.html">Archive</a>
<a href="tags.html">Tags</a>
<div id="search-container">
<input type="text" id="search-input" placeholder="Search anywhere...">
<i class="fas fa-search search-icon"></i>
</div>
</nav>
</header></div>
<div id="content">
<div class="post-date">17 Jul 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-07-17-db-notes:-relational-model.html">CMU 15-445 notes: Relational Model & Algebra</a></h1>
<nav id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#org0988b3b">1. Terminology</a>
<ul>
<li><a href="#orgafe1e7b">1.1. Database</a></li>
<li><a href="#orgfa88ed7">1.2. Database design consideration</a></li>
<li><a href="#org7b00496">1.3. Database management system (DBMS)</a></li>
<li><a href="#org9b084c3">1.4. Data model</a></li>
<li><a href="#org7732301">1.5. Schema</a></li>
<li><a href="#orgbf932ec">1.6. Entities and Tables</a></li>
<li><a href="#org6432073">1.7. Attributes and Fields</a></li>
<li><a href="#org6101d96">1.8. Logical layer</a></li>
<li><a href="#org1ae97b4">1.9. Physical layer</a></li>
<li><a href="#orgd2d39e0">1.10. Data manipulation languages (DMLs)</a></li>
<li><a href="#orgd41205b">1.11. SQL (Structured Query Language) and relational model</a></li>
</ul>
</li>
<li><a href="#org22f6309">2. Relational model</a>
<ul>
<li><a href="#orga17f6ef">2.1. A relation</a></li>
<li><a href="#orga621154">2.2. A domain</a></li>
<li><a href="#org886107b">2.3. A tuple</a></li>
<li><a href="#orgc11a67e">2.4. Keys</a></li>
</ul>
</li>
<li><a href="#org80ab087">3. Relational Algebra</a></li>
</ul>
</div>
</nav>
<p>
This is a personal note for the <a href="https://www.youtube.com/watch?v=uikbtpVZS2s&list=PLSE8ODhjZXjaKScG3l0nuOiDTTqpfnWFf&index=2">CMU 15-445 L1 video</a> and <a href="https://15445.courses.cs.cmu.edu/fall2022/notes/01-introduction.pdf">CMU 15-445 L1 notes</a>, along with some terminology explained by <a href="https://claude.ai/chat/14f3c4ec-0ca8-495e-ac70-dd13f9eab5ea">Claude.ai</a>.
</p>
<div id="outline-container-org0988b3b" class="outline-2">
<h2 id="org0988b3b"><span class="section-number-2">1.</span> Terminology</h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-orgafe1e7b" class="outline-3">
<h3 id="orgafe1e7b"><span class="section-number-3">1.1.</span> Database</h3>
<div class="outline-text-3" id="text-1-1">
<ul class="org-ul">
<li>An organized collection of inter-related data that models some aspect of the real-world.</li>
</ul>
</div>
</div>
<div id="outline-container-orgfa88ed7" class="outline-3">
<h3 id="orgfa88ed7"><span class="section-number-3">1.2.</span> Database design consideration</h3>
<div class="outline-text-3" id="text-1-2">
<ul class="org-ul">
<li>Data integrity: protect invalid writing.</li>
<li>Implementation: query complexity, concurrent query.</li>
<li>Durability: replication, fault tolerance.</li>
</ul>
</div>
</div>
<div id="outline-container-org7b00496" class="outline-3">
<h3 id="org7b00496"><span class="section-number-3">1.3.</span> Database management system (DBMS)</h3>
<div class="outline-text-3" id="text-1-3">
<ul class="org-ul">
<li>A software that manages a database.</li>
<li>Allow the definition, creation, query, update and administration of databases.</li>
</ul>
</div>
</div>
<div id="outline-container-org9b084c3" class="outline-3">
<h3 id="org9b084c3"><span class="section-number-3">1.4.</span> Data model</h3>
<div class="outline-text-3" id="text-1-4">
<ul class="org-ul">
<li>A conceptual, high-level representation of how data is structured</li>
<li>Defines entities, attributes, relationships between entities and constraints.</li>
</ul>
</div>
</div>
<div id="outline-container-org7732301" class="outline-3">
<h3 id="org7732301"><span class="section-number-3">1.5.</span> Schema</h3>
<div class="outline-text-3" id="text-1-5">
<ul class="org-ul">
<li>A concrete implementation of a data model.</li>
<li>Defines tables, fields, data types, keys and rules.</li>
<li>Typically represented by a specific database language.</li>
</ul>
</div>
</div>
<div id="outline-container-orgbf932ec" class="outline-3">
<h3 id="orgbf932ec"><span class="section-number-3">1.6.</span> Entities and Tables</h3>
<div class="outline-text-3" id="text-1-6">
<ul class="org-ul">
<li>Entities: conceptual representations of objects in the logical data model.</li>
<li>Tables: physical storage structures in the physical data model.</li>
</ul>
</div>
</div>
<div id="outline-container-org6432073" class="outline-3">
<h3 id="org6432073"><span class="section-number-3">1.7.</span> Attributes and Fields</h3>
<div class="outline-text-3" id="text-1-7">
<ul class="org-ul">
<li>Attributes: properties of an entity.</li>
<li>Fields: columns in a database table.</li>
</ul>
</div>
</div>
<div id="outline-container-org6101d96" class="outline-3">
<h3 id="org6101d96"><span class="section-number-3">1.8.</span> Logical layer</h3>
<div class="outline-text-3" id="text-1-8">
<ul class="org-ul">
<li>The entities and attributes the database has.</li>
</ul>
</div>
</div>
<div id="outline-container-org1ae97b4" class="outline-3">
<h3 id="org1ae97b4"><span class="section-number-3">1.9.</span> Physical layer</h3>
<div class="outline-text-3" id="text-1-9">
<ul class="org-ul">
<li>How are entities and attributes stored in the database.</li>
</ul>
</div>
</div>
<div id="outline-container-orgd2d39e0" class="outline-3">
<h3 id="orgd2d39e0"><span class="section-number-3">1.10.</span> Data manipulation languages (DMLs)</h3>
<div class="outline-text-3" id="text-1-10">
<ul class="org-ul">
<li>Methods to store and retrieve information from a database.</li>
<li>Procedural: the query specifies the (high-level) strategy the DBMS should use to get the results, e.g., with relational algebra.</li>
<li>Declarative: the query specifies only what data is desired but not how to get it, e.g., with relational calculus (a formal language).</li>
</ul>
</div>
</div>
<div id="outline-container-orgd41205b" class="outline-3">
<h3 id="orgd41205b"><span class="section-number-3">1.11.</span> SQL (Structured Query Language) and relational model</h3>
<div class="outline-text-3" id="text-1-11">
<ul class="org-ul">
<li>SQL <b><b>implements</b></b> the relational model in DBMS and provides a standard way to create, manipulate and query relational databases.</li>
<li>Different SQL implementation may vary and do not strictly adhere to the relational model, e.g., allow duplicate rows.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org22f6309" class="outline-2">
<h2 id="org22f6309"><span class="section-number-2">2.</span> Relational model</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>A <b><b>data model</b></b> that defines a database <b><b>abstraction</b></b> to avoid maintenance overhead when changing the physical layer.</li>
<li>Data is stored as relations/tables.</li>
<li>Physical layer implementation and execution strategy depends on DBMS implementation.</li>
</ul>
<figure id="orgfc4ba41">
<img src="https://www.guru99.com/images/1/091318_0803_RelationalD1.png" alt="091318_0803_RelationalD1.png" align="center" width="500px">
<figcaption><span class="figure-number">Figure 1: </span>Relational model concepts (<a href="https://www.guru99.com/images/1/091318_0803_RelationalD1.png">Source</a>)</figcaption>
</figure>
</div>
<div id="outline-container-orga17f6ef" class="outline-3">
<h3 id="orga17f6ef"><span class="section-number-3">2.1.</span> A relation</h3>
<div class="outline-text-3" id="text-2-1">
<ul class="org-ul">
<li>An unordered set that contains the relationship of attributes that represent entities.</li>
<li>Relationships are unordered in the relation.</li>
</ul>
</div>
</div>
<div id="outline-container-orga621154" class="outline-3">
<h3 id="orga621154"><span class="section-number-3">2.2.</span> A domain</h3>
<div class="outline-text-3" id="text-2-2">
<ul class="org-ul">
<li>A named set of allowable values for a specific attribute.</li>
</ul>
</div>
</div>
<div id="outline-container-org886107b" class="outline-3">
<h3 id="org886107b"><span class="section-number-3">2.3.</span> A tuple</h3>
<div class="outline-text-3" id="text-2-3">
<ul class="org-ul">
<li>A set of attribute values in the relation.</li>
<li>Values can also be lists or nested data structures.</li>
<li><code>Null</code>: a special value in any attribute which means the attribute in a tuple is undefined.</li>
<li>\(n-ary\): a relation with \(n\) attributes.</li>
</ul>
</div>
</div>
<div id="outline-container-orgc11a67e" class="outline-3">
<h3 id="orgc11a67e"><span class="section-number-3">2.4.</span> Keys</h3>
<div class="outline-text-3" id="text-2-4">
<ul class="org-ul">
<li>Primary key: uniquely identifies a single tuple.</li>
<li>Foreign key: specifies that an attribute (e.g., <code>CustomerID</code>) in one relation (e.g., <code>OrderTable</code>) has to map to a tuple (e.g., the tuple with the same <code>CustomerID</code>) in another relation (e.g., <code>CustomerTable</code>).</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org80ab087" class="outline-2">
<h2 id="org80ab087"><span class="section-number-2">3.</span> Relational Algebra</h2>
<div class="outline-text-2" id="text-3">
<ul class="org-ul">
<li>A set of fundamental operations to retrieve and manipulate tuples in a relation.</li>
<li>Each operator takes in one or more relations as inputs, and outputs a new relation; operators can be chained.</li>
<li>Is a <b><b>procedure language</b></b>, meaning the execution always follow the query, even there exists more efficient way to get the same result; A better way is to be more declarative, e.g., SQL’s <code>where</code> syntax.</li>
<li><a href="https://i.sstatic.net/AHjRg.png">Common relational algebra</a>.</li>
</ul>
</div>
</div>
<div class="taglist"><a href="https://chenyo.me/tags.html">Tags</a>: <a href="https://chenyo.me/tag-study.html">study</a> <a href="https://chenyo.me/tag-database.html">database</a> <a href="https://chenyo.me/tag-cmu.html">cmu</a> </div></div>
<div id="postamble" class="status"><div id="search-results"></div>
<footer>
<div class="footer-content">
<div class="footer-left">
<p>© 2024 chenyo. Some rights reserved.</p>
<a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">
<img alt="Creative Commons License" style="border-width: 0"
src="https://i.creativecommons.org/l/by-nc/4.0/88x31.png"/>
</a>
</div>
<div class="social-links">
<a href="https://t.me/chenyo17" target="_blank" rel="noopener noreferrer">
<i class="fab fa-telegram"></i>
</a>
<a href="https://github.com/chenyo-17" target="_blank" rel="noopener noreferrer">
<i class="fab fa-github"></i>
</a>
</div>
</footer></div>
</body>
</html>