/img/node.jpg

CMU 15-445 Lecture #01: Course Overview & Relational Model

CMU 15-445 Database Systems Lecture #01: Course Overview & Relational Model Outline Course Logistics Relational Model Relational Algebra Course overiew This course is about the design/implementation of database management systems (DBMSs) This is not a course ($\rightarrow Key\ point\ is\ the\ theory\ and\ the\ concept$) about how to use a DBMS to build applications or how to administer a DBMS.→ See CMU 95-703 (Heinz College) PROJECTS All projects will use the CMU DB Group BusTub academic DBMS.

Sorting

Data Structure Sorting QuickSort Idea $Process\ after\ dividing \rightarrow$(like MergeSort in thought) Divide the sequence into two subsequences $$ S=S_L+S_R $$ Downsizing $$ max(|S_L|,|S_R|) < n $$ Be independent of each other $$ max(S_L) \leq min(S_R) $$ After the subsequences are sorted recursively, the original sequence is ordered naturally $$ Sorted(S)=Sorted(S_L)+Sorted(S_R) $$ A trivial solution: With a single element, is itself a solution$\rightarrow Recursive\ base\newline$ Problem How to delimit subsequence?

Searching

Data Structure Searching Read Map Static Search Table Sequential Search Binary Search Indexing Search Binary Search Trees (Dynamic Search Table) Binary search tree AVL tree B-Tree Hash Table What is hashing Hash Function Collision Resolution Closed Hashing Open Hashing Analysis of Hashing Search Table Definition A set of the same type of data elements Key The value of data item in the data element. It is used to identify the

Graph

Data Structure Graph Definition: A graph G consists of two sets a finite, nonempty set of vertices V(G) a finite, possible empty set of edges E(G) G(V,E) represents a graph The number of vertices is written $|V|(n)$, and the number of edges is written $|E|(e)$ General graphs differ from trees need not have a root node no implicit parent-child relationship may be several (or no) paths from one vertex to another Definition For a Directed graph $if\ u, v\ are\ two\ vertices,then\ <u, v> is\ an\ arc(edge), u\ is\ called\ as\ tail, v\ is\ called\ head$

Dynamic Programming

Something About Dynamic Programming $Fibonacci\ By\ Dynamic\ Programming$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 /* * In this program, we will calculate the Fibonacci by dynamic programming * The definition of the Fibonacci: Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2) (n >= 2) * Fibonacci(1) = 1 and Fibonacci(0) = 0 * we can find the program is faster than the recursion's * T(n) = O(n) and S(n) = O(1) */ #include <iostream> std::size_t FibonacciByDynamicProgramming(std::size_t n) { std::size_t f{0}, g{1}; for (std::size_t i = 0; i < n; i++) { g = g + f; f = g - f; } return f; } int main() { for (std::size_t i = 0; i <= 64; i++) std::cout << "Fibonacci(" << i << ") = " << FibonacciByDynamicProgramming(i) << std::endl; return 0; } $Longest\ Common\ Subsequence\ By\ Dynamic\ Programming$ 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 /* * In this program, we will use dynamic programming to find the length * of the longest common subsequence in two arrays * T(m + n) = O(m * n) and S(m + n) = O(m * n) */ /* * Example: array1[] = {1, 2, 3, 4, 5, 6, 7} * array2[] = {2, 5, 6, 7} * we should make a matrix(n * m) and make the element in array1 and array2 in the top and left of the matrix * like this case: 1 2 3 4 5 6 7 * 2 0 0 0 0 0 0 0 * 5 0 0 0 0 0 0 0 * 6 0 0 0 0 0 0 0 * 7 0 0 0 0 0 0 0 * Then we will fill the matrix top line and leftest column * The measuring of the matrix[1, x] x -> [1, m]: * The length of the longest common subsequence in array2[0] and the array1[x - 1] * and in the same way, we can easy to understand the measuring of the matrix[x, 1] x -> [1, n]: * The length of the longest common subsequence in array1[0] and the array2[x - 1] * so after fill, the matrix: * 1 2 3 4 5 6 7 * 2 0 1 1 1 1 1 1 * 5 0 0 0 0 0 0 0 * 6 0 0 0 0 0 0 0 * 7 0 0 0 0 0 0 0 * the base elements are ok, so we will use dynamic programming * if array1[x] == array2[y],we can know that it is form the "decreasing and conquer" * so we should make matrix[y - 1, x - 1] = matrix[y - 2, x - 2] + 1 * else array1[x] !

String

Data Structure String $Structure\rightarrow list$ linked String Arrayed String General Concepts of String $Null\ String(\emptyset):Nothing\ in\ the\ string, the\ length\ is\ zero.$ $Blank(Space)string:Only\ includes\ one\ or\ more\ blanks(spaces)in\ the\ string.$ $Substring: sub-sequence\ of\ one\ string.$ ADT { ADT String {Data Object:D={ ai | ai∈CharacterSet,i=1,2,...n, n≥0 } Data Relationship:R1={ < ai-1, ai > | ai-1, ai∈D,i=2,...,n } Operation: …… } ADT String Operations { 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 StrAssign (&T, chars) //string assignment Initial:chars are character constant.