|
Query optimization is a conventional problem in database
systems and also an important topic in distributed
database systems. As the Internet is expanding,
thenumber of databases on the Internet is growing rapidly and
query optimization indistributed database becomes more
important. In a distributed system, the communication
cost is assumed dominant. How toreduce communication cost
becomes a major problem. In this thesis, we propose anapproach
to reducing the cost for performing the chain query. This
approach firstselects one end node of the chain query
as the target node where the result of thechain query
will be generated. Staring from this node, this approach
utilizesmultiple semijoins to eliminate the
unnecessary data that does not belong to theresult from
each table in the chain query. it fully reduces the table on the
other end node in this chain. Then, from the end node where
the full reduction table resides, this approach
combines every partial table (the table that has been reduced)to
the target node in the sequential order and finishes this chain
query. This approach notonly has a low complexity but
reduces as much as possible the amount of data
transmission between each pair of succeeding nodes. To justify
our approach, we prove some theorems related to our
approachcompare with another approach that utilizes the
dynamic programming technique.From our observation, the
approach we proposed not only has better performanceon time
complexity but also reduces the communication cost.
|