Consider the Purchases relation sho

Consider the Purchases relation shown in Figure 24.1. Assume that we want to find pairs of customers and items such that the customer has purchased the item more than ve times. We can express this query in SQL as follows

Think about how this query would be evaluated by a relational DBMS. Conceptually, for each (custid, item) pair, we need to check whether the sum of the qty field is greater than 5. One approach is to make a scan over the Purchases relation and maintain running sums for each (custid,item) pair. This is a feasible execution strategy as long as the number of pairs is small enough to t into main memory. If the number of pairs is larger than main memory, more expensive query evaluation plans that involve either sorting or hashing have to be used.

The query has an important property that is not exploited by the above execution strategy: Even though the Purchases relation is potentially very large and the number of (custid,item) groups can be huge, the output of the query is likely to be relatively small because of the condition in the HAVING clause. Only groups where the customer has purchased the item more than five times appear in the output. For example, there are nine groups in the query over the Purchases relation shown in Figure 24.1, although the output only contains three records. The number of groups is very large, but the answer to the query|the tip of the iceberg|is usually very small. Therefore, we call such a query an iceberg query. In general, given a relational schema R with attributes A1, A2, ..., Ak, and B and an aggregation function aggr, an iceberg query has the following structure:

Traditional query plans for this query that use sorting or hashing first compute the value of the aggregation function for all groups and then eliminate groups that do not satisfy the condition in the HAVING clause.

Comparing the query with the problem of finding frequent itemsets that we discussed in the previous section, there is a striking similarity. Consider again the Purchases relation shown in Figure 24.1 and the iceberg query from the beginning of this section. We are interested in (custid, item) pairs that have SUM (P.qty) > 5. Using a variation of the a priori property, we can argue that we only have to consider values of the custid field where the customer has purchased at least ve items overall. We can generate such items through the following query:

Similarly, we can restrict the candidate values for the item field through the following query:

If we restrict the computation of the original iceberg query to (custid, item) groups where the eld values are in the output of the previous two queries, we eliminate a large number of (custid, item) pairs a priori! Thus, a possible evaluation strategy is to first compute candidate values for the custid and item fields, and only to use combinations of these values in the evaluation of the original iceberg query. We first generate candidate field values for individual fields and only use those values that survive the a priori pruning step as expressed in the two previous queries. Thus, the iceberg query is amenable to the same bottom-up evaluation strategy that is used to find frequent itemsets. In particular, we can use the a priori property as follows: We only keep a counter for a group if each individual component of the group satisfies the condition expressed in the HAVING clause. The performance improvements of this alternative evaluation strategy over traditional query plans can be very significant in practice.

Even though the bottom-up query processing strategy eliminates many groups a priori, the number of (custid, item) pairs can still be very large in practice|even larger than main memory.

ผลลัพธ์ (ไทย) 1:

พิจารณาความสัมพันธ์ซื้อที่แสดงในรูปที่ 24.1 สมมติว่า เราต้องการหาคู่ของลูกค้าและสินค้าที่ลูกค้าได้ซื้อสินค้ามากกว่าเวลา ve เราสามารถที่แสดงแบบสอบถามนี้ใน SQL ดังนี้

คิดว่า จะประเมินแบบสอบถามนี้โดย DBMS เชิงสัมพันธ์ ทาง แนวคิดสำหรับแต่ละ (custid สินค้า) คู่ เราต้องตรวจสอบว่าผลรวมของฟิลด์ปริมาณมากกว่า 5 วิธีการหนึ่งทำให้การสแกนผ่านความสัมพันธ์ซื้อรักษาผลรวมสะสมสำหรับแต่ละ (custid สินค้า) คู่กัน นี่คือกลยุทธ์การดำเนินการเป็นไปได้ตราบใดที่จำนวนคู่คือเล็กพอที่จะไม่ลงในหน่วยความจำหลัก ถ้าจำนวนคู่ที่มีขนาดใหญ่กว่าหน่วยความจำหลัก สอบถามสักนิดมีแผนการประเมินที่เกี่ยวข้องกับการเรียงลำดับ หรือ hashing ใช้ได้

สอบถามมีลักษณะสำคัญที่ไม่สามารถตามกลยุทธ์การดำเนินการข้างต้น: แม้ว่าความสัมพันธ์การซื้อที่มีขนาดใหญ่มากอาจของ (custid สินค้า) กลุ่มสามารถเป็นใหญ่ ผลลัพธ์ของแบบสอบถามจะ มีขนาดค่อนข้างเล็กเนื่องจากเงื่อนไขสำหรับส่วนคำสั่ง having เฉพาะกลุ่มที่ลูกค้าซื้อสินค้ามากกว่าห้าครั้งปรากฏในผลลัพธ์ ตัวอย่าง ได้ 9 กลุ่มในการสอบถามผ่านความสัมพันธ์ซื้อที่แสดงไว้ในรูป 24.1 แม้ว่าผลผลิตประกอบด้วยสามระเบียนเท่านั้น จำนวนกลุ่มมีขนาดใหญ่มาก แต่คำตอบ query|the แนะนำของ iceberg|is ดีมักมาก ดังนั้น เราเรียกแบบสอบถามแบบสอบถามแบบภูเขาน้ำแข็ง ทั่วไป กำหนดแผนความสัมพันธ์ R กับแอตทริบิวต์ A1, A2,..., Ak และ B และ aggr ฟังก์ชันการรวม แบบสอบถามแบบภูเขาน้ำแข็งมีโครงสร้างต่อไปนี้:

แผนแบบสอบถามแบบสอบถามนี้ที่ใช้เรียงลำดับหรือ hashing แรกคำนวณค่าการรวมฟังก์ชันสำหรับกลุ่มทั้งหมด และกำจัดกลุ่มที่ตอบสนองเงื่อนไขในส่วนคำสั่ง HAVING จะแล้ว

สอบถามปัญหาการค้นหา itemsets บ่อยที่เรากล่าวถึงในส่วนก่อนหน้าการเปรียบเทียบ มีความคล้ายคลึงกันโดดเด่น พิจารณาความสัมพันธ์ซื้อที่แสดงไว้ในรูป 24.1 และแบบสอบถามของภูเขาน้ำแข็งจากจุดเริ่มต้นของส่วนนี้อีก เราสนใจ (custid สินค้า) คู่ที่มีผลบวก (P.qty) > 5 ใช้รูปแบบของตัว priori คุณสมบัติ เราสามารถโต้แย้งว่า เราจะต้องพิจารณาค่าของฟิลด์ custid ที่ลูกค้าได้ซื้อน้อยได้สินค้าโดยรวมได้ เราสามารถสร้างรายการดังกล่าวโดยใช้แบบสอบถามต่อไปนี้:

รับ เราสามารถจำกัดค่าตัวเลือกสำหรับสินค้าผ่านแบบสอบถามต่อไปนี้:

ถ้าเราจำกัดการคำนวณถามภูเขาน้ำแข็งเดิม (custid สินค้า) กลุ่มที่ค่า eld อยู่ในผลลัพธ์ของการสอบถามก่อนหน้านี้สอง เรากำจัดจำนวนมาก (custid สินค้า) จับคู่เป็น priori ดังนั้น กลยุทธ์การประเมินผลที่ได้คือ การคำนวณค่าตัวเลือกสำหรับฟิลด์ custid และสินค้าก่อน และเท่านั้น จะใช้ชุดของค่าเหล่านี้ในการประเมินของแบบสอบถามต้นฉบับของภูเขาน้ำแข็ง เราต้อง สร้างค่าฟิลด์ตัวเลือกสำหรับแต่ละฟิลด์ และใช้ค่าเหล่านั้นที่อยู่รอดขั้นตอนตัด priori แสดงในแบบสอบถามก่อนหน้านี้สอง เท่า ดังนั้น แบบสอบถามของภูเขาน้ำแข็งจะคล้อยตามการประเมินล่างขึ้นกลยุทธ์เดียวกันที่ใช้ค้นหาบ่อย itemsets ตก โดยเฉพาะ เราสามารถใช้ตัว priori คุณสมบัติเป็นดังนี้: เราเพียงเก็บตัวนับสำหรับกลุ่มแต่ละส่วนแต่ละกลุ่มเป็นไปตามเงื่อนไขที่ระบุในคำสั่ง having ได้ การปรับปรุงประสิทธิภาพของการประเมินทางเลือกกลยุทธ์นี้ผ่านแบบสอบถามแบบแผนสำคัญมากในทางปฏิบัติสามารถ

แม้สายล่างสอบถามประมวลผลกลยุทธ์กำจัดหลาย เป็น priori กลุ่มจำนวน (custid สินค้า) คู่ยังคงสามารถมีขนาดใหญ่มากใน practice|even ที่มีขนาดใหญ่กว่าหน่วยความจำหลักได้

ผลลัพธ์ (ไทย) 2:

พิจารณาความสัมพันธ์ซื้อแสดงในรูปที่ 24.1 สมมติว่าเราต้องการที่จะหาคู่ของลูกค้าและรายการดังกล่าวที่ลูกค้าได้ซื้อสินค้ามากขึ้นกว่าที่เคยครั้ง เราสามารถแสดงแบบสอบถามนี้ใน SQL ดังต่อไปนี้คิดเกี่ยวกับวิธีการค้นหานี้จะได้รับการประเมินโดย DBMS เชิงสัมพันธ์ แนวคิดสำหรับแต่ละ (CustID รายการ) คู่ที่เราจำเป็นต้องตรวจสอบว่าผลรวมของข้อมูลจำนวนมากกว่า 5. วิธีการหนึ่งที่จะทำให้การสแกนผ่านความสัมพันธ์การซื้อและการบำรุงรักษาจำนวนเงินที่ใช้สำหรับแต่ละ (CustID รายการ) คู่ . นี่คือกลยุทธ์การดำเนินเป็นไปได้ตราบใดที่จำนวนคู่ที่มีขนาดเล็กพอที่จะเข้าไป t หน่วยความจำหลัก หากจำนวนคู่มีขนาดใหญ่กว่าหน่วยความจำหลักมีราคาแพงกว่าแผนการประเมินผลแบบสอบถามที่เกี่ยวข้องกับการอย่างใดอย่างหนึ่งการเรียงลำดับหรือ hashing ต้องใช้แบบสอบถามที่มีคุณสมบัติที่สำคัญที่ไม่ได้ใช้ประโยชน์โดยกลยุทธ์การดำเนินการดังกล่าวข้างต้น: แม้ว่าความสัมพันธ์การสั่งซื้ออาจเป็น มีขนาดใหญ่มากและจำนวนของ (CustID รายการ) กลุ่มได้มากผลลัพธ์ของแบบสอบถามมีแนวโน้มที่จะมีขนาดค่อนข้างเล็กเนื่องจากสภาวะในการมีข้อ เฉพาะกลุ่มที่ลูกค้าได้ซื้อสินค้ามากขึ้นกว่าห้าครั้งปรากฏในผลลัพธ์ ตัวอย่างเช่นมีเก้ากลุ่มในแบบสอบถามมากกว่าความสัมพันธ์การสั่งซื้อสินค้าที่แสดงในรูปที่ 24.1 แม้ว่าการส่งออกมีสามเฉพาะระเบียน จำนวนของกลุ่มที่มีขนาดใหญ่มาก แต่คำตอบในแบบสอบถาม | ปลายของภูเขาน้ำแข็ง | มักจะเป็นขนาดเล็กมาก ดังนั้นเราจึงเรียกเช่นแบบสอบถามแบบสอบถามภูเขาน้ำแข็ง โดยทั่วไปได้รับคีอาสัมพันธ์กับคุณลักษณะ A1, A2, ... , เค, และ B และ AGGR ฟังก์ชันการรวมแบบสอบถามภูเขาน้ำแข็งมีโครงสร้างดังต่อไปนี้แผนแบบสอบถามแบบดั้งเดิมสำหรับการค้นหาที่ใช้เรียงลำดับหรือ hashing แรกคำนวณ ค่าของฟังก์ชั่นการรวมสำหรับทุกกลุ่มแล้วกำจัดกลุ่มที่ไม่ตรงตามเงื่อนไขในการมีข้อเปรียบเทียบแบบสอบถามที่มีปัญหาในการหา itemsets บ่อยครั้งที่เรากล่าวถึงในส่วนก่อนหน้านี้ที่มีความคล้ายคลึงกันที่โดดเด่น พิจารณาอีกครั้งความสัมพันธ์ซื้อแสดงในรูปที่ 24.1 และแบบสอบถามภูเขาน้ำแข็งจากจุดเริ่มต้นของส่วนนี้ เรามีความสนใจใน (CustID รายการ) คู่ที่มี SUM (P.qty)> 5. การใช้รูปแบบของสถานที่ให้บริการเบื้องต้นที่เราสามารถยืนยันว่าเราจะต้องพิจารณาค่าของสนาม CustID ที่ลูกค้าได้ซื้อได้ที่ อย่างน้อยได้โดยรวมของรายการ เราสามารถสร้างรายการดังกล่าวผ่านทางคำต่อไปนี้ในทำนองเดียวกันเราสามารถ จำกัด ค่าสมัครสำหรับฟิลด์รายการผ่านแบบสอบถามต่อไปนี้: ถ้าเรา จำกัด การคำนวณของแบบสอบถามภูเขาน้ำแข็งเดิมไปที่ (CustID รายการ) กลุ่มที่ค่าช่องที่อยู่ใน การส่งออกของก่อนหน้านี้สองคำสั่งที่เรากำจัดจำนวนมาก (CustID รายการ) คู่เบื้องต้น! ดังนั้นกลยุทธ์การประเมินผลที่เป็นไปได้คือการคำนวณค่าสมัครครั้งแรกสำหรับ CustID และรายการฟิลด์และมีเพียงที่จะใช้การรวมกันของค่าเหล่านี้ในการประเมินผลของแบบสอบถามภูเขาน้ำแข็งเดิม ครั้งแรกที่เราสร้างค่าเขตข้อมูลผู้สมัครแต่ละเขตข้อมูลและจะใช้ค่าเหล่านั้นที่อยู่รอดเบื้องต้นขั้นตอนการตัดแต่งกิ่งที่แสดงในสองคำสืบค้นก่อนหน้า ดังนั้นแบบสอบถามภูเขาน้ำแข็งคล้อยตามกลยุทธ์เดียวกันการประเมินผลจากล่างขึ้นบนที่ใช้ในการหา itemsets บ่อย โดยเฉพาะอย่างยิ่งเราสามารถใช้คุณสมบัติเบื้องต้นดังนี้: เราเพียง แต่ให้เคาน์เตอร์สำหรับกลุ่มถ้าแต่ละองค์ประกอบของแต่ละกลุ่มตามเงื่อนไขที่แสดงออกในการมีข้อ การปรับปรุงประสิทธิภาพของกลยุทธ์การประเมินผลทางเลือกแผนการแบบสอบถามแบบดั้งเดิมอาจจะมีความสำคัญมากในทางปฏิบัติแม้กลยุทธ์การประมวลผลแบบสอบถามล่างขึ้นจะช่วยลดการนิรนัยหลายกลุ่มจำนวน (CustID รายการ) คู่ยังคงสามารถมีขนาดใหญ่มากในทางปฏิบัติ | แม้มีขนาดใหญ่กว่าหน่วยความจำหลัก

ผลลัพธ์ (ไทย) 3:

พิจารณาซื้อความสัมพันธ์ที่แสดงในรูปที่ เดอะ . สมมติว่าเราต้องการค้นหาคู่ของลูกค้าและรายการต่างๆที่ลูกค้าได้ซื้อสินค้ามากกว่าได้ครั้ง เราสามารถแสดงแบบสอบถามใน SQL ดังนี้

คิดถึง แบบสอบถามนี้จะถูกประเมินโดยระบบจัดการฐานข้อมูลเชิงสัมพันธ์ . แนวคิดสำหรับแต่ละ ( custid รายการ ) คู่เราต้องตรวจสอบว่า ผลรวมของปริมาณข้อมูลมากกว่า 5 วิธีการหนึ่งคือการทำสแกนผ่านการซื้อความสัมพันธ์และรักษาวิ่งผลรวมแต่ละ ( custid รายการ ) คู่ นี้เป็นกลยุทธ์ที่เป็นไปได้การตราบใดที่ตัวเลขคู่มีขนาดเล็กพอที่จะไม่เข้าไปในหน่วยความจำหลัก ถ้าจำนวนของคู่มีขนาดใหญ่กว่าหน่วยความจำหลักสอบถามแผนการที่เกี่ยวข้องกับการประเมินราคาแพงมากขึ้นด้วยการเรียงลำดับหรือแฮชต้องใช้

สอบถามได้ที่สำคัญคุณสมบัติที่ไม่ได้ใช้ประโยชน์จากกลยุทธ์การดำเนินการข้างต้น แม้ว่าการซื้อความสัมพันธ์ซ่อนเร้นมากขนาดใหญ่และจำนวน ( custid รายการ ) กลุ่มสามารถ ขนาดใหญ่ผลลัพธ์ของแบบสอบถามมีแนวโน้มที่จะค่อนข้างเล็ก เพราะมีเงื่อนไขในข้อ เฉพาะกลุ่มที่ลูกค้าได้ซื้อสินค้ามากกว่าห้าครั้งปรากฏในการส่งออก ตัวอย่างเช่น มี 9 กลุ่ม ในการไปซื้อความสัมพันธ์ที่แสดงในรูปที่ เดอะ แม้ว่าผลผลิตที่มีเพียงสามประวัติ จำนวนของกลุ่มมีขนาดใหญ่มากแต่ตอบแบบสอบถาม | ปลายของภูเขาน้ำแข็ง | มักจะมีขนาดเล็กมาก ดังนั้นเราจึงเรียกเช่นแบบสอบถามภูเขาน้ำแข็งแบบสอบถาม โดยทั่วไป ให้สัมพันธ์กับคุณลักษณะของ R A1 , A2 , . . . , และ , และ B และการรวมฟังก์ชั่น aggr ภูเขาน้ำแข็ง , แบบสอบถามมีโครงสร้างดังต่อไปนี้ :

แผนแบบสอบถามนี้แบบสอบถามที่ใช้แบบดั้งเดิมสำหรับการเรียงลำดับหรือการ hashing แรกคำนวณค่าของฟังก์ชันการรวมทุกกลุ่มแล้ว ขจัดกลุ่มที่ไม่เป็นไปตามเงื่อนไขในการมีข้อ

เมื่อสอบถามเกี่ยวกับปัญหาของการหาเซตรายการความถี่ที่เรากล่าวถึงในส่วนก่อนหน้านี้มีความคล้ายคลึงกันโดดเด่นลองพิจารณาซื้อความสัมพันธ์แสดงในรูปรายงานและภูเขาน้ำแข็งสอบถาม จากจุดเริ่มต้นของส่วนนี้ เราสนใจ ( custid รายการ ) คู่ที่ได้ผลรวม ( p.qty ) > 5 การใช้รูปแบบของ priori ทรัพย์สิน เราก็เถียงว่า เราต้องพิจารณาค่าของเขตข้อมูล custid ที่ลูกค้าได้ซื้ออย่างน้อยได้รายการรวมเราสามารถสร้างรายการดังกล่าวผ่านแบบสอบถามต่อไปนี้ :

ฉันใด เราสามารถ จำกัด ค่าสมัครรายการเขตข้อมูลผ่านแบบสอบถามต่อไปนี้ :

ถ้าเรากัดการคำนวณของภูเขาน้ำแข็งแบบสอบถามต้นฉบับ ( custid รายการ ) กลุ่มที่ค่าละมั่งอยู่ในผลลัพธ์ของแบบสอบถามก่อนหน้านี้สอง เรากำจัด เป็นจำนวนมาก ( custid รายการ ) คู่ระหว่าง ! ดังนั้นกลยุทธ์การประเมินความเป็นไปได้เป็นครั้งแรกเพื่อคำนวณค่าผู้สมัครสำหรับ custid และรายการเขตข้อมูล และใช้ชุดของค่าเหล่านี้ในการประเมินแบบสอบถาม ๆเดิม ครั้งแรกที่เราสร้างค่าสำหรับเขตข้อมูลเขตข้อมูลผู้สมัครบุคคลและใช้เฉพาะค่าที่อยู่ระหว่างขั้นตอนการตัดแต่งกิ่งที่แสดงออกในก่อนหน้านี้สองแบบสอบถาม ดังนั้นภูเขาน้ำแข็งแบบสอบถามซูฮกกับล่างการประเมินผลกลยุทธ์ที่ใช้ในการหาเซตรายการความถี่ . โดยเฉพาะ เราสามารถใช้ระหว่างคุณสมบัติดังนี้ เราเพียง แต่ให้มีเคาน์เตอร์สำหรับแต่ละองค์ประกอบของแต่ละกลุ่ม ถ้ากลุ่มใดตรงกับเงื่อนไขในประเทศมีข้อประสิทธิภาพของการปรับปรุงนี้ทางเลือกการประเมินผลกลยุทธ์มากกว่าแผนแบบสอบถามแบบดั้งเดิมสามารถที่สำคัญมากในการฝึก

แม้ว่าจะเป็นการประมวลผลแบบสอบถามกลยุทธ์ขจัด priori หลายกลุ่ม จำนวน ( custid รายการ ) คู่ยังสามารถมีขนาดใหญ่มากในการปฏิบัติ | แม้มีขนาดใหญ่กว่าหน่วยความจำหลัก