# Assessment of Urban Water Supply System Based on Query Optimization Strategy

Authors: Shibao Lu; Yizi Shang; Wei Li; Zhimin Wang
Journal: Complexity
 (2018)

---

## Abstract

As a complicated water treatment system project, an urban water supply plays a significant role in enhancing ecological civilization construction, promoting social-economic sustainable development, and improving the living environment of humans. This paper has the goal of improving water treatment efficiency and reducing water treatment cost based on comparative studies by applying two types of distributed database query optimization methods, including the system for a distributed database (SDD-1) and all reduction algorithms. The approach involves the components of partial relations and deletes the database components that are unrelated to a query, using only attributes related to a query. Thereby, the realization process becomes simple, with a small amount of transmitted data. The results show that the validity and convenience of all reduction algorithms involve the whole query process. An algorithm is independent of the chart of static characteristics and can realize all reduction states without depending on analyzing the benefits from intermediate semijoin results, which will ultimately contribute to reductions in the transmission of useless data in the network and communication costs. Implementation of the query optimization strategy can improve water treatment efficiency, reduce water treatment cost, lower water treatment expense, and implement effective communication.


---

## Body

## 1. Introduction

With the rapid development of the social economy and population, the water supply demand in a city is constantly increasing, the water supply scale becomes larger with continuously increasing complexity, and people’s requirements for the urban water supply system become increasingly high. The water supply system is an important part of a city’s infrastructure, a guarantee of social economy development, and a necessity for people’s lives. Following the increase in urban population and enhancement of the social productivity level, the water supply scale continually increases in size and complexity, and people’s requirements for the urban water supply system continue to increase. In addition, urban water supply enterprises are energy consumers, with their power consumption accounting for approximately 60% of the cost of water production. The traditional scheduling mode based on experience will cause a huge waste of energy, which is not suitable for the development requirements of modern society. If optimized scheduling is adopted, it will not only operate reasonably under the premise of satisfying the water supply requirements but will also produce large energy source savings [1].Some cities in America, Britain, Japan, and France use computers to perform online optimized scheduling and adopt different computing methods to produce a scheduling plan for the system, which has obtained huge social and economic benefits. China’s current urban water supply scheduling decisions still utilize a scheduling mode that combines manual experience scheduling with informatization, which can hardly meet the needs of users. At the same time, different departments of a water supply enterprise just work individually in different links of the whole. Thus, the enterprise’s resources are not effectively integrated, and information is not fully excavated and shared, resulting in issues that include poor management scheduling, low strain capacity, and difficult coordination among production and management departments. There is a huge contrast between this and a current informatization and networked society with rapid development. Therefore, there is an irresistible trend to use real-time monitoring systems with a high degree of informatization and networking in the urban water supply industry.This type of system plays a significant role in enhancing ecological civilization construction, promoting social-economic sustainable development, and improving the living environment of humans. Following the principles of “scientific water treatment, systematic water treatment, overall perspective, and comprehensive treatment,” we have improved the design standards, construction standards, and security standards. This involves implementing unmanned remote real-time monitoring for waste water, flooding, drainage water, water security, and water saving by relying on modern computerized communication and sensor technology. How to establish a database and early warning platform to implement scientific monitoring and an early warning system has also been investigated.A hot issue for the current database value-based query optimization is how to choose a correct sequence for the most time-consuming join operation inquiry by utilizing existing approximate information. This involves the grammatical and semantic analysis of queries, approximate model management, join cost models, and so on. At present, some researchers have conducted related research in this field. For example, Urhan and Franklin [2] explained the query optimization flow and current main technical characteristics from an overall perspective, showing that these can be improved. Wolf et al. [3] proposed the idea of extracting semantic information from a database and tried to add a semantic optimization process by utilizing the existing approximate information of a database to generate equivalent optimized statements for the original query. Fuxman and Miller [4] analyzed the database approximate characteristics, reduced the approximate management models, and provided a reasonable approximate information platform for database optimization. Green and Tannen [5] extended the approximate model to multidimensional cases and introduced a multidimensional data management technology. This technology provided more comprehensive information for queried algebraic operations. Burdick et al. [6] improved the traditional semijoin optimization algorithm SDD-1, combined caching technology and coding compression technology into semijoin operations, and reduced the cost of semijoin operations. Lu et al. [7] extended the semijoin optimization work for a database to an isomerase database and reduced the semijoin operation costs by using a heuristic rule to improve the query efficiency. In the process of query execution, some of the existing approximate information failed to be useful for the intermediate results of the query in general. Koltsidas and Viglas [8] proposed a dynamic method of changing the approximate information of a database and provided useful information for timely query execution. This made cost estimation more timely and accurate, which improved the query efficiency.Some major databases adopt query optimization technologies, which provide good results. Their process flows are roughly similar. Because the database systems that are the bases of these treatment flows are different, different query processors have their own characteristics. For example, the query optimizer of an Oracle database combines a rule-based optimization method and cost-based optimization method when executing a query. The cost module needs to estimate the cost of executing plans according to the corresponding data distributions and statistical information from a data dictionary. Therefore, histograms are introduced to describe the distribution of data values when Oracle determines the data distribution. Thus, the accuracy of cost estimation can be greatly improved [9]. Nowadays, a complicated object originating from a Berkeley database research plan, the relational database management system PostgreSQL, has greatly improved query optimization. One of the important breakthroughs is applying a heuristic optimization genetic algorithm (GA) in the field of query optimization. Open BASE adopts the B+Tree index mechanism and realizes two types of index documents: a simple type and a structural type. However, because the query optimization module does not take query rewriting into account, the query optimization efficiency cannot be fully realized. Moreover, because the Open BASE algorithm adopts borders in exhaustive search methods, there would be no satisfactory solution to the problem of multijoin query optimization [10].Query optimization is an NP problem. Even though many researchers have performed studies from many different perspectives, there is no guarantee of providing an optimal execution plan for each query. Database system development is advancing rapidly. Developers also keep running into various problems and provide an optimization solution for each database system based on specific attributes. Meanwhile, in the current query optimization research, value-based query optimization has drawn increasing attention. However, the related research is at the initial stage. This paper discusses how to realize reasonable management for an urban water supply information system using an optimization query method. In order to ensure that a good application platform is made available for urban water supply in a database system, it was found that the All Reduction Algorithm is a highly efficient query strategy by design comparison of SDD-1 and all reduction algorithms. The main query mode of all reduction algorithms is carrying out the reduction process on intermediate temporary relations in a query tree. All reduction algorithms enable each attribute to reach the conventional state by performing a reduction on the query tree in the top-down direction, which reduces useless data transmission, thereby lowering the data transmission quantity for the entire network and reducing the query error caused by the database timeliness characteristics of an urban water supply.


## 2. Content and Object of Query Optimization

### 2.1. Content of Query Optimization

Urban water supply information is an important means of improving the efficiency of an urban water supply. The main objective of database system research is to hide the data structure details as much as possible. This objective allows database systems to be applied in various fields. Moreover, the main objective of distributed database research is to hide the distributed environment details, which allows the system to be effectively applied. The relational data model can provide a database with an interface that is unrelated to the data, and the relational database language refers to the relational calculus. When implementing a data query, it is only necessary to describe the queried data without explaining how to get them. The Structured Query Language (SQL) is a general-purpose relational database language. Users can obtain data easily and quickly using the SQL to conduct a data query. However, descriptions for searching, accessing operations, and transmitting data are also required using the SQL. Thus, the corresponding research on query optimization technology is continuously being conducted.The purpose of query optimization is to minimize the overhead and total query time as much as possible during query execution and the generation of an execution strategy. The main task of the query optimizer is controlling and accelerating the process of query execution and data transmission. As shown in Figure1, the query optimizer first takes a certain expression to be queried as an input (this expression is the output of the grammatical analysis submodule for query processors). Then, the query optimizer chooses an appropriate data access strategy for the query output [11]. However, because this is a complicated problem, ideal and comprehensive query optimization is almost impossible. Many experts and scholars have conducted studies in this field, which is still in the initial stage, without satisfying outcomes. In most cases, only query optimization effects on local targets could be achieved, and even some theories were not applicable.Figure 1
Process of query optimization.Query optimization refers to choosing the minimum cost solutions in various possible schemes. In either a centralized or a distributed environment, a query optimization strategy is chosen according to the expectation measurements for various schemes. In a centralized database, a typical measurement method involves calculating the outputs, input operation times, and CPU service conditions (I/O overhead mainly refers to the overhead for collecting a data page from memory to the main memory and from memory to a buffering area). In a distributed database, the data transmission quantity should also be considered. However, there has been no common viewpoint on whether the transmission costs or local I/O costs are more important. This depends on the processing environment [12].Under the condition of a distributed database with decentralized fields, it seems that the transmission cost is more important when the bandwidth is seriously limited. However, in a local area network, the bandwidth between sites is close to a local I/O operation. With the data warehouse development and the use of larger applications in some fields, there has been a serious demand to reduce data transmission costs. Query optimization estimates various possible execution strategies based on this purpose and chooses an “optimal” solution after a comparison. Query optimization can provide a quick response to a complicated and expensive query. Distributed query optimization has been carried out for many years, and different scholars have performed a large quantity of relevant work from different application perspectives. These previous studies can be classified into two basic methods, including transmission cost reduction by reducing the data transmission quantity in a distributed query and response time reduction by adopting parallel technology [13].The structure in Figure2 shows each stage of query processing, and it can be applied to any database system, including centralized, distributed, and parallel database systems. This query starts when a user enters an SQL statement. Then, the query resolver translates it, optimizes it, and converts it into an executable query plan. A resource generator will execute this plan and obtain query results.Figure 2
Process of distributed query optimization.


### 2.2. Object of Query Optimization

The water supply system of a city is characterized by a high degree of uncertainty. Whether a centralized or distributed database system is used, the selection of a query strategy is based on the expected cost of executing a query. The only difference is that the main factors constituting the query cost are not exactly the same in these two systems. In a centralized database, a system mostly operates in a computer with a single processor. Thus, the query execution is taken as the total cost. In contrast, in a distributed database system, the communication costs for transmitting data between sites should be considered in query processing because of the distribution and redundancy of data. In addition to considering the computer costs, the transmission costs for data in a network should also be taken into consideration to determine the total cost [14].Thus, it can be seen that a distributed query process increases the content and complexity compared with a centralized query. The query costs and parallel processing degrees are quite different for different query processing methods. Although some of the technologies and methods for a centralized query are also used in distributed query processing, the problem scales and factors of the optimization are substantively different. The query optimization of a distributed database system has two different objects: minimizing the total cost and obtaining the shortest query response time. This has important significance in a distributed database system [15]. The evaluation system for an urban water supply information system has a typical distributed database structure, which is consistent with a distributed data system in terms of applications. The main purpose of a query strategy for the evaluation system of an urban water supply information system is to look for a query strategy with minimal costs.


## 2.1. Content of Query Optimization

Urban water supply information is an important means of improving the efficiency of an urban water supply. The main objective of database system research is to hide the data structure details as much as possible. This objective allows database systems to be applied in various fields. Moreover, the main objective of distributed database research is to hide the distributed environment details, which allows the system to be effectively applied. The relational data model can provide a database with an interface that is unrelated to the data, and the relational database language refers to the relational calculus. When implementing a data query, it is only necessary to describe the queried data without explaining how to get them. The Structured Query Language (SQL) is a general-purpose relational database language. Users can obtain data easily and quickly using the SQL to conduct a data query. However, descriptions for searching, accessing operations, and transmitting data are also required using the SQL. Thus, the corresponding research on query optimization technology is continuously being conducted.The purpose of query optimization is to minimize the overhead and total query time as much as possible during query execution and the generation of an execution strategy. The main task of the query optimizer is controlling and accelerating the process of query execution and data transmission. As shown in Figure1, the query optimizer first takes a certain expression to be queried as an input (this expression is the output of the grammatical analysis submodule for query processors). Then, the query optimizer chooses an appropriate data access strategy for the query output [11]. However, because this is a complicated problem, ideal and comprehensive query optimization is almost impossible. Many experts and scholars have conducted studies in this field, which is still in the initial stage, without satisfying outcomes. In most cases, only query optimization effects on local targets could be achieved, and even some theories were not applicable.Figure 1
Process of query optimization.Query optimization refers to choosing the minimum cost solutions in various possible schemes. In either a centralized or a distributed environment, a query optimization strategy is chosen according to the expectation measurements for various schemes. In a centralized database, a typical measurement method involves calculating the outputs, input operation times, and CPU service conditions (I/O overhead mainly refers to the overhead for collecting a data page from memory to the main memory and from memory to a buffering area). In a distributed database, the data transmission quantity should also be considered. However, there has been no common viewpoint on whether the transmission costs or local I/O costs are more important. This depends on the processing environment [12].Under the condition of a distributed database with decentralized fields, it seems that the transmission cost is more important when the bandwidth is seriously limited. However, in a local area network, the bandwidth between sites is close to a local I/O operation. With the data warehouse development and the use of larger applications in some fields, there has been a serious demand to reduce data transmission costs. Query optimization estimates various possible execution strategies based on this purpose and chooses an “optimal” solution after a comparison. Query optimization can provide a quick response to a complicated and expensive query. Distributed query optimization has been carried out for many years, and different scholars have performed a large quantity of relevant work from different application perspectives. These previous studies can be classified into two basic methods, including transmission cost reduction by reducing the data transmission quantity in a distributed query and response time reduction by adopting parallel technology [13].The structure in Figure2 shows each stage of query processing, and it can be applied to any database system, including centralized, distributed, and parallel database systems. This query starts when a user enters an SQL statement. Then, the query resolver translates it, optimizes it, and converts it into an executable query plan. A resource generator will execute this plan and obtain query results.Figure 2
Process of distributed query optimization.


## 2.2. Object of Query Optimization

The water supply system of a city is characterized by a high degree of uncertainty. Whether a centralized or distributed database system is used, the selection of a query strategy is based on the expected cost of executing a query. The only difference is that the main factors constituting the query cost are not exactly the same in these two systems. In a centralized database, a system mostly operates in a computer with a single processor. Thus, the query execution is taken as the total cost. In contrast, in a distributed database system, the communication costs for transmitting data between sites should be considered in query processing because of the distribution and redundancy of data. In addition to considering the computer costs, the transmission costs for data in a network should also be taken into consideration to determine the total cost [14].Thus, it can be seen that a distributed query process increases the content and complexity compared with a centralized query. The query costs and parallel processing degrees are quite different for different query processing methods. Although some of the technologies and methods for a centralized query are also used in distributed query processing, the problem scales and factors of the optimization are substantively different. The query optimization of a distributed database system has two different objects: minimizing the total cost and obtaining the shortest query response time. This has important significance in a distributed database system [15]. The evaluation system for an urban water supply information system has a typical distributed database structure, which is consistent with a distributed data system in terms of applications. The main purpose of a query strategy for the evaluation system of an urban water supply information system is to look for a query strategy with minimal costs.


## 3. Query Optimization Principle

### 3.1. SDD-1 Algorithm

The SDD-1 query strategy is based on the optimization process idea of a semijoin algorithm. The SDD-1 query strategy mainly adopts optional projection or semijoin methods to conduct data reduction operations based on the logical relationships of the query. The query objective is to minimize the cost of the executed query. The specific query process involves continuously reducing the intermediate logic relationship using a semijoin, applying the fullest semijoin operation, and concentrating the complete relation in a target station that can execute the query. In addition, in the cost calculation, because the target station is not necessarily the result station required by a query, the data transmission costs for the last station are not considered [16].The SDD-1 algorithm is a dynamic exhaustive planning algorithm. It introduces the gain concept and selects the most beneficial semijoin by comparing semijoin operations.The concept of the algorithm is as follows [17]:
(1)
Initialization: construct beneficial semijoins and store them in the BS chart; the ES chart is empty and is used to store the execution strategy.
(2)
In the first round, place the most beneficial semijoin in the BS chart, and conduct the semijoin operation. Move the operation results to the ES chart and correct the BS chart.
(3)
Repeat step 2 until the BS chart is empty; the execution strategy is then stored in the ES chart. The remaining space is where most of the data are stored. Finally, the data at each station are collected at this station for assembly.
(4)
Algorithm correction: when the site executing the last semijoin is selected as the execution site, the last semijoin can be cancelled. In addition, the data dependency shall also be corrected. For example, if R1∝R2′ is selected, and R2′ here is derived from R2∝R1, this will cause a deviation. The algorithm needs to record the data sources of intermediate results, make adjustments when data dependency occurs, and correct the execution sequence of semiconnections.Because the SDD-1 algorithm requires exhausting all of the semijoin combinations, one serious issue is the algorithm complexity. As the number of relations increases, the query graph becomes exceptionally complicated. This query planning execution with an exhaustive search will increase in an exponential order, and the time and space overheads will also increase in an exponential order, which makes it impossible for the system to bear. Moreover, the semijoin sequence obtained from the SDD-1 algorithm is not necessarily the optimum one, even though an algorithm correction shall eventually be conducted.Other SDD-1-based algorithms such as R-algorithm, A-algorithm, and other morphing algorithms adopt exhaustive search methods. When the quantity of relations is larger, the execution efficiency of these algorithms is very low. However, the SDD-1 algorithm is the most extensively used semijoin algorithm. It has many advantages when processing the local optimum and global optimum, which can be utilized. Most studies related to the semijoin algorithm are based on the SDD-1 algorithm.


### 3.2. All Reduction Algorithms

As with the traditional relational database, efficient query optimization is not only a key factor in improving the performance of a distributed real-time database but also a prerequisite basic requirement for the evaluation of an urban water supply information system. Because of its own characteristics in terms of real-timeliness, complexity, and special loads, the evaluation system platform for an urban water supply makes the traditional query optimization method unfit for extensive application in the environment of an evaluation system. For example, the dynamic programming method, which is widely applied in commercial database systems, belongs to the category of exhaustive query [18]. Though it is conducive to the determination of the optimum solution, it is inapplicable to the evaluation system for an urban water supply information system because of its complexity in terms of time and space in relation to the magnitude of the exponent. A random algorithm has the advantage of constant special loads; however, it is impossible to predict the running time for most random algorithms. These random algorithms make it difficult to meet the real-time requirements of the system. Although in most cases the complexity of a heuristic strategy is only that of the polynomial time, it generates plans at the expense of a complexity that is an order of magnitude higher than that of an exhaustive optimization algorithm. In a real-time database, the correctness of the results is related not only to the final results but also to the time it takes to generate the results. Therefore, an effort must be made to reduce the operating costs, ensuring that the query results can be generated during a given period. The goal of database optimization is to shorten the query response time and cut the query processing costs to the greatest extent possible. Nevertheless, both of these have something to do with the size of the relation. For this reason, an effort should be made to minimize the size of the intermediate results for the relation joining, and a best joining strategy might be determined. To this end, this paper has introduced a new method for query optimization specific to the characteristics of the distributed database in the evaluation system for an urban water supply [19, 20].


### 3.3. Design of All Reduction Algorithms Based on the Semijoin Concept

The reduction process is an operation when querying the database that normally involves only part of the database (partial relation) or certain components of a partial relation. The query efficiency will certainly be improved if it is possible to eliminate all the components that are irrelevant to the query and process only those components relevant to the query. Therefore, in query processing, an operation that focuses on eliminating the database components that are irrelevant to the query is called a reduction process [21]. A program that is needed for the operation to complete the reduction process is called a reducer. A query may have multiple “reduction programs.” All reduction algorithms reduce the data on the basis of the multirelation and semijoin concepts. In the course of a distributed query, immense communication costs may be incurred in the network if a direct connection strategy is employed to query and process data. This is because a large amount of data transmission occurs among the different stations of the evaluation system for an urban water supply. Although the amount of internetwork data transmission may be effectively reduced with the semijoin method, semijoined programs have their own defects; i.e., they are dependent upon the static characteristics of the database [22].The database for an urban water supply is a real-time system. Therefore, it is possible for inaccurate semijoined programs to be formed. All reduction algorithms are independent of the static characteristics of all the relations. Moreover, there is no need to search for a specific algorithm. It can be realized through relatively easy algorithms. Once query trees are generated through a relational algebra query and undergo the optimizing process, operations will be carried out to cut the intermediate relations of the query trees in line with the bottom-up query strategy in order to decrease the number of useless tuples. Then, top-down operations will be carried out to reduce the query tree with a view to bringing the entire query tree to the state of all the reductions [23].With the reduction algorithm, the precursor attributes of all the relations are first transmitted to a station for the joining operation. Then, the attributes of the joining results are returned to the original respective nodes. After this, the original relations are reduced to obtain all the effective tuples, which are finally transmitted to the destination node for joining. All reduction methods reinforce the semijoin technique. The relations in the distributed database are reduced to the maximum extent possible. The transmission costs are reduced because only tuples that are indispensable for the query results are transmitted in the process. All reduction algorithms do not depend on the static characteristics of the relations. Moreover, there is no need to maintain the static characteristics. As a result, the accuracy can be improved [24]. Not all possible halt-joined operation programs have to be searched and compared. Therefore, the communication costs can be lowered. However, the transmission costs can also be high when there is more than one joining attribute in one relation [25]. This is because more than one joining attribute, once projected, may lead to a huge amount of temporary relations. This situation is quite similar to the record numbers of the original relation.


### 3.4. Specific Steps for All Reduction Query Strategy

For the purposes of this paper, the following definitions are required for the query optimization with all reduction algorithms [26]:
(i)
CardX: the amount of tuples contained in relation X
(ii)
SizeX: the sum of the widths of all the attributes contained in relation X
(iii)
VX,a: the amount of attributes contained in relation X
(iv)
SizeX: the width of attribute X
(v)
X: the size of relation X, X=cardX×sizeX
(vi)
Effective attribute: effective relational attribute contained in the final query resultsThe main concept for the design of all reduction algorithms is as follows illustrated in Figure3 [27]. First, a specific relational algebra query is converted into query trees through the process of query optimization in the previous stage. Then, the intermediate relations in the query tree are reduced to the state of all reductions through the semijoin operation algorithm, and the target results for the query are finally obtained using the direct joining strategy.Figure 3
Flowchart of specific steps for the all reduction query strategy.The first step involves performing a semijoin reduction operation on the query trees in the direction from the leaf nodes to the root nodes.This stage is defined as the upward stage. The upward stage mainly involves performing semijoin operations on the left and right subtrees of the query tree to bring it to the state of all reductions. Specifically, projection operations are performed on the joining attributes of the leaf nodes one at a time, and the results are transmitted in parallel to the father nodes. The father nodes reinforced semijoin operation will be performed on the properties of the leaf nodes and father nodes to obtain the intermediate results. Then, the obtained intermediate results are transmitted to the upper nodes, and the projection operation is performed on the joining attributes. Finally, the reinforced semijoin operation is performed on the resultant attributes and upper nodes. In this process, the reduction operation is performed in a bottom-up direction, which moves successively from the leaf nodes to the final root nodes of the query tree [28]. Because the reduction process is performed on the attribute relations of the entire query tree, the root node contains the restrictive attributes of all the nodes. The root node will reach the all-reduction state.Through the first step, the results obtained from the root nodes that have finally undergone the reinforced semijoin process are in the all-reduction state. The projection operation is then performed on the joining attributes of the processed root nodes and each child node. The obtained results are then transferred to the lower node layers, and the cutting process is performed on these temporary intermediate relations at the nodes. For this reason, the lower nodes will also reach the all-reduction state. This process will continue successively in a top-down direction until the leaf nodes are encountered. When the downward process of semijoin cutting ends, the results of the intermediate relations of all the nodes in the query tree will reach the all-reduction state [29].The third step involves data connection and processing.After being processed in the first two steps, the query tree will reach the all-reduction state. Therefore, it is possible to perform a joining operation and the final transmission process on the query data. All reduction programs derived from all reduction algorithms will not cause the cutting of real-time data in the system when performing joining operations between nodes because they simply eliminate the useless tuples that are irrelevant to the query.Therefore, the data semijoin operation can be performed in parallel on the query tree in a bottom-up direction. Each relation after the node reduction can be directly transmitted to the destination node for query processing. Because all of the intermediate relation results obtained are arranged in an order based on the joining attributes, the merger joining method is adopted to enhance the speed of the joining execution for the entire query [30]. Through the two stages (bottom-up and top-down) of the reduction strategy based on the query tree, the restrictive attribute of the lower nodes is transmitted to the root nodes layer by layer in the upward stage. In addition, it brings the root nodes to the all-reduction state.


## 3.1. SDD-1 Algorithm

The SDD-1 query strategy is based on the optimization process idea of a semijoin algorithm. The SDD-1 query strategy mainly adopts optional projection or semijoin methods to conduct data reduction operations based on the logical relationships of the query. The query objective is to minimize the cost of the executed query. The specific query process involves continuously reducing the intermediate logic relationship using a semijoin, applying the fullest semijoin operation, and concentrating the complete relation in a target station that can execute the query. In addition, in the cost calculation, because the target station is not necessarily the result station required by a query, the data transmission costs for the last station are not considered [16].The SDD-1 algorithm is a dynamic exhaustive planning algorithm. It introduces the gain concept and selects the most beneficial semijoin by comparing semijoin operations.The concept of the algorithm is as follows [17]:
(1)
Initialization: construct beneficial semijoins and store them in the BS chart; the ES chart is empty and is used to store the execution strategy.
(2)
In the first round, place the most beneficial semijoin in the BS chart, and conduct the semijoin operation. Move the operation results to the ES chart and correct the BS chart.
(3)
Repeat step 2 until the BS chart is empty; the execution strategy is then stored in the ES chart. The remaining space is where most of the data are stored. Finally, the data at each station are collected at this station for assembly.
(4)
Algorithm correction: when the site executing the last semijoin is selected as the execution site, the last semijoin can be cancelled. In addition, the data dependency shall also be corrected. For example, if R1∝R2′ is selected, and R2′ here is derived from R2∝R1, this will cause a deviation. The algorithm needs to record the data sources of intermediate results, make adjustments when data dependency occurs, and correct the execution sequence of semiconnections.Because the SDD-1 algorithm requires exhausting all of the semijoin combinations, one serious issue is the algorithm complexity. As the number of relations increases, the query graph becomes exceptionally complicated. This query planning execution with an exhaustive search will increase in an exponential order, and the time and space overheads will also increase in an exponential order, which makes it impossible for the system to bear. Moreover, the semijoin sequence obtained from the SDD-1 algorithm is not necessarily the optimum one, even though an algorithm correction shall eventually be conducted.Other SDD-1-based algorithms such as R-algorithm, A-algorithm, and other morphing algorithms adopt exhaustive search methods. When the quantity of relations is larger, the execution efficiency of these algorithms is very low. However, the SDD-1 algorithm is the most extensively used semijoin algorithm. It has many advantages when processing the local optimum and global optimum, which can be utilized. Most studies related to the semijoin algorithm are based on the SDD-1 algorithm.


## 3.2. All Reduction Algorithms

As with the traditional relational database, efficient query optimization is not only a key factor in improving the performance of a distributed real-time database but also a prerequisite basic requirement for the evaluation of an urban water supply information system. Because of its own characteristics in terms of real-timeliness, complexity, and special loads, the evaluation system platform for an urban water supply makes the traditional query optimization method unfit for extensive application in the environment of an evaluation system. For example, the dynamic programming method, which is widely applied in commercial database systems, belongs to the category of exhaustive query [18]. Though it is conducive to the determination of the optimum solution, it is inapplicable to the evaluation system for an urban water supply information system because of its complexity in terms of time and space in relation to the magnitude of the exponent. A random algorithm has the advantage of constant special loads; however, it is impossible to predict the running time for most random algorithms. These random algorithms make it difficult to meet the real-time requirements of the system. Although in most cases the complexity of a heuristic strategy is only that of the polynomial time, it generates plans at the expense of a complexity that is an order of magnitude higher than that of an exhaustive optimization algorithm. In a real-time database, the correctness of the results is related not only to the final results but also to the time it takes to generate the results. Therefore, an effort must be made to reduce the operating costs, ensuring that the query results can be generated during a given period. The goal of database optimization is to shorten the query response time and cut the query processing costs to the greatest extent possible. Nevertheless, both of these have something to do with the size of the relation. For this reason, an effort should be made to minimize the size of the intermediate results for the relation joining, and a best joining strategy might be determined. To this end, this paper has introduced a new method for query optimization specific to the characteristics of the distributed database in the evaluation system for an urban water supply [19, 20].


## 3.3. Design of All Reduction Algorithms Based on the Semijoin Concept

The reduction process is an operation when querying the database that normally involves only part of the database (partial relation) or certain components of a partial relation. The query efficiency will certainly be improved if it is possible to eliminate all the components that are irrelevant to the query and process only those components relevant to the query. Therefore, in query processing, an operation that focuses on eliminating the database components that are irrelevant to the query is called a reduction process [21]. A program that is needed for the operation to complete the reduction process is called a reducer. A query may have multiple “reduction programs.” All reduction algorithms reduce the data on the basis of the multirelation and semijoin concepts. In the course of a distributed query, immense communication costs may be incurred in the network if a direct connection strategy is employed to query and process data. This is because a large amount of data transmission occurs among the different stations of the evaluation system for an urban water supply. Although the amount of internetwork data transmission may be effectively reduced with the semijoin method, semijoined programs have their own defects; i.e., they are dependent upon the static characteristics of the database [22].The database for an urban water supply is a real-time system. Therefore, it is possible for inaccurate semijoined programs to be formed. All reduction algorithms are independent of the static characteristics of all the relations. Moreover, there is no need to search for a specific algorithm. It can be realized through relatively easy algorithms. Once query trees are generated through a relational algebra query and undergo the optimizing process, operations will be carried out to cut the intermediate relations of the query trees in line with the bottom-up query strategy in order to decrease the number of useless tuples. Then, top-down operations will be carried out to reduce the query tree with a view to bringing the entire query tree to the state of all the reductions [23].With the reduction algorithm, the precursor attributes of all the relations are first transmitted to a station for the joining operation. Then, the attributes of the joining results are returned to the original respective nodes. After this, the original relations are reduced to obtain all the effective tuples, which are finally transmitted to the destination node for joining. All reduction methods reinforce the semijoin technique. The relations in the distributed database are reduced to the maximum extent possible. The transmission costs are reduced because only tuples that are indispensable for the query results are transmitted in the process. All reduction algorithms do not depend on the static characteristics of the relations. Moreover, there is no need to maintain the static characteristics. As a result, the accuracy can be improved [24]. Not all possible halt-joined operation programs have to be searched and compared. Therefore, the communication costs can be lowered. However, the transmission costs can also be high when there is more than one joining attribute in one relation [25]. This is because more than one joining attribute, once projected, may lead to a huge amount of temporary relations. This situation is quite similar to the record numbers of the original relation.


## 3.4. Specific Steps for All Reduction Query Strategy

For the purposes of this paper, the following definitions are required for the query optimization with all reduction algorithms [26]:
(i)
CardX: the amount of tuples contained in relation X
(ii)
SizeX: the sum of the widths of all the attributes contained in relation X
(iii)
VX,a: the amount of attributes contained in relation X
(iv)
SizeX: the width of attribute X
(v)
X: the size of relation X, X=cardX×sizeX
(vi)
Effective attribute: effective relational attribute contained in the final query resultsThe main concept for the design of all reduction algorithms is as follows illustrated in Figure3 [27]. First, a specific relational algebra query is converted into query trees through the process of query optimization in the previous stage. Then, the intermediate relations in the query tree are reduced to the state of all reductions through the semijoin operation algorithm, and the target results for the query are finally obtained using the direct joining strategy.Figure 3
Flowchart of specific steps for the all reduction query strategy.The first step involves performing a semijoin reduction operation on the query trees in the direction from the leaf nodes to the root nodes.This stage is defined as the upward stage. The upward stage mainly involves performing semijoin operations on the left and right subtrees of the query tree to bring it to the state of all reductions. Specifically, projection operations are performed on the joining attributes of the leaf nodes one at a time, and the results are transmitted in parallel to the father nodes. The father nodes reinforced semijoin operation will be performed on the properties of the leaf nodes and father nodes to obtain the intermediate results. Then, the obtained intermediate results are transmitted to the upper nodes, and the projection operation is performed on the joining attributes. Finally, the reinforced semijoin operation is performed on the resultant attributes and upper nodes. In this process, the reduction operation is performed in a bottom-up direction, which moves successively from the leaf nodes to the final root nodes of the query tree [28]. Because the reduction process is performed on the attribute relations of the entire query tree, the root node contains the restrictive attributes of all the nodes. The root node will reach the all-reduction state.Through the first step, the results obtained from the root nodes that have finally undergone the reinforced semijoin process are in the all-reduction state. The projection operation is then performed on the joining attributes of the processed root nodes and each child node. The obtained results are then transferred to the lower node layers, and the cutting process is performed on these temporary intermediate relations at the nodes. For this reason, the lower nodes will also reach the all-reduction state. This process will continue successively in a top-down direction until the leaf nodes are encountered. When the downward process of semijoin cutting ends, the results of the intermediate relations of all the nodes in the query tree will reach the all-reduction state [29].The third step involves data connection and processing.After being processed in the first two steps, the query tree will reach the all-reduction state. Therefore, it is possible to perform a joining operation and the final transmission process on the query data. All reduction programs derived from all reduction algorithms will not cause the cutting of real-time data in the system when performing joining operations between nodes because they simply eliminate the useless tuples that are irrelevant to the query.Therefore, the data semijoin operation can be performed in parallel on the query tree in a bottom-up direction. Each relation after the node reduction can be directly transmitted to the destination node for query processing. Because all of the intermediate relation results obtained are arranged in an order based on the joining attributes, the merger joining method is adopted to enhance the speed of the joining execution for the entire query [30]. Through the two stages (bottom-up and top-down) of the reduction strategy based on the query tree, the restrictive attribute of the lower nodes is transmitted to the root nodes layer by layer in the upward stage. In addition, it brings the root nodes to the all-reduction state.


## 4. Application of the Query Optimization Algorithm in the Evaluation System of Urban Water Supply

The database system for an urban water supply mainly accomplishes the tasks of reading the relevant data uploaded by the GPRS and building a real-time monitoring database, basic geographic database, user database, historical database, etc. [31]. The main purpose of water resource database query optimization is to cut down the communication costs for the entire network. With respect to the characteristics of the distributed database in the management system for an urban water supply, an optimum connection strategy can be determined using the FRD algorithm. It has also been demonstrated that the communication costs and response time can be effectively decreased with this algorithm.For queries into the information in the three stations of the evaluation database for an urban water supply, the distribution of these three stations is as shown in Figure4.Figure 4
Each site map in the distributed database.First, a chart of static characteristics is generated with respect to all the semijoined programs associated with the query. A chart of static characteristics is shown in Table1.Table 1
Static characteristics table.
Attribute
Selectance
Size
G.GNO
0.3
120
E.GNO
0.8
400
E.JNO
1
200
J.GNO
0.4
200According to the chart of static characteristics, all the semijoined programs associated with the query execution between the three stations are listed in Table2.Table 2
Query graph for semijoin program.
Relation
Card
Size
G
30
1500
E
100
3000
J
50
2000The process that adopts the SDD-1 algorithm is as follows [32]:
(1)
Assess all the semijoined programs that exist in the query graph.
(2)
Retain the programs with the maximum benefits in the semijoins. Then, update the chart of static characteristics, and assess the benefits of the semijoined programs that existed in the revised query graph.
(3)
Repeat step (2) until no more semijoined programs exist in the chart of static characteristics. The last station that executes the joining operation is the station with the lowest communication costs, as Table3 shows.Table 3
SDD-1 algorithm search strategy.
Query strategy
Semijoin program
Overhead
E.ENO⟶station 2
G∝ENOE
120
J.JNO⟶station 2
G∝JNOJ
200
GENO⟶station 1
E∝ENOG
120
E⟶station 3
1200
G station 3
360
Total overhead
2000The SDD-1 algorithm supports a relational data model. The global relation can be segmented into two steps (horizontal segmentation first, then vertical segmentation), which makes it possible to store each segment in a redundant form.SDD-1 can provide transparency for segmented storage (the user does not know the distribution of the different segments). It realizes the control of relations through the use of the data language, i.e., an advanced processing language applicable to computer data. The architecture of the SDD-1 algorithm is based on three relatively independent virtual machines: the data module, transaction processing module, and reliable network. This architecture allows the division of the problem of distributed database management into three systems, which limit their impact on each other.One major problem with the SDD-1 algorithm is its complexity. The system cannot sustain the burgeoning costs when a query or search is being made with a huge number of tuples. Of course, for this kind of search mode, the best path for making queries might be found. For this purpose, we have made some improvements to decrease the time complexity. An artificial intelligence algorithm could be introduced to the SDD-1 algorithm. When the number of tuples is not as large, the concept of theA′ algorithm could also be used for query optimization, on the basis of which the optimum method for path searching and optimization might also be discovered. However, when the number of tuples is very large, the previous methods will still be used [33].Using all reduction algorithms [34–36]:
(1)
Complicated query problems are converted into query trees, and after relational algebra optimization, pretreated query trees are generated.
(2)
As shown by the arrow in Figure5, all of the left and right subtrees are traversed in a bottom-up direction. A semijoin process is performed on the query trees in a bottom-up direction from the leaf nodes to the root nodes. When the root nodes are finally encountered, the full-reduction state will thus be obtained (left subtree: A∝e=fE⟶E′; right subtree: J∝g=hYJ∝i=jZ⟶J′;rootnode:G∝a=bE′G∝c=dJ′⟶G′; then, G′ has reached the all-reduction state).
(3)
As shown by the arrow in the top-down direction in Figure6, the semijoin process is performed on the query trees in a top-down direction from the root nodes to the leaf nodes. Finally, all the intermediate relations in each node are in the full-reduction state.
(i)
Left subtree:E∝a=bG⟶E″ and X∝e=fE″⟶X′ (enabling X, which is not yet optimized, to be optimized)
(ii)
Right subtree:J∝c=dG′⟶J′, Y∝g=hJ′⟶Y′, and Z∝i=jJ′⟶Z′ (enabling Y and Z, which are not yet optimized, to be optimized)
(4)
After the upper and lower semijoins, the relations have all reached the all-reduction state. At this moment, useless tuples have been eliminated, and it is possible to perform the final transmission process and connection to obtain the query results.Figure 5
Query roadmap-ascending stage.Figure 6
Query roadmap-downlink phase.Transmission costs for all reduction algorithms:(1)
Bottom-up reduction stage: transmission costs forX, D, M, H, and K connection attributes
(i)
Transmission cost for connection attributes of relationX is cardΠeX∗sizee
(ii)
Transmission cost for connection attributes of relationE′ is cardΠaE′∗sizea
(iii)
Transmission cost for connection attributes of relationY is cardΠgY∗sizeg
(iv)
Transmission cost for connection attributes of relationZ is cardΠiK∗sizei
(v)
Transmission cost for connection attributes of relationJ′ is cardΠcJ′∗sizec
(2)
Post all-reduction stage: cost for post stage or cost for returning the attributes after reduction iscardi∗sizei,i∈a,b,c,d,e,f,g,h,i,j.All reduction algorithms extend the concept of the SDD-1 algorithm. Based on the data compression and semijoin strategy, a scheme to obtain all reduction programs is ultimately obtained. The reduction in these programs makes it possible to cut the communication costs involved with the network to a minimum [37]. This algorithm is mainly conducted to solve the problem of inaccurate semijoined programs being generated. Because of the inability of the real-time database, it is difficult to obtain an accurate chart of static characteristics. This algorithm eliminates the need to expend resources maintaining an enormous chart of static characteristics. Thus, it is possible to constantly evaluate the benefits of all the semijoined programs [38]. This makes it easier to recover the expenditure for the system.


## 5. Conclusions

An urban water supply system requires long-term complex water control systematic engineering. The establishment of a scientific evaluation system is very important to improve the water treatment efficiency, lower the water treatment costs, cut down on the expenses for water treatment, and effectively implement and perfect water treatment projects. This paper is mainly aimed at cutting down the internetwork communication expenses with respect to query optimization for a distributed database [39]. With the concept of the SDD-1 algorithm as a guide, this paper proposed a reduction strategy that involved cutting operations on the intermediate relations of the query trees in the semijoin strategy. In the entire course of a query, this algorithm only performs operations on the attributes. With the small amount of data being transmitted, it is relatively easy to realize this process. This algorithm does not depend upon the chart of static characteristics. Moreover, there is no need to analyze the benefits of intermediate semijoined results. However, it can reach the all-reduction state and eventually assist in reducing the communication costs by lowering the frequency of useless data transmission between the networks. In the process of urban water supply, this query optimization strategy will play an important role in cutting costs and improving efficiency.



---

*Source: 8068914-2018-10-02.xml*