Đang chuẩn bị liên kết để tải về tài liệu:
Joe Celko s SQL for Smarties - Advanced SQL Programming P49

Joe Celko s SQL for Smarties - Advanced SQL Programming P49. In the SQL database community, Joe Celko is a well-known columnist and purveyor of valuable insights. In Joe Celko's SQL for Smarties: Advanced SQL Programming, he picks up where basic SQL training and experience leaves many database professionals and offers tips, techniques, and explanations that help readers extend their capabilities to top-tier SQL programming. Although Celko denies that the book is about database theory, he nevertheless alludes to theory often to buttress his practical points. This title is not for novices, as the author points out. Instead, its intended audience. | 452 CHAPTER 21 AGGREGATE FUNCTIONS Charles 900.00 Delta 800.00 Eddy 700.00 Fred 700.00 George 700.00 Able Baker and Charles are the three highest paid personnel but 1 000.00 900.00 and 800.00 are the three highest salaries. The highest salaries belong to Able Baker Charles and Delta a set with four elements. The way that most new SQL programmers do this in other SQL products is produce a result with an order by clause then read the first so many rows from that cursor result. In Standard SQL cursors have an order by clause but no way to return a fixed number of rows. However most SQL products have propriety syntax to clip the result set at exactly some number of rows. Oh yes did I mention that the whole table has to be sorted and that this can take some time if the table is large The best algorithm for this problem is the Partition algorithm by C. A. R. Hoare. This is the procedure in QuickSort that splits a set of values into three partitions those greater than a pivot value those less than the pivot and those values equal to the pivot. The expected run time is only 2 n operations. In practice it is a good idea to start with a pivot at or near the kth position you seek because real data tends to have some ordering already in it. If the file is already in sorted order this trick will return an answer in one pass. Here is the algorithm in Pascal. CONST list_length some large number . TYPE LIST ARRAY 1.list_length OF REAL PROCEDURE FindTopK Kth INTEGER records LIST VAR pivot left right start finish INTEGER BEGIN start 1 finish list_length WHILE start finish DO BEGIN 21.4 Extrema Functions 453 pivot records Kth left start right finish REPEAT WHILE records left pivot DO left left 1 WHILE records right pivot DO right right - 1 IF left right THEN BEGIN swap right and left elements Swap records left records right left left 1 right right - 1 END UNTIL left right IF right Kth THEN start left IF left Kth THEN finish right END the first k numbers are in positions 1 through kth