• 作者： 張玉盈; 劉博敏; 廖正煌
• 作者服務機構： 中山大學應用數學系
• 中文摘要： 在分散式系統中，查詢處理需要透過網路來傳送資料。然而，最佳化查詢處理的問題已經被證明是NP-hard。在一聯結序列中，會降低資料傳送成本的半聯結稱之為有效益的半聯結（beneficial semijoins）。有效益的半聯結包含了傳統的有益的半聯結（profitable semijoins）與有利的半聯結（gainful semijoins）；後者本身並非有益，但會因為聯結產生者的包含而變得有益。在本篇論文中，我們提出一個新的方法，以動態累積的利益（dynamic cumulative benefit）為經驗值，找出有效益的半聯結。也就是說，給一串聯結序列，我們以半聯結插入一串聯結運算中，藉以降低資料傳送成本。由我們模擬實驗的結果顯示，我們的方法可有效率的找到有效益的半聯結，而且比起有益的半聯結方法，需較少的傳輸代價。
• 英文摘要： Query processing in a distributed system requires the transmission of data between computers ina network. The problem of optimal query processing in distributed database systems has been shownto be NP-hard. Semijoins whose execution will reduce the amount of data transmission required to performa join sequence are termed beneficial semijoins for that join sequence. Beneficial semijoins includeconventional profitable semijoins and gainful semijoins that are not profitable themselves but becomebeneficial due to the inclusion of join reducers. In this paper, we propose a new strategy, based on theheuristic values of dynamic cumulative benefit, for finding beneficial semijoins. That is, given a sequenceof join operations, we interleave the sequence of join operations with semijoins to reduce the datatransmission cost. From our simulation study, we show that our strategy can efficiently find beneficialsemijoins and requires a lower data transmission cost than does the profitable semijoin approach.
• 中文關鍵字： distributed databases; heuristic algorithms; query optimization; relational dataases; semijoins
• 英文關鍵字： --