# Subquery Allocation Problem and Heuristics for Secret Sharing Distributed Database System

Authors: Toshiyuki Miyamoto; Takeshi Ikemura
Journal: Journal of Computer Systems, Networks, and Communications
 (2010)

---

## Abstract

We discuss query optimization in a secure distributed database system, called the Secret Sharing Distributed DataBase System (SSDDBS). We have to consider not only subquery allocations to distributed servers and data transfer on the network but also decoding distributed shared data. At first, we formulated the subquery allocation problem as a constraints satisfaction problem. Since the subquery allocation problem is NP-complete in general, it is not easy to obtain the optimal solution in practical time. Secondly, we proposed aheuristic evaluation function for the best-first search. We constructed an optimization model on an available optimization software, and evaluated the proposed method. The results showed that feasible solutions could be obtained by using the proposed method in practical time, and that quality of the obtained solutions was good.


---

## Body

## 1. Introduction

The need for distributed databases (DDB) [1] is increasing as information technologies develop and the amount of data to be handled is growing exponentially. For databases such as those containing personal data, confidentiality, dependability, and robustness are becoming increasingly important. We have proposed a Secret Sharing Distributed Database (SSDDB) [2] that combines a secure distributed storage system [3–5] with a relational database system. The relations are divided into fragments in the SSDDB, and the fragments are managed by encrypting with a (k,n) threshold scheme [6]. Thus, the fragment must be both encrypted and decrypted every time there is a request to the database system to perform a search or some other functions. This makes it essential to have optimized parallel operation.Optimization of the query process in an SSDDB proceeds in 3 stages: optimization of the query structure, optimization of subquery allocation to servers employed, one for each fragment request, and optimization of the combination of subquery results. This paper addresses the issue of subquery allocation to servers.Optimization of the query process in an ordinary DDB is precisely described in [1]. A database management system must decide which server to use for processing when the same data are in distributed locations due to replication, even for ordinary distributed databases. Optimization of the query process for such a case is not sufficiently described in [1]. Evrendilek et al. proposed a query optimization problem which considers the data replication in [7]. However, with SSDDB, a server must be selected for decrypting fragments, and the procedures suggested for allocating subqueries to servers in ordinary DDBs are not very effective here. There exists no research on optimization of the query process for SSDDB as far as we know.There are three factors to consider when allocating subqueries to servers: firstly, subquery allocation to servers; next, determination of the server storing the fragment needed to handle the subquery; finally, determination of the server for the necessary decrypting of the fragment. Subquery allocation to servers in an ordinal distributed database is known to be an NP-complete problem [7]. Since the subquery allocation problem in an ordinal distributed database is a special case of that of SSDDB, subquery allocation to servers becomes an NP-complete problem. This paper is an investigation of best-first search methods with a view to online use, and proposes heuristic methods for the best-first search.Section2 provides an overview of SSDDB and Section 3 demonstrates the formulation of the subquery allocation problem as a constraint satisfaction problem. A heuristic evaluation function for a best-first search is then proposed. Section 4 shows the execution of an experimental calculation and demonstrates the effectiveness of the proposed heuristic evaluation function.


## 2. Secret Sharing Distributed Database System

### 2.1. The(k,n) Threshold Scheme

The secret sharing distributed database system is software that safely performs distributed sharing of confidential information. The system described herein uses the(k,n) threshold scheme demonstrated by Shamir [6].LetF represent an algebraic number field and a confidential datum s be an element of F. A (k-1)th degree polynomial equation is created using s and random coefficients ri∈F (i=1,…,k-1)
(1)f(x)=∑i=0k-1rixi,
where r0=s. The value wj=f(xj) is calculated for each of the n distinct values of xj∈F (j=1,…,n,xj≠0). The value wj is called a share and xj is called the ID of share wj.Sincef(x) is a (k-1)th degree polynomial, it is uniquely defined by its values at k different points (xj,f(x-j)). The confidential datum s can be retrieved by evaluating s=f(0).In the(k,n) threshold scheme, it is impossible to decrypt s using fewer than k shares. There is no dependence on how shares are selected, so even if up to n-k shares are lost, it remains possible to decrypt s.


### 2.2. SSDDB Structure

An outline of the structure of an SSDDB is presented in Figure1. The SSDDB is composed of a database management system (DBMS) and a secret sharing storage system (SSSS). The DBM process on the DBMS and the SSS process on the SSSS are assumed to be connected to each other over the Internet and each is able to communicate with the other individually.Figure 1
Secret Sharing Distributed Database.When the DBM receives a query from an external source, it creates a query processing plan. It carries out this processing while assigning subqueries to other DBMs for parts of the processing and sending requests to DBMs and SSSs to retrieve or decrypt the necessary data sets. Thus, the user can approach the DBMS in the same way as approaching an ordinary distributed database management system, but an SSSS is used for storage, so the specificity of an SSSS must be considered in the query optimization, as described below.The data sets are divided into small sets (fragments) and encrypted using the(k,n) threshold scheme. This process is managed by the SSSS. A DBM is also capable of caching data sets. Only DBM3 in the figure is caching data.The dashed lines in the figure indicate physical boundaries. DBM1, SSS1, DBM2, and SSS2 are each separate processes running on the same computer. In other words, no SSS process is running on the computer where DBM3 is running. A DBM can request an SSS to retrieve and decrypt a fragment on a different computer. However, this generates a cost due to transmission of data over the network.


## 2.1. The(k,n) Threshold Scheme

The secret sharing distributed database system is software that safely performs distributed sharing of confidential information. The system described herein uses the(k,n) threshold scheme demonstrated by Shamir [6].LetF represent an algebraic number field and a confidential datum s be an element of F. A (k-1)th degree polynomial equation is created using s and random coefficients ri∈F (i=1,…,k-1)
(1)f(x)=∑i=0k-1rixi,
where r0=s. The value wj=f(xj) is calculated for each of the n distinct values of xj∈F (j=1,…,n,xj≠0). The value wj is called a share and xj is called the ID of share wj.Sincef(x) is a (k-1)th degree polynomial, it is uniquely defined by its values at k different points (xj,f(x-j)). The confidential datum s can be retrieved by evaluating s=f(0).In the(k,n) threshold scheme, it is impossible to decrypt s using fewer than k shares. There is no dependence on how shares are selected, so even if up to n-k shares are lost, it remains possible to decrypt s.


## 2.2. SSDDB Structure

An outline of the structure of an SSDDB is presented in Figure1. The SSDDB is composed of a database management system (DBMS) and a secret sharing storage system (SSSS). The DBM process on the DBMS and the SSS process on the SSSS are assumed to be connected to each other over the Internet and each is able to communicate with the other individually.Figure 1
Secret Sharing Distributed Database.When the DBM receives a query from an external source, it creates a query processing plan. It carries out this processing while assigning subqueries to other DBMs for parts of the processing and sending requests to DBMs and SSSs to retrieve or decrypt the necessary data sets. Thus, the user can approach the DBMS in the same way as approaching an ordinary distributed database management system, but an SSSS is used for storage, so the specificity of an SSSS must be considered in the query optimization, as described below.The data sets are divided into small sets (fragments) and encrypted using the(k,n) threshold scheme. This process is managed by the SSSS. A DBM is also capable of caching data sets. Only DBM3 in the figure is caching data.The dashed lines in the figure indicate physical boundaries. DBM1, SSS1, DBM2, and SSS2 are each separate processes running on the same computer. In other words, no SSS process is running on the computer where DBM3 is running. A DBM can request an SSS to retrieve and decrypt a fragment on a different computer. However, this generates a cost due to transmission of data over the network.


## 3. Query Optimization for an SSDDB

### 3.1. Outline of Query Processing in an SSDDB

Optimization of query processing in an SSDDB consists of the three stages of firstly, query structure optimization, secondly, optimization of subquery allocation to multiple servers, one for each fragment request, and thirdly, optimization of the combination of the subquery results.In query structure optimization, the query is subdivided by employing information in the fragments. The first task is to eliminate any redundant expressions sometimes included in user-generated queries. Queries are also rewritten or divided into subqueries in order to reduce the volume of intermediate data. At this point, SSDDB specificity is not yet required, so the ordinary procedure for a DDBS [1] can be used as is.The generated subqueries can be processed by separate servers. In the second stage, a server for processing a subquery is selected so as to minimize the processing cost of the query, by considering fragment allocations and server loads. In the SSDDB, all fragments except for those in the cache are distributed as shares in the SSSS. Thus, no particular fragment is assigned to any particular server. The cost of recreating distributed fragments must be calculated. Sections3.2 and 3.3 address the issues of allocating subqueries to servers while considering the specificity of the SSDDB.Finally, the results of processing the subqueries assigned to the different servers are combined. As with the first step, SSDDB specificity is not required, so again the ordinary procedure for a DDBS [1, 7] can be applied as is.


### 3.2. Subquery Allocation Problem to Servers

LetS be a finite set of servers with |S|=p. Here, the term server is assumed to mean a physical computer, at most one DBM process and at most one SSS process are running on each server. F is a finite set of fragments with |F|=m, and SQ is a finite set of subqueries with |SQ|=r.Letdj,h∈ℝ+ be the cost required to decrypt some fragment fj∈F on some server sh∈S. Here, ℝ+ is the set of all nonnegative real numbers. Costs are set considerably higher in servers where an SSS process is not running, in order to avoid assigning decryption requests to such servers. When a fragment fj is decrypted on a server sh, the cost for transmitting shares from other servers is assumed to be stj,h∈ℝ+.The cost for processing a subquerysqi on a server sh is assumed to be wi,h∈ℝ+. As was the case with decrypting costs, this should be set rather high for servers where a DBM process is not running. The cost necessary in order to transmit a fragment fj from a server sh to a serversh′ is written tfj,h,h′. The load cost of a server sh is assumed to be lh∈ℝ+.Some additional variables are employed here.vi,j is set to the value of 1 when a subquery sqi calls a fragment fj; otherwise, to the value of 0. cj,h is set to 1 when a fragment fj is cached in a server sh; otherwise, to 0. xi,h is set to 1 when a subquery sqi is allocated to a server sh; otherwise, to 0. yh1,j,h2 is set to 1 when a fragment fj is transmitted to a server sh1, where it is required, from a server sh2; otherwise, it is 0. zj,h is set to 1 when a fragment fj is decrypted at a server sh; otherwise, it is 0.Normally, parameters of disk I/O, CPUs and the network can be used when constructing a query processing cost model in a distributed database. For an SSDDB, disk I/O can be considered a part of the share decryption cost; the following two costs are employed.The calculation costSCh in a server sh is defined with the following expression:
(2)SCh=lh+∑sqi∈SQxi,hwi,h+∑fj∈Fzj,hdj,h.The network costNCh for a server sh is defined thus:
(3)NCh=∑fj∈Fzj,hstj,h+∑fj∈F∑sh2∈Syh,j,h2tfj,h2,h.The above expressions indicate that the subquery allocation problem to servers becomes a constraint satisfaction problem for the decision variablesxi,h, yh1,j,h2, and zj,h(4)minmaxsh∈S{SCh+NCh}
subject to
(5)∀sqi∈SQ,∑sh∈Sxi,h=1,(6)∀sqi∈SQ,∀fj∈F,∀sh1∈S,xi,h1vi,j=∑sh2∈Syh1,j,h2,(7)∀sh1∈S,∀fj∈F,∑sh2∈Syh2,j,h1(zj,h1+cj,h1)=∑sh2∈Syh2,j,h1.
Here, the object function prevents the subqueries from being concentrated on a single server. Equation (5) is to ensure that each subquery is processed only once by one of the servers. Equation (6) indicates that the fragment a server requires must always be transmitted from some server (please note that the h1=h2 case is permitted). Equation (7) indicates that when a fragment fj is transmitted from a server sh1 to a server sh2, sh1 must have either decrypted fj or been holding it in its cache.


### 3.3. Subquery Allocation to Servers Based on Best-First Searches

Subquery allocation to servers in an ordinal distributed database is known to be an NP-complete problem [7]. If k is set to 1 in the (k,n) threshold scheme in an SSDDB, this describes an ordinal distributed database. Accordingly, the issue of subquery allocation to servers becomes an NP-complete problem. This paper is an investigation of best-first search methods with a view to online use.In combinatorial optimization problem, searching the optimal solution is done by expanding states iteratively. The search process could be described by a tree structure, called the search tree. Figure2 is an example of the search tree.Figure 2
A best-first search tree.Based on preliminary experiments, we heuristically decided the order of decision variables asxi,h, zj,h, yh1,j,h2 as shown in Figure 2. The depth of the search tree of each step is r, p*m, and r*m*p. But at the time when variables xi,h and zj,h are decided, most of variables yh1,j,h2 have been decided by evaluating (5), (6), and (7).In the best-first search, the most promising state is chosen by evaluating a function, called theheuristic evaluation function. Let us consider a situation expanding the state s in Figure 2; we are going to choose a server to process the subquery sqi. The heuristic evaluation function G(xi,h) shows an expected cost when choosing a server sh, and the search process chooses the state whose G(xi,h) is minimal.The fragments in the SSDDB are encrypted using the(k,n) threshold scheme and the shares are distributed to the various servers. Therefore, in order to process a subquery, the shares are transmitted and the fragment must be decrypted. Let us assume here that a subquery sqi is processed by a server sh, and that in addition to the cost wi,h of processing sqi on sh, there is a cost for the decryption of the fragment fj, which is needed for the processing in sqi, and transmitting fj to server sh. Accordingly, the minimum possible value for the cost of processing a subquery sqi on a server sh is as follows:
(8)G(xi,h)=lh+wi,h+minsh2∈S{dj,h2+stj,h2+tfj,h,h2}.When a subquerysqi is supposed to be processed on a server sh, a server to decrypt the corresponding fragment fj must be decided. The server sh2 which gives the minimal value in (8) is the most promising one. Accordingly, a heuristic evaluation function for choosing a server to decrypt a fragment fj is given as follows:
(9)G(zj,h)={0iftheservershgivestheminimalvaluein(8)forsomesubquery,1,otherwise.Since most of variablesyh1,j,h2 could be decided by evaluating (5), (6), and (7), we have not prepared any heuristic evaluation function for the variable yh1,j,h2.


## 3.1. Outline of Query Processing in an SSDDB

Optimization of query processing in an SSDDB consists of the three stages of firstly, query structure optimization, secondly, optimization of subquery allocation to multiple servers, one for each fragment request, and thirdly, optimization of the combination of the subquery results.In query structure optimization, the query is subdivided by employing information in the fragments. The first task is to eliminate any redundant expressions sometimes included in user-generated queries. Queries are also rewritten or divided into subqueries in order to reduce the volume of intermediate data. At this point, SSDDB specificity is not yet required, so the ordinary procedure for a DDBS [1] can be used as is.The generated subqueries can be processed by separate servers. In the second stage, a server for processing a subquery is selected so as to minimize the processing cost of the query, by considering fragment allocations and server loads. In the SSDDB, all fragments except for those in the cache are distributed as shares in the SSSS. Thus, no particular fragment is assigned to any particular server. The cost of recreating distributed fragments must be calculated. Sections3.2 and 3.3 address the issues of allocating subqueries to servers while considering the specificity of the SSDDB.Finally, the results of processing the subqueries assigned to the different servers are combined. As with the first step, SSDDB specificity is not required, so again the ordinary procedure for a DDBS [1, 7] can be applied as is.


## 3.2. Subquery Allocation Problem to Servers

LetS be a finite set of servers with |S|=p. Here, the term server is assumed to mean a physical computer, at most one DBM process and at most one SSS process are running on each server. F is a finite set of fragments with |F|=m, and SQ is a finite set of subqueries with |SQ|=r.Letdj,h∈ℝ+ be the cost required to decrypt some fragment fj∈F on some server sh∈S. Here, ℝ+ is the set of all nonnegative real numbers. Costs are set considerably higher in servers where an SSS process is not running, in order to avoid assigning decryption requests to such servers. When a fragment fj is decrypted on a server sh, the cost for transmitting shares from other servers is assumed to be stj,h∈ℝ+.The cost for processing a subquerysqi on a server sh is assumed to be wi,h∈ℝ+. As was the case with decrypting costs, this should be set rather high for servers where a DBM process is not running. The cost necessary in order to transmit a fragment fj from a server sh to a serversh′ is written tfj,h,h′. The load cost of a server sh is assumed to be lh∈ℝ+.Some additional variables are employed here.vi,j is set to the value of 1 when a subquery sqi calls a fragment fj; otherwise, to the value of 0. cj,h is set to 1 when a fragment fj is cached in a server sh; otherwise, to 0. xi,h is set to 1 when a subquery sqi is allocated to a server sh; otherwise, to 0. yh1,j,h2 is set to 1 when a fragment fj is transmitted to a server sh1, where it is required, from a server sh2; otherwise, it is 0. zj,h is set to 1 when a fragment fj is decrypted at a server sh; otherwise, it is 0.Normally, parameters of disk I/O, CPUs and the network can be used when constructing a query processing cost model in a distributed database. For an SSDDB, disk I/O can be considered a part of the share decryption cost; the following two costs are employed.The calculation costSCh in a server sh is defined with the following expression:
(2)SCh=lh+∑sqi∈SQxi,hwi,h+∑fj∈Fzj,hdj,h.The network costNCh for a server sh is defined thus:
(3)NCh=∑fj∈Fzj,hstj,h+∑fj∈F∑sh2∈Syh,j,h2tfj,h2,h.The above expressions indicate that the subquery allocation problem to servers becomes a constraint satisfaction problem for the decision variablesxi,h, yh1,j,h2, and zj,h(4)minmaxsh∈S{SCh+NCh}
subject to
(5)∀sqi∈SQ,∑sh∈Sxi,h=1,(6)∀sqi∈SQ,∀fj∈F,∀sh1∈S,xi,h1vi,j=∑sh2∈Syh1,j,h2,(7)∀sh1∈S,∀fj∈F,∑sh2∈Syh2,j,h1(zj,h1+cj,h1)=∑sh2∈Syh2,j,h1.
Here, the object function prevents the subqueries from being concentrated on a single server. Equation (5) is to ensure that each subquery is processed only once by one of the servers. Equation (6) indicates that the fragment a server requires must always be transmitted from some server (please note that the h1=h2 case is permitted). Equation (7) indicates that when a fragment fj is transmitted from a server sh1 to a server sh2, sh1 must have either decrypted fj or been holding it in its cache.


## 3.3. Subquery Allocation to Servers Based on Best-First Searches

Subquery allocation to servers in an ordinal distributed database is known to be an NP-complete problem [7]. If k is set to 1 in the (k,n) threshold scheme in an SSDDB, this describes an ordinal distributed database. Accordingly, the issue of subquery allocation to servers becomes an NP-complete problem. This paper is an investigation of best-first search methods with a view to online use.In combinatorial optimization problem, searching the optimal solution is done by expanding states iteratively. The search process could be described by a tree structure, called the search tree. Figure2 is an example of the search tree.Figure 2
A best-first search tree.Based on preliminary experiments, we heuristically decided the order of decision variables asxi,h, zj,h, yh1,j,h2 as shown in Figure 2. The depth of the search tree of each step is r, p*m, and r*m*p. But at the time when variables xi,h and zj,h are decided, most of variables yh1,j,h2 have been decided by evaluating (5), (6), and (7).In the best-first search, the most promising state is chosen by evaluating a function, called theheuristic evaluation function. Let us consider a situation expanding the state s in Figure 2; we are going to choose a server to process the subquery sqi. The heuristic evaluation function G(xi,h) shows an expected cost when choosing a server sh, and the search process chooses the state whose G(xi,h) is minimal.The fragments in the SSDDB are encrypted using the(k,n) threshold scheme and the shares are distributed to the various servers. Therefore, in order to process a subquery, the shares are transmitted and the fragment must be decrypted. Let us assume here that a subquery sqi is processed by a server sh, and that in addition to the cost wi,h of processing sqi on sh, there is a cost for the decryption of the fragment fj, which is needed for the processing in sqi, and transmitting fj to server sh. Accordingly, the minimum possible value for the cost of processing a subquery sqi on a server sh is as follows:
(8)G(xi,h)=lh+wi,h+minsh2∈S{dj,h2+stj,h2+tfj,h,h2}.When a subquerysqi is supposed to be processed on a server sh, a server to decrypt the corresponding fragment fj must be decided. The server sh2 which gives the minimal value in (8) is the most promising one. Accordingly, a heuristic evaluation function for choosing a server to decrypt a fragment fj is given as follows:
(9)G(zj,h)={0iftheservershgivestheminimalvaluein(8)forsomesubquery,1,otherwise.Since most of variablesyh1,j,h2 could be decided by evaluating (5), (6), and (7), we have not prepared any heuristic evaluation function for the variable yh1,j,h2.


## 4. Computational Experiment

This problem of subquery allocation to servers was solved with an ILOG solver (Ver. 5.1, ILOG). The problem was described using OPL. The operating system was Linux (CPU: Celeron 2.0 GHz, Memory: 1 GB).The following 2 procedures were used for comparison.No Heuristic
The ILOG Solver engine was used as is withoutheuristic evaluation functions. This solver determines variables in the order they are described. In the experimental model, they were described in the order x, z, y.EDN
Theheuristic evaluation function employed by Evrendilek et al. [7], which is referred to as EDN, was used in (10).
(10)G(xi,h)=lh+∑wi,h.
Equation (10) ensures that the processing for subqueries is distributed as widely as possible.The results are presented in Table1. Symbols p, m, and r in the table denote the numbers of servers, fragments, and subqueries, respectively. D denotes the dominant cost among the decryption cost (d), subquery processing cost (w) and transmission cost for shares and fragments (t). As indicated by n, all of these costs are about the same. The dominant cost was selected at random from the range [100,999] and the other costs were randomly selected from [10,99]. Five problems were constructed using identical conditions.Table 1
Experimental results.
pmrDProposedEDNNo Heuristictitotffϵtitotffϵtitotffϵ444n0.02.041.210.04.052.80014.5714.5824.43444d0.02.021.610.01.034.90.0131.9331.9315.59444w.01.02.021.190.02.031.290111.36111.3634.96444t.01.02.021.530.03.033.520.06.063.87555n.01.04.101.30.01.11.162.73.01—>360055.51555d.01.09.471.190.04.404.65.01.16.7425.30555w.01.59.591.23.01.03.0411.59.01—>360057.72555t.01.06.101.37.01.11.163.22.01131.10131.1423.81666n.022.814.471.57.022.064.303.70.01—>360056.83666d.031.844.711.69.021.424.485.63.01—>360056.54666w.026.836.8411.24.025.625.631.27.02—>360057.65666t.03.16.201.93.0135.5235.5314.76.02—>360055.90777n.0428.3129.741.84.0244.4149.474.37.03—>360058.26777d.038.669.1211.85.033.5496.986.17.03—>360057.12777w.04.10.1321.37.03.16.1811.65.03—>3600511.48777t.04.18.972.26.0438.0939.4115.49.03—>360057.15888n.0712.5677.552.23.0554.73118.164.08.05—>360059.01888d.07228.05297.2431.60.06259.21334.66311.23.05—>3600512.54888w.06452.08452.1221.37.054.384.4341.92.06—>3600516.12888t.061.071.132.13.0614.8715.0127.86.05—>360059.431044n.03.39.501.96.03.25.373.97.03—>360057.272044n.178.6712.091.96.1410.1213.552.91.18—>360059.893044n.393.995.332.85.37500.26501.193.47.48—>360059.794044n.8912.0016.6713.98.82124.77124.8712.241.05—>360057.625044n1.75228.79229.2523.461.70355.59356.004.242.15—>3600512.476044n2.86352.73369.863.512.701381.341391.8412.983.44—>360059.677044n4.4240.6240.7333.414.381261.051261.6023.515.19—>3600513.758044n7.1059.4259.8023.287.17635.63649.353.288.60—>3600512.129044n9.2082.56730.9123.638.89518.86529.9833.4911.16—>3600511.054104n.02.15.191.22.01.12.182.93.0116.7316.7734.344204n.041.181.651.48.032.032.402.72.03.87.9434.004304n.062.063.331.21.054.065.092.45.052.972.9844.334404n.082.034.001.22.073.926.422.37.07—>360054.064504n.12212.42434.961.38.11121.41655.802.61.11—>360054.304604n.1616.2238.711.24.1413.0151.893.52.14—>360054.554704n.2026.3232.6111.27.17415.08421.5013.14.17—>360055.004804n.2585.89185.641.58.22578.80608.032.67.21—>360054.724904n.2969.58149.281.36.271017.211127.392.80.26—>360054.394410n.016.5316.591.50.016.3425.372.110—>360054.984420n.04—>36005—.01—>36005—.01—>36005—4430n.06—>36005—.02—>36005—.02—>36005—4440n.10—>36005—.04—>36005—.03—>36005—4450n.14—>36005—.06—>36005—.04—>36005—4460n.22—>36005—.07—>36005—.04—>36005—4470n.26—>36005—.09—>36005—.04—>36005—4480n.36—>36005—.11—>36005—.06—>36005—4490n.41—>36005—.14—>36005—.06—>36005—The calculation time was limited to 1 hour andf was the number of searches that were not completed within the time limit. Blank columns indicate that searches were completed for all problems. The value ti was the mean time required to find a feasible solution (initial feasible solution). The value to was the mean time required to find the optimal solution. The value tf was the mean time required to complete the search. The means for to and tf were taken over the searches that were completed. All times were stated in seconds.The valueϵ is the ratio between the evaluated values of the initial feasible solution and the optimal solution and represents the mean over problems for which the optimal solution was identified.The results whenp, m, and r were set to identical values and the scale of the problem was varied are listed in the upper part of Table 1. The time ti was within 0.1 s and the feasible solution was easily found with all the methods. Also, as ϵ shows, the proposed procedure proved to be better than the other procedures at finding the initial feasible solution.The time required to complete the search grew exponentially with the scale of the problem.Furthermore, the search was never completed within the time limit under the No Heuristic procedure, even when the problem scale was small. Thus, it is essential to develop a procedure for quickly deriving a useful feasible solution for the subquery allocation problem.The proposed method was able to find optimal solutions for a greater quantity of the problems within the time limit than the EDN approach. Also, on average, the proposed method was superior from the perspective of times to find the optimal solution and complete the search. It should be noted that the values forto and tf are the means of problems seeking optimal solutions within the time limit. For example, under p=8, m=8, r=8, and D=w, for the proposed method to=452.08 s, while for EDN to=4.38 s. However, the proposed method successfully completed 3 problems, while EDN successfully completed only 1 problem. The given values for to and tf for EDN represent those from that single problem, while the values from the proposed method are the means taken over the three problems.Thus, the proposed method is superior to both EDN and the No Heuristic procedure in terms of both initial feasible solution and calculation time.Let us turn to some observations about the relationship between problem characteristics and solution methods. First, when the transmission cost is dominant (D=t), the searches are completed more quickly than for other problems of similar scale. On the other hand, when the subquery processing cost or decryption cost is dominant (D=w or D=d), the time required for search completion increases with the scale of the problem. This seems to be because transmission cost depends greatly on server selection.We observed changes in the calculation time when only one of the parametersp, m, or r was changed (lower part of Table 1).It takes more time to derive an initial feasible solution when the number of servers is increased; on the other hand, the time to identify an initial feasible solution remained within 1 s when either the number of fragments or subqueries was increased. The value ofϵ was raised relatively high by expanding the number of servers. Future studies must address the issue of developing procedures for identifying good feasible solutions at high speed in systems incorporating large numbers of servers.


## 5. Conclusions

It is essential to optimize query processing, as this has a great influence over database performance. This study provides a formulation of the subquery allocation problem in a secret sharing distributed database in terms of a constraint satisfaction problem. Aheuristic evaluation function is proposed for solutions in best-first searches.An experiment was conducted using an ILOG Solver to examine the effectiveness of the above function. Some issues remain for the proposed procedure when there are a large number of servers, and further research will be necessary. It will also be necessary to evaluate the performance of this method on an actual system.



---

*Source: 984059-2010-02-14.xml*