=Paper=
{{Paper
|id=Vol-1558/paper39
|storemode=property
|title=Weighted Sum Model for Multi-Objective Query Optimization for Mobile-Cloud Database Environments
|pdfUrl=https://ceur-ws.org/Vol-1558/paper39.pdf
|volume=Vol-1558
|authors=Florian Helff,Le Gruenwald,Laurent d'Orazio
|dblpUrl=https://dblp.org/rec/conf/edbt/HelffGd16
}}
==Weighted Sum Model for Multi-Objective Query Optimization for Mobile-Cloud Database Environments==
https://ceur-ws.org/Vol-1558/paper39.pdf
Weighted Sum Model for Multi-Objective Query
Optimization for Mobile-Cloud Database Environments
Florian Helff1 Le Gruenwald1 Laurent d'Orazio2
1 2
School of Computer Science CNRS, UMR 6158, LIMOS
University of Oklahoma Blaise Pascal University
Norman, Oklahoma, USA Clermont-Ferrand, France
{fhelff, ggruenwald}@ou.edu laurent.dorazio@isima.fr
ABSTRACT Consider the three query execution plans (QEPs) with their costs
In a mobile-cloud database environment, different users on for monetary costs (M), execution time (T) and energy
multiple mobile devices request services executed on a cloud. consumption (E) shown in Figure 1. Focusing on a single
During those requests, queries are executed to obtain data, stored objective always leads to the decision to select either plan QEP1
on the cloud and partly in caches on the mobile devices. The or QEP2 for execution since those QEPs have a minimum cost in
process of choosing an optimal query execution plan during a one of the three objectives. Since QEP3 does not have a minimum
query optimization process is difficult because of multiple value in any of the three costs, it will never be selected although it
objectives involved regarding multiple non-static pricing models is a competitive choice considering all three objectives on the
and different user constrains, such as monetary cost, query same level of importance. Therefore, a strategy which considers
execution time and mobile device energy consumption. This paper all objectives at the same time is needed in order to make a
provides a strategy of how to incorporate those various objectives comprehensive decision.
in this decision process, based on a weighted-sum model, to
achieve a good query execution plan. The experimental
performance studies show that comparing with strategies, the QEP1: {M= $0.080; T= 0.5s; E= 0.012 mA}
proposed strategy is able to achieve its goal while incurs almost QEP2: {M= $0.050; T= 3.0s; E= 0.300 mA}
no additional overhead.
QEP3: {M= $0.055; T= 0.6s; E= 0.013 mA}
1. INTRODUCTION Figure 1 Execution Plan Costs Example
In a mobile-cloud database environment [1], queries are issued at
mobile devices to retrieve data that is stored on the cloud and An existing optimization strategy which incorporates multiple
optionally on the mobile devices. The process of finding an objectives is called the Weighted Sum Model [5]. In this model,
optimal query execution plan (QEP) in this environment is every possible alternative (a QEP in our application) is rated by a
important in many ways. In an application scenario where many score including all objectives, individually weighted to stress the
queries are executed per day, organizations try to minimize the importance of different objectives. This model is used in many
monetary cost spent for query execution to fit their budget. They multi-objective optimization problems in various fields of
also want to minimize query execution times to meet customers’ computer science and also other fields such as economics (Cost-
query response time requirements and to optimize employees’ Utility Analysis) [6] [7]. However, the weakness of this model is
working time. Furthermore, users also want to minimize energy the process of summarizing the different objectives. The fact that
consumption on their mobile devices where queries might be different objectives might have different dimensions and units
executed [2]. This optimization process is a stretch of leads to the problem of “adding apples and oranges” [8]. Since the
contradicting propositions, especially when considering different mobile-cloud database environment has to deal with multi
cloud pricing models [3]. objectives with different units, the Weighted Sum Model cannot
Current decision strategies mostly focus on a single main be used without major changes in its strategy. This problem is
objective, such as execution time, and order further objectives, dealt with in the later explanation of our proposed algorithm in
like monetary cost and energy consumption, in a descending Section 4.
order. This strategy is called lexicographical ordering [4] which is To fit in the context of Query Optimization, the Normalized
not sufficient as shown in following example: Weighted Sum Algorithm (NWSA), which is proposed in this
paper, uses the Weighted Sum Model as basis but makes major
changes to cover the weaknesses of it and to fit in the mobile-
cloud database environment. To cover multiple units for different
objectives, the values are normalized to a user-defined maximum.
This process eliminates units and results in distribution on a
2016, Copyright is with the authors. Published in the Workshop percentage basis. Additionally, user weights are implemented to
Proceedings of the EDBT/ICDT 2016 Joint Conference (March 15, 2016, situational stress on objectives, according to user preferences and
Bordeaux, France) on CEUR-WS.org (ISSN 1613-0073). Distribution of needs. These strategies adapt the ideas of a user based decision
this paper is permitted under the terms of the Creative Commons license [9].
CC-by-nc-nd 4.0
Experiments are conducted to study the performance of NWSA. 2.2 The Weighted Sum Model
The experimental results show that NWSA is able to derive a The Weighted Sum Model (WSM) [5, 12] is most commonly used
good QEP and incurs almost no additional overhead comparing in multi-objective optimization problems. It combines the
with the existing strategy that is based on the lexicographical different objectives and weights corresponding to those objectives
ordering of the optimization objectives [4]. to create a single score for each alternative to make them
The rest of the paper is structured as follows. Section 2 gives comparable. The formulas used in this model are shown in the
some fundamental information about the Weighted Sum Model, following Figure 2.
underlying principles and explains the adjustments of this model. In these formulas, the WSM-score for an alternative Ai denoted as
Section 3 discusses other related work. Section 4 describes the 𝐴𝑊𝑆𝑀−𝑠𝑐𝑜𝑟𝑒
𝑖 is calculated by adding the products of a weight 𝑤𝑗
proposed strategy, the Normalized Weighted Sum Algorithm. with its corresponding parameter 𝑎𝑖𝑗 , the value of this objective.
The experimental model and results and the underlying use case This parameter is, for example, the monetary cost which has to be
are discussed in Section 5. Finally, the conclusions and future spent to execute the query. The best alternative is chosen as the
work are given in Section 6. one which has the maximum WSM score ( 𝐴𝑊𝑆𝑀−𝑠𝑐𝑜𝑟𝑒 ∗ ). The
different objectives are assumed to be positive: the higher the
score, the better the alternative. Assuming objectives to be
2. FUNDAMENTAL INFORMATION negative (in case of cost models), the best alternative has
This section describes the Pareto Set, which is fundamental for equivalently the lowest score.
every Multi-Objective Optimization problem, and the Weighted
Sum Model, that will be modified and used in the proposed
strategy. 3. RELATED WORK
The lexicographic ordering is probably the simplest but most used
scoring function to solve multi-objective optimization problems
2.1 Pareto set [4]. This strategy compares parameters of the most important
The Pareto set is a set of dominant alternatives, which does not objective and selects the alternative with the highest/lowest
include dominated alternatives. An alternative ‘A’ is dominating parameter for that objective. If multiple alternatives consist of the
an alternative ‘B’ if at least one objective (decision variable) of same highest/lowest parameter, the selection process starts over
‘A’ is better than the objective in ‘B’ and all other objectives in with the second most important objective under those alternatives
‘A’ are at least equal to the objectives in ‘B’. Those dominating [4]. The complexity of this algorithm is in linear relation to the
alternatives are called Pareto optimal as defined by Zitzler and count of alternatives it selects its solution from since it scans the
Thile [10]. In the application of query optimization, every alternative once for the lowest parameter. This strategy is
objective corresponds to a cost, for example, query execution equivalent to the example explained in Section 1, which also
time, monetary cost, or energy consumption cost, and an shows the weaknesses of the lexicographical ordering. Multiple
alternative is equivalent to a single QEP. objectives are only considered if the selection process on a single
objective is not sufficient. Although this strategy does not have to
The strength of finding a Pareto set is that every alternative in this deal with multiple dimensions or units, it is not sufficient in
set is optimal for at least one scoring function. A scoring function finding an optimal solution for the proposed optimization problem
describes the stress on the different objectives in order to set the since it cannot handle multiple objectives and, therefore, is not
importance to them and to compare alternatives in this Pareto set. able to give a sufficient solution.
[11]
The set of all optimal solutions under every possible scoring
In the context of query optimization, finding a Pareto set of query function is called the Pareto set. Skyline queries [13, 14, 15] are
execution plans is not sufficient for query execution since a single one example of a strategy of finding a Pareto set. Those strategies
execution plan needs to be selected. The process of selecting a are used in situations where no scoring function is available. As
single solution is left open for a user to choose. Regardless, the also mentioned in [9], it is important to distinguish between the
following Weighted Sum Model functions as a scoring function, Pareto optimal set, skyline queries which return the Pareto optimal
using a user’s preferences, and always selects a query out of this alternatives, the skyline which represents the result of skyline
Pareto set, which is proven in Section 0. queries and the according algorithms to implement the queries. As
already discussed, because one single alternative has to be
returned as the output, a strategy that finds the Pareto optimal
𝑛 alternatives alone is not sufficient to solve this problem. There
exists work that aims to solve the problem of multi-objective
𝐴𝑊𝑆𝑀−𝑠𝑐𝑜𝑟𝑒
𝑖 = ∑ 𝑤𝑗 𝑎𝑖𝑗
query optimization in combination with Skyline queries [16] or
𝑗=1
Pareto set computations [17] [18] but all those strategies have to
𝑛 be concluded by a user selecting one of the solutions from the
𝐴𝑊𝑆𝑀−𝑠𝑐𝑜𝑟𝑒
∗ = max ∑ 𝑤𝑗 𝑎𝑖𝑗 Skyline/Pareto Set. The reason of calculating a Pareto set is
𝑖
𝑗=1 because of lack of an existing scoring function during execution
time. The weakness of such calculation is the generated overhead
of the calculation since this is an expensive computation. Given a
Figure 2 Weighted Sum Model Scoring Function scoring function, and making the user decide on his/her
preferences prior execution to directly compute a single solution,
which is an element in a Pareto set, avoids the additional overhead
since computing the Pareto set is not necessary.
4. NORMALIZED WEIGHTED SUM 𝑛
𝑎𝑖𝑗
ALGORITHM 𝐴𝑊𝑆𝑀−𝑠𝑐𝑜𝑟𝑒
∗ = min ∑ 𝑤𝑗
𝑖 𝑚𝑗
This section describes the proposed algorithm called the 𝑗=1
Normalized Weighted Sum Algorithm (NWSA), the
implementation details and the proof showing that NWSA always Figure 5 Modified Weighted Sum Model Scoring Function:
selects a query execution plan from the Pareto set. Optimal Alternative
In the following Section 4.2, the proposed algorithm is described.
4.1 Adaption to Multi-Objective Problems It is then followed by a proof that the chosen alternative in this
As already pointed out in Section 1, one problem of the WSM is decision process is always an element of the corresponding Pareto
the addition of multiple dimensions or units. This problem can be set, independent of the chosen weights.
resolved by normalizing the different parameters [12]. This
normalization can be done in relation to a user-defined maximum
4.2 Algorithm
The developed algorithm calculates the best alternative in a multi-
of acceptance of each objective. The resulting values represent the
objective decision process as shown in Figure 6.
fraction towards this maximum and do not contain a unit which
makes them addable to each other. Additionally, the normalization
to a user-defined maximum of parameters adapts another strategy Algorithm : NWSA
called user-based decision [9]. Another advantage of this user- Input:
defined maximum of acceptance of each objective can be seen in Alternatives Ai with i=1..m and parameter aij to
the later implementation of the algorithm. Alternatives which objective Oj with j=1..n ; uwj the user weight for
violate those regulations can be taken out of consideration to keep objective Oj; ewj the environment weight for objective
the defined conditions. Oj; mj the maximum accepted value for objective Oj
The second adjustment is made for the weights. To include
environmental factors, the used weight is composed of a user- Output: best alternative Ai
defined weight and an automatically generated environmental
weight. Environmental factors are, for example, the current 1. Abest null
battery status, an ongoing charging process or factors describing
2. AbestRestrictionViolating null
the currently used cloud. The environmental weight adjusts the
user weight if, for example, a mobile device is being charged and
energy consumption is obsolete, or a query is run overnight and 3. for i=1 to m
execution time should be assigned a minor importance factor. 4. Aiscore CalculateScore(Ai)
5. end for
In conclusion, the Modified Weighted Sum Model Scoring
Function can be expressed as in Figure 3.
6. for i=1 to m
7. violate false
𝑛
𝑎𝑖𝑗 8. for j=1 to n
𝐴𝑊𝑆𝑀−𝑠𝑐𝑜𝑟𝑒
𝑖 = ∑ 𝑤𝑗 9. if(aij>mj)
𝑚𝑗
𝑗=1
10. violate true
11. save violation
Figure 3 Modified Weighted Sum Model Scoring Function 12. end if
13. end for
𝑎𝑖𝑗 is the value of alternative i (QEPi) for objective j, 𝑚𝑗 the user-
14. if(violate=true)
defined acceptable maximum value for objective j, and 𝑤𝑗 the
15. if(Aiscore< AbestRestrictionViolatingscore)
normalized composite weight of user and environment for
objective j defined in Figure 4. 16. AbestRestrictionViolating Ai
17. end if
18. else
𝑗 𝑢𝑤 ∗𝑒𝑤
𝑗 19. if(Aiscore < Abestscore)
𝑤𝑗 = ∑(𝑢𝑤 .
∗𝑒𝑤) 20. Abest Ai
21. end if
Figure 4 Composite Normalized Weight Factor 22. end if
23. end for
Figure 4 shows the computation of the composite weight where
uwj and ewj describe the weight of the user and the environmental 24. if(Abest null)
weight for objective j, respectively. Since the different objectives
are representative of different costs, the algorithm chooses the
25. return AbestRestrictionViolating , violations
alternative with the lowest score to minimize costs as shown in 26. else
Figure 5. 27. return Abest
28. end if
Figure 6 Decision Algorithm processing the cache consumes more energy than waiting for
incoming data. A full review of such a system is given in [19].
The modified WSM function to calculate the score of an Regarding that background, the simulation is built as follows:
alternative Ai (CalculateScore(Ai)), which is used in Line 5 of this
algorithm, is the previously defined function in Figure 3. This The simulation consists of one million experiments, where the
function is executed for every alternative (Lines 3-5). As it can be proposed NWSA as well as the lexicographical ordering strategy
seen in this algorithm, each alternative is checked if it violates the have to choose a single QEP out of a set of 20 QEPs. The cost of
user-defined maximum value for each objective (Lines 8-13). The each QEP is generated randomly within the following ranges:
violation itself has to be saved for future use (Line 11) Monetary Cost (M) has a range of 0 up to 10 cents and was
Afterwards, the best alternative (Abest) which is the one with the chosen according to the current Amazon EC2 pricing models [3];
lowest score is selected (Lines 14-22) and returned as the output the range for query execution time was selected to be between 0
of the algorithm. If all possible alternatives violate those and 10 seconds (including data transfer time), and energy between
restrictions, the algorithm will return the lowest score alternative 0 and 0.5 mAh. This simulation is repeated for multiple weight
(AbestRestrictionViolating) as well as the previously saved restriction(s) compositions.
that it violates (Lines 24-25). The complexity of this algorithm is
in linear relation to the count of alternatives, which is also the
complexity of the lexicographical ordering strategy as discussed 5.2 Experimental Results
in Section 3. In comparison to the lexicographical ordering strategy the
experimental results show two facts: First, the NWSA computes
the same results under the same costs as the lexicographical
4.3 Proof for Pareto-Set ordering when focusing only on one objective. Second, NWSA
This section provides a proof that, independent from possible produces negligible overhead in computing this selection. As it
weights and from the number of objectives, the proposed was already discussed in the previous sections 3 and 4.2, both
algorithm always picks an alternative within the Pareto set. algorithms are running linear execution time related to the size of
QEPs to choose from. That leads to a total algorithm execution
Proof by contradiction: time of less than one millisecond per experiment for both
It is assumed that the chosen algorithm picks an alternative Abest algorithms so that the difference is negligible. Concluding this
which is not an element of the Pareto set. Compliant with the used comparison, negligible overhead is incurred and no higher cost
formula in the proposed algorithm (Figure 3) it can be determined alternatives results are selected. Looking at the performance of
that NWSA, this evaluation shows the possibilities of this strategy.
𝒏 𝒏
𝑨𝑾𝑺𝑴−𝒔𝒄𝒐𝒓𝒆
𝒃𝒆𝒔𝒕 = ∑ 𝒘𝒋 𝒂𝒊𝒋 = 𝐦𝐚𝐱 ∑ 𝒘𝒋 𝒂𝒊𝒋
𝒊
𝒋=𝟏 𝒋=𝟏
Impact of Monetary Cost Weight on
Since Abest is not an element of the Pareto set, an alternative Apareto Total Monetary Cost (MC)
hast to exist which dominates Abest. According to the definition of
the Pareto set, this alternative has one higher value for at least one 60000
criterion than Abest without having a lower value for all other 50000
objectives. This is in contradiction to
𝑛 40000
𝐴𝑊𝑆𝑀−𝑠𝑐𝑜𝑟𝑒 = max ∑ 𝑤𝑗 𝑎𝑖𝑗 MC
𝑏𝑒𝑠𝑡
𝑖
𝑗=1
in $ 30000
since the score is better for Apareto with unchanged weights. A 20000
similar proof in the context of skyline queries is shown in [13].
10000
0
5. PERFORMANCE EVALUATION
0
1
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
This section describes an evaluation of the proposed strategy by
means of simulation experiments. It also compares the differences Weight on Monetary Cost
of the proposed algorithm with the lexicographical ordering
strategy [4]. Figure 7 Impact of Monetary Cost Weight on Total Monetary
Cost of QEPs selected by NWSA
5.1 Simulation Model
In the proposed mobile-cloud database environment, each QEP
consists of three costs: monetary cost for using the cloud provider,
query execution time as time to run a certain query plan, and
energy used on the mobile device. The last cost becomes
important under the condition of using a cache on the mobile
device to have the option of receiving partial or total requested
data from the mobile device itself [2]. This obviously results in a
lower monetary cost since the cloud provider is less or not used,
but also results in a higher amount of consumed energy since
Algorithm (NWSA), was proposed, to select the best query
Impact of Monetary Cost Weight on execution plan for query optimization that includes multiple
Query Execution Time (QET) objectives, such as monetary cost, query execution time, and
energy consumption, in the decision process. The simulation
12000 experiments evaluating NWSA in the context of a mobile-cloud
11500 query optimization have been presented. NWSA is able to select
11000 the query execution plan that is an element of the Pareto set, while
avoiding the expensive cost of computing the Pareto set. NWSA is
QET 10500 highly adaptable to any multi-objective decision problem since it
in sec 10000 is not limited to any number of objectives. The experimental
9500 results show that NWSA incurs negligible computational
9000 overhead in comparison to the existing lexicographical ordering
8500 strategy. Additionally, the use of weights enables a more precise
8000 selection of a query execution plan since the minimum and
maximum values of an objective span a wide gap.
0 0,1 0,20,30,40,5 0,60,70,8 0,9 1
A future modification is to also consider non-linear functions of
Weight on Monetary Cost
the normalization of objectives as well as of the composition of
user and environmental weights. As far as the usage of this
Figure 8 Impact of Monetary Cost Weight on Total Execution algorithm is concerned, we intend to incorporate it into the query
Time of QEPs selected by NWSA optimization process to calculate fast estimations of query costs
for clouds [20, 21, 22, 23]. Another future field of usage of this
algorithm is a new Cache Replacement Policy for the mobile
Impact of Monetary Cost Weight on Cache to extend semantic Caching [2]. Based on the computed
Total Consumed Energy (E) score of a QEP, the new policy can help to keep more valuable
data in the semantic cache (the higher the score is, the higher the
250000 cost to regain those results will be).
245000
240000
E 235000 ACKNOWLEDGEMENT
in mAh 230000 This work is partially supported by the National Science
225000 Foundation Award No. 1349285.
220000
215000
References
210000
0
1
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
[1] H. T. Dinh, C. Lee, D. Niyato und P. Wang, „A survey of
Weight on Monetary Cost mobile cloud computing: architecture, applications, and
approaches,“ in Wireless communications and mobile
Figure 9 Impact of Monetary Cost Weight on Total Consumed computing 13.18, 2013.
Energy of QEPs selected by NWSA
[2] M. Perrin, "Time-, Energy-, and Monetary Cost-Aware
To have an option of deciding how to stress the weights on the Cache Design for a Mobile Cloud Database System," May
different objectives can change a lot in terms of total cost as it can 2015.
be seen in Figure 7-9. The figures show the changes of the total
cost of the one million chosen QEPs as the weight on monetary [3] Amazon, „Amazon EC2 Pricing,“ 2015. [Online]. Available:
cost increases. The remaining weight is divided equally between https://aws.amazon.com/ec2/pricing/?nc1=h_ls. [Zugriff am
execution time and energy consumption. 18 08 2015].
It can be seen that when the monetary cost weight increases, the [4] A. Ben-Tal, Characterization of Pareto and lexicographic
monetary costs decreases, while the query execution time and optimal solutions, Springer Berlin Heidelberg, 1980.
energy consumption increase. It is notable that the minimum and
maximum values of an objective span a large gap, so an impact of [5] E. Triantaphyllou, Multi-criteria decision making methods: a
having weights is easily seen. Already having a small weight on comparative study, 44 ed., Springer Science & Business
one objective can lead to a big difference in the total cost. Media, 2013.
While not shown in this paper, the graphs plotting the impacts of [6] P. Kind, J. E. Lafata, K. Matuszewsk und D. Raisch, „The
increasing weights on the execution time and energy consumption use of QALYs in clinical and patient decision-making: Issues
show an equivalent trend as the impact of increasing weights on and prospects,“ in VALUE IN HEALTH 12, 2012.
the monetary cost.
[7] M. G. M. Hunink und M. C. Weinstein, Decision Making in
Health and Medicine: Integrating Evidence and Values, 2nd
Hrsg., Cambridge University Press, 2014.
6. CONCLUSION AND OUTLOOK
In this paper, a new algorithm, called Normalized Weighted Sum
[8] P. C. Fishburn, "Methods of estimating additive utilities.: 2014.
Management science 13.7," 1967.
[18] C. Lei, Z. Zhuang, E. A. Rundensteiner und M. Eltabakh,
[9] C.-H. Goh, Y.-C. A. Tung and C.-H. Cheng, " A revised „Shared Execution of Recurring Workloads in
weighted sum decision model for robot selection," in MapReduce∗,“ in Proceedings of the VLDB Endowment,
Computers & Industrial Engineering Vol.30(2), 1996. 2015.
[10] E. Zitzler and L. Thiele, "Multiobjective Evolutionary [19] J. Mullen, M. Perrin, F. Helff, L. Gruenwald and L. d'Orazio,
Algorithms:," in IEEE TRANSACTIONS ON "A Vision of Time-, Energy-, and Monetary Cost-Aware
EVOLUTIONARY COMPUTATION, VOL. 3, NO. 4, , Query Processing in Mobile Cloud Database Environment,"
NOVEMBER 1999. March 2015.
[11] D. V. Lindley, Scoring Rules and the Inevitability of [20] N. Bruno, S. Jain and J. Zhou, "Continuous cloud-scale query
Probability, 50 ed., International Statistical Review Vol 50, optimization and processing," in Proceedings of the VLDB
1982, pp. 1-11. Endowment 6.11 , 2013.
[12] I. Kim and O. de Weck, "Adaptive weighted-sum method for [21] H. Kllapi, E. Sitaridi und M. M. Tsangaris, „Schedule
bi-objective optimization: Pareto front generation," in Optimization for Data Processing Flows on the Cloud,“ in
Structural and multidisciplinary optimization 29.2 , 2005, pp. Proceedings of the 2011 ACM SIGMOD International
149-158. Conference on Management of data (ACM), 2011.
[13] J. Chomicki, P. Ciaccia and N. Meneghetti, "Skyline queries, [22] M. Armbrust and e. al., "A view of cloud computing," in
front and back," in ACM SIGMOD Record 42.3, 2013. Communications of the ACM 53.4, 2010.
[14] D. Kossmann, F. Ramsak and S. Rost, "Shooting stars in the [23] H. M. Fard, R. Prodan, J. J. D. Barrionuevo and T. Fahringer,
sky: An online algorithm for skyline queries," in Proceedings "A Multi-Objective Approach for Workflow Scheduling in
of the 28th international conference on Very Large Data Heterogeneous Environments," in 12th IEEE/ACM
Bases (VLDB), 2002. International Symposium on Cluster, Cloud and Grid
Computing, 2012.
[15] D. Papadias, Y. Tao, G. Fu and B. Seeger, "An optimal and
progressive algorithm for skyline queries," in Proceedings of
the 2003 ACM SIGMOD international conference on
Management of data (ACM), 2003.
[16] C. H. Papadimitriou und M. Yannakakis, „Multiob jective
Query Optimization,“ in Proceedings of the twentieth ACM
SIGMOD-SIGACT-SIGART symposium on Principles of
database systems, 2001.
[17] I. Trummer und C. Koch, „Multi-Objective Parametric Query
Optimization,“ in Proceedings of the VLDB Endowment,