Tài liệu, ebook Cơ Sở Dữ Liệu

 Step 9: Mapping of Union Types (Categories)  Create a new relation S for the category with a primary key.  Include any attributes of the category in S.  If superclasses have different keys:  Include a new key attribute, called surrogate key, as foreign key in each relation of the superclasses.  These foreign keys reference to the prima...

59 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1649 | Lượt tải: 0

Physical database design  The process of producing a description of the implementation of the database on secondary storage.  Describes the base relations, file organizations, and indexes design used to achieve efficient access to the data, and any associated integrity constraints and security measures.

48 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1625 | Lượt tải: 0

Exercise 3 (2)  Attic keeps track of its clients through the assigning of client numbers. They also keep track of clients’ names and addresses.  When Attic sells an item to a client, they need to keep track of the actual selling price, the date of the sale, and the sales tax.  When Attic buys an item, they wish to track the purchase cost, c...

61 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1727 | Lượt tải: 0

Problems with ER Models (2)  Fan Trap  Where a model represents a relationship between entity types, but pathway between certain entity occurrences is ambiguous.  Usually: two or more 1:N relationships fan out from the same entity.  Chasm Trap  Where a model suggests the existence of a relationship between entity types, but pathway do...

73 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1387 | Lượt tải: 0

AVL Trees as Arrays? We previously saw that: – Complete tree can be stored using an array using Q(n) memory – An arbitrary tree of n nodes requires O(2n) memory Is it possible to store an AVL tree as an array and not require exponentially more memory?

130 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1541 | Lượt tải: 2

Summary In this topic, we covered binary search trees – Described Abstract Sorted Lists – Problems using arrays and linked lists – Definition a binary search tree – Looked at the implementation of: • Empty, size, height, count • Front, back, insert, erase • Previous smaller and next larger objects

82 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1076 | Lượt tải: 2

Summary In this talk, we introduced the idea of balance – We require O(ln(n)) run times – Balance will ensure the height is (ln(n)) There are numerous definitions: – AVL trees use height balancing – Red-black trees use null-path-length balancing – BB(a) trees use weight balancing

20 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1036 | Lượt tải: 2

Applications One application of an 26-ary trees is a trie where the root represents the start of each valid word, and the different sub-trees represent next letters in valid words – Consider the words in the phrase “The fable then faded from my thoughts and memory.” – All 26 sub-trees are only shown for the root node, but all nodes have 26...

20 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 923 | Lượt tải: 1

Array storage Question: why not store any tree as an array using breadth-first traversals? – There is a significant potential for a lot of wasted memory Consider this tree with 12 nodes would require an array of size 32 – Adding a child to node K doubles the required memory

21 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1092 | Lượt tải: 3

Applications Perfect binary trees are considered to be the ideal case – The height and average depth are both (ln(n)) We will attempt to find trees which are as close as possible to perfect binary trees

20 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 978 | Lượt tải: 1