Tài liệu Công Nghệ Thông Tin

Shared memory contains shared data ● Buffer pool ● Lock table ● Log buffer ● Cached query plans (reused if same query submitted again) ■ All database processes can access shared memory ■ To ensure that no two processes are accessing the same data structure at the same time, databases systems implement mutual exclusion using either ● Operat...

37 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 613 | Lượt tải: 0

Solution: use number of hyperlinks to a site as a measure of the popularity or prestige of the site ● Count only one hyperlink from each site (why? ­ see previous slide) ● Popularity measure is for site, not for individual page  But, most hyperlinks are to root of site  Also, concept of “site” difficult to define since a URL prefix like cs....

25 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 571 | Lượt tải: 0

Data cleansing ● E.g. correct mistakes in addresses (misspellings, zip code errors) ● Merge address lists from different sources and purge duplicates ■ How to propagate updates ● Warehouse schema may be a (materialized) view of schema from data sources ■ What data to summarize ● Raw data may be too large to store on­line ● Aggregate values ...

52 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 567 | Lượt tải: 0

Database buffers are generally implemented in virtual memory in spite of some drawbacks: ● When operating system needs to evict a page that has been modified, the page is written to swap space on disk. ● When database decides to write buffer page to disk, buffer page may be in swap space, and may have to be read from swap space on disk and ou...

81 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 808 | Lượt tải: 0

Allow data items to be of various sizes and define a hierarchy of data granularities, where the small granularities are nested within larger ones ■ Can be represented graphically as a tree (but don't confuse with treelocking protocol) ■ When a transaction locks a node in the tree explicitly, it implicitly locks all the node's descendents in th...

79 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 532 | Lượt tải: 0

Instructions l i and lj of transactions Ti and Tj respectively, conflict if and only if there exists some item Q accessed by both li and lj, and at least one of these instructions wrote Q. 1. l i = read(Q), lj = read(Q). li and lj don’t conflict. 2. l i = read(Q), lj = write(Q). They conflict. 3. l i = write(Q), lj = read(Q). They conflict...

46 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 686 | Lượt tải: 0

Some query optimizers integrate heuristic selection and the generation of alternative access plans. ● Frequently used approach  heuristic rewriting of nested block structure and aggregation  followed by cost­based join­order optimization for each block ● Some optimizers (e.g. SQL Server) apply transformations to entire query and do not depe...

69 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 664 | Lượt tải: 0

Worst case estimate: b r ∗ bs + br block transfers + 2 * br seeks ● Each block in the inner relation s is read once for each block in the outer relation (instead of once for each tuple in the outer relation ■ Best case: b r + bs block transfers + 2 seeks. ■ Improvements to nested loop and block nested loop algorithms: ● In block nested­loop,...

55 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 764 | Lượt tải: 0

Since the inter­node connections are done by pointers, “logically” close blocks need not be “physically” close. ■ The non­leaf levels of the B+­tree form a hierarchy of sparse indices. ■ The B+­tree contains a relatively small number of levels  Level below root has at least 2*  n/2 values  Next level has at least 2*  n/2 *  n/2 values...

84 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 770 | Lượt tải: 0

Level 1 provides much better write performance than level 5 ● Level 5 requires at least 2 block reads and 2 block writes to write a single block, whereas Level 1 only requires 2 block writes ● Level 1 preferred for high update environments such as log disks ■ Level 1 had higher storage cost than level 5 ● disk drive capacities increasing rapid...

90 trang | Chia sẻ: huyhoang44 | Ngày: 16/03/2020 | Lượt xem: 720 | Lượt tải: 0