[Stanford CS145]Introduction to Databases

2020.1.4 created and write week1 and JSON
2020.1.6 update on week2 relational algebra
2020.1.13 update on week3 SQL
2020.1.14 update on week4 relational design theory
2020.1.15 update on week5 querying XML
2020.1.16 update on week6 UML&indexes&transactions
2020.1.31 update on week7 constrains&triggers
2020.2.3 update on week8 view&authorization

week1

Intro to DB
Relational Model
XML (Extensible Markup Language)
- XML tutorial 1、XML tutorial 2
- well-formed XML
  - adheres to basic structural requirements
- valid XML
  - adheres to basic structural requirements and content-specific specification
  - DTD (Document Type Definition)
    - DTD tutorial
  - XSD (XML Schema)
    - XSD tutorial

week1 schedule

第一周主要讲了两种结构：relational model和xml，以及valid xml的两种语法检查器：DTD和XSD。练习题主要是XML和DTD的，要写DTD语句。总体来说还挺简单的。还没用xmllint运行过，可以试试。如果平常不使用的话这些模型和语言的话，应该遗忘得蛮快的，不过希望以后用到时pick up也快一点。

week2

json(JavaScript Object Notation)
- json tutorial
- json with python3
relational algebra
- select operator, project operator(set, eliminate duplicates, different from SQL)
- cross product(a.k.a. Cartesian product), natural join, theta join
- set(union, intersection, difference)
- rename operator
  - to unify schemas for set operators
  - for disambiguation in "self-joins"
- alternate notation
  - assignment statement
  - expression tree
    
    week2 schedule

ps:opt-rel-algebra link

unfortunately, challenge-level exercises have been closed and didn't offer a post-deadline version.

json在实习期间我跑人体姿态识别的代码时有接触过，当时对于视频的每帧、视频帧的每人、人体的关键点、关键点的info...这样的层级用json来store和解析是非常方便的。除此之外，比较新鲜的是该课程介绍了json schema，也是挺简单的。

relational algebra的语句非常有趣，尤其是natural join好神奇。我从图书馆借了数据库教材，对于关系代数的介绍非常晦涩，是密密麻麻的符号。但是stanford教授却讲得格外清楚。我有时候觉得外国人废话很多，简单的问题也要讲这么久，但实际上，人家能让我们觉得知识这么简单真的是因为人家讲得好。想要自找challenge，那就自己看教材呗。

week3

The select statement:

select A1, A2, ..., An
from R1, R2, ..., Rm
where condition
group by columns
  having condition
order by Ai asc/desc, Aj asc/desc ...

basic operator
- <, <=, >, >=, =, <>, !=
- and, or, not
- in, not in
- exists, all, any
set operator: union, intersect, except
subquery in where, select and from
null values
aggregation
- count(*), count(Ai), sum(Ai), avg(Ai), max(Ai), min(Ai)

modification statement

insert new data

insert into Table
  Values(A1, A2, ..., An)

insert into Table
  Select-Statement

delete existing data

delete from Table
where condition

updating existing data

update Table
set A1=Expr1, A2=Expr2, ...
where condition

week3 schedule

断断续续用了一周的时间才学完SQL，毕竟在学校一直跟朋友嗨，奔波回家也劳心费神的。刚到家想学习结果Apple pencil就坏了，然而我的替换笔尖留守在寝室，我悲从中来。

这一系列的学习带给我的感受是SQL是很有趣的，非常锻炼思维，做练习题写SQL语句时感到我脑海里在高速设计solution，特别愉快。SQL跟Python等语言不是很像，我觉得最特殊的地方在于，同一query你可以有N种写法，至于孰优孰劣，教授只是几笔带过，需要我们做更深的考量。而教授介绍的都是比较basic的语句，目前一些题我能想到的解答有点redundant，我寻思是因为不知道怎么用分支循环变量等结构，希望日后能继续深耕。

另一感受就是国内教材真的令我无语。relational algebra带我们入门所以会比较偏理论，好，你云里雾里跟我天花乱坠我忍了。我依旧不计前嫌辛辛苦苦把你拖回家，结果连SQL，这是一门语言诶，都写的绕来绕去，我好伤心。

week4

overview
- design 'anomalies'
  - redundancy, update anomaly, deletion anomaly
- how to design
  - design by decomposition
- properties and normal forms
  - Functional Dependencies -> Boyce-Codd Normal Form
    - e.g. SNN -> sName, same SNN always has same sName
  - Multivalued Dependencies -> Fourth Normal Form
    - e.g. SNN -> cName, SNN -> HS, given SNN has every combination of cName with HS
functional dependencies(FDs)
- class
  - trivial FD, nontrivial FD, completely nontrivial FD
- rules
  - splitting, combining, trivial dependency, transitive
- closure of attributes
  - how to find (closure of A bar) / A bar+?
    - Given relation, FDs, set of attributes A bar, to find all B such that A bar -> B.
    - solution: applying transitive and combining rules.
  - How to use closure?
    - find all keys given a set of FDs.
    - solution: consider every subset A bar of attributes with increasing size, if A bar+ =all attributes, then A bar is a key and every superset of A bar is also a key.
- specifying FDs for a relation
  - what we want is ...
- usage
  - relational design by decomposition
  - data storage - compression
  - reasoning about queries - optimization
Boyce-Codd Normal Form(BCNF)
- definition
  - Relation R with FDs is in BCNF if: for each A bar -> B, A is a key
- BCNF decomposition algorithm
  - iterative decomposition
multivalued dependencies(MVDs)
- definition
  - A bar ->> B bar, for each value of A bar, we must have every combination of B and the rest.
- class
  - trivial MVDs, nontrivial MVDs
- rule
  - FD is an MVD rule:if A bar -> B bar, A bar ->> B bar
  - intersection rule, transitive rule ...
Forth Normal Form(4NF)
- definition
  - Relation R with MVDs is in 4NF if: for each nontrivial A ->> B, A is a key
- 4NF decomposition algorithm

week4 schedule

这一周回归到理论上来，主题是设计good schema。整体思路是我希望我的schema满足一定的Norm Form，于是我先根据real world写出dependencies，从完整的schema入手，一步步地对它进行分解，直到每个relation都满足这个Norm Form。这里介绍了两种, Boyce-Codd Norm Form和Forth Norm Form,分别对应functional dependencies和multivalued dependencies。当然，分解后的结果我们定义为good，但事实上not necessarily。这些Norm Form有自己的shortcomings。

总之，这部分内容是很需要耐心琢磨和理解的。事实上，只是入了个门，如果想要对这些Norm Form有更深的掌握，如果想设计好的数据库schema，需要继续努力呀。

week5

XPath
- XPath = path expressions + conditions
- basic construct: /, //, *, @A, [c], [2]...
- built-in functions(lots of them): contains(s1, s2), name() ...
- navigation axes(13 of them): parent::, following-sibling::,descendant::, self::...

doc("bookstore.xml")/Bookstore/(Book|Magazine)[@Price<90]/Title

doc("bookstore.xml")//Book[contains(Remark, "great")]/Title

doc("bookstore.xml")/Bookstore/(Book|Magazine)[Title = following-sibling::Book/Title or preceding-sibling::Book/Title]

XQuery
- XQuery = XPath + full-featured query language
- XQuery is an expression language and each expression operates on & returns a sequence of elements.
- FLWOR expression: for $var in expr, let $var in expr, where condition, order by expr, return expr. All except return are optional. for and let can be repeated and interleaved.
- mixing queries and xml: <Result> {...query goes here...}</Result>

for $b in doc("Bookstore.xml")/Bookstore/Book
where $b/@price < 90
return $b/Title

for $b in doc("Bookstore.xml")/Bookstore/Book
where some $fn in $b/Authors/Author/First_Name
  satisfies contains($b/Title, $fn)
return <Book>
            {$b/Title}
            {for $fn in $b/Authors/Author/First_Name where contains($b/Title, $fn) returns ($fn)}
      </Book>

XSLT
- XSL=extensible stylesheet language, XSLT=XSL with transformations
- XSLT Specification is in XML


<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" indent="yes" omit-xml-declaration="yes">

<!--copy books and magazines-->
<xsl:template match="Book">
  <BookTitle><xsl:value-of select="Title" /></BookTitle>
</xsl:template>

<xsl:template match="Magazine">
  <MagazineTitle><xsl:value-of select="Title" /></MagazineTitle>
</xsl:template>

</xsl:stylesheet>


<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" indent="yes" omit-xml-declaration="yes">

<!--copy books and magazines-->
<xsl:template match="Book">
  <xsl:copy-of select="." />
</xsl:template>

<xsl:template match="Magazine">
  <xsl:copy-of select="." />
</xsl:template>

</xsl:stylesheet>

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" indent="yes" omit-xml-declaration="yes">

<!--Books costing less than $90-->
<xsl:template match="Book[@Price &lt; 90]">
  <xsl:copy-of select="." />
</xsl:template>

<!--delete text on leave nodes-->
<xsl:template match="text()" />

</xsl:stylesheet>

week5 schedule

上一次学到xml，是在week1，当时介绍了数据库的两种模型：relational model和xml。对于xml，当时学了两种语言DTD(document type definition)和XSD(XML schema definition)，用于描述和检查xml的语法。

这一周，继续学习对xml文档的查询，新了解了三种语言：XPath， XQuery和XSLT。XPath是其他规范的基础，可以方便地标识到XML文档的节点。XQuery之于XML，就像SQL之于relational model，以查询xml文档。XSLT，全称是extensible stylesheet language transformation，之于xml就像css对于html一样，用于格式化xml文档。除此之外，还有XLink， XPointer...哎呀一次就学会这么多，我真是太厉害了。

——其实并不是！做题的时候一遍遍报错然后小修小补，直到correct，很多概念都不清楚。过两天应该就更不记得了。菜鸟教程和w3school对于xml相关的技术都有详细的教程，如今只学习了简单的实例，日后有需要再做深入学习。

week6

UML(unified modeling language)
- UML is a higher-level model, can be translated into relations automatically.
- 5 concepts
  - classes -> relations
    - primary key (pk)
  - associations -> relations or fold in
    - multiplicity: many to one, one to many, many to many, one to one
    - self-associations
  - association classes -> add attributes to relation
  - subclasses
    - three ways
    - disjoint vs overlapping, complete vs incomplete
  - composition & aggregation -> relations
indexes
- primary mechanism to get improved performance on a database
- underlying data structures: balanced trees(<>=) or hash table(only=)
- An index on R.A may be useful whenever a query has a selection condition on R.A or does a join involving R.A
- downsides: extra space, index creation and index maintenance
- SQL Syntax

create index indexName on T(A1, A2,...)
drop index indexName

transaction
- motivated by 2 requirements
  - concurrent database access
  - resilience to system failures
- definition
  - A transaction is a sequence of one or more SQL operation treated as a unit
- ACID properties:
  - atomicity <- use logging
  - consistency
  - isolation <- use locking
  - durability <- use logging
- isolation levels
  - read uncommitted
  - read committed
  - repeated read
  - serializable

week6 schedule

这week学了三部分：UML，indexes和transaction，都好难理解的说。UML本质上就是一个高层的模型，用画图的方式来表示数据关系，然后可以被translated into relations。indexes便于我们使用hash和平衡树，以降低复杂度，至于怎么找indexes也是很tricky的。transaction是数据库至关重要的概念，可或许是因为locking和logging不在这门课的射程范围内，所以transaction的properties是如何实现我不甚了解，于是有点懵懵懂懂的，尤其是isolation levels。

week7

constaint
- non-null constraint
- key constraint
- referential integrity ( foreign key )
- attribute-based constraint
- tuple-based constraint
- general assertions
trigger
- SQL standard
  - structure
```
create trigger name
before|after|instead of event(insert/delete/update(of attr) on R)
[referencing-variables](e.g. referencing New Row as NR, New Table as NT)
[for each row]
when(statement)
action
```
  - no DBMS implements exact standard.
    - expressive：Postgres > SQLite >> MySQL
- features
  - trigger enforcing constraint, trigger chaining, self-triggering, cycles, conflicts, nested trigger condition...
    
    week7 schedule

随着学习的深入，我们越来越接近高阶的语法，这周讲的是constrain和trigger，一静一动。说到触发器呀，第一反应就是数电：上升沿触发，下降沿触发，分频，时钟... 后来学习硬件编程，写过计时器、红绿灯等等，对触发就更熟悉了。哎呀不禁感叹我会的太多了。

之所以需要约束和触发，是为了对数据做些简单的处理，就不必麻烦应用者了。比如，向Apply关系表中添加一条我申请stanford的信息，insert into Apply values(xxx, Monica, Stanford, null)，这时候一判断，原来是我，就直接触发，把最后一栏的decision更新成Y就好了嘛。

课程介绍了SQL standard，之所以称为标准，意思就是我先这么规定着，follow不follow看你咯。所以市面上的DBMS都多多少少跟标准不一样。这门课用跟标准比较接近的SQLite做了demo，不过既然是14年的课，不知版本迭代了多少次了，想必现在的SQLite和我学的不怎么一样QAQ。没事我们学的是思想是灵魂！

week8

view
- define views
```
  create view vname(A1, A2,...) as
  <query>
```
- query views
  - can reference view like any table
  - queries involving view rewritten to use base tables
- modify views
  - using triggers
    - using instead of trigger
  - automatic view modification
    - restrictions in SQL standard for "updatable views"
- materialized views
  - = a new table
authorization
- explanation:
  - users can only operate on data for which they are authorized.
- obtaining privileges (privs: select, select(sID), insert, delete)
```
grant privs on R to users
[with grant option]
```
- revoking privileges
  - cascade: revoke transitively, unless also granted from another source
  - restrict: disallow if cascade would revoke any other privileges
```
  revoke privs on R from users
  [cascade/ restrict]
```
- beyond simple table-level privileges: view
  
  week8 schedule

两部分：view和authorization。view相当于虚拟R，有点像编程语言定义常量，编译的时候会自动把常量的值带入。view的创建和查询都很简单，比较复杂的是修改操作，因为对view的修改牵涉到对base models的修改。最直观是用trigger，当修改view时触发trigger，来修改R。一些DBMS（demo用的SQLite）支持自动修改，但是对可修改的view有一些限制。刚刚说的其实是virtual view，也有materialized view，这时候就是真的创建table了。

authorization即不同用户对同一T有不同的权限，同一用户对不同R有不同的权限，同一用户对同一R的不同修改操作（更新、插入、删除和选择）有不同的权限。如果权限的颗粒度小，就又回到我们上边说的创建view啦。

week9

week9 schedule

week10

week10 schedule