Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
New Channel Access Approach for the IEEE 802.15.4 Devices in 2.4 GHz ISM Band Read chapter Read first chapter

2014 | OriginalPaper | Chapter

Integer Linear Programming Solution for the Multiple Query Optimization Problem

Authors : Tansel Dokeroglu, Murat Ali Bayır, Ahmet Cosar

Published in: Information Sciences and Systems 2014

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Multiple Query Optimization (MQO) is a technique for processing a batch of queries in such a way that shared tasks in these queries are executed only once, resulting in significant savings in the total evaluation. The first phase of MQO requires producing alternative query execution plans so that the shared tasks between queries are identified and maximized. The second phase of MQO is an optimization problem where the goal is selecting exactly one of the alternative plans for each query to minimize the total execution cost of all queries. A-star, branch-and-bound, dynamic programming (DP), and genetic algorithm (GA) solutions for MQO have been given in the literature. However, the performance of optimal algorithms, A-star and DP, is not sufficient for solving large MQO problems involving large number of queries. In this study, we propose an Integer Linear Programming (ILP) formulation to solve the MQO problem exactly for a large number of queries and evaluate its performance. Our results show that ILP outperforms the existing A-star algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Cooperative Emergency Navigation Framework Using Mobile Cloud Computing
next chapter A Graphical Model Approach for Multi-Label Classification
Literature
1.
E. Angel, E. Bampis, L. Gourvès, On the minimum hitting set of bundles problem, Algorithmic Aspects in Information and Management (Springer, Berlin, 2008), pp. 3–14CrossRef
2.
M.A. Bayir, I.H. Toroslu, A. Cosar, Genetic algorithm for the multiple-query optimization problem. Syst. Man Cybern. Part C: Appl. Rev. IEEE Trans. 37(1), 147–153 (2007)CrossRef
3.
J.R. Bernardino, P.S. Furtado, H.C. Madeira, Approximate query answering using data warehouse striping. J. Intell. Inf. Syst. 19(2), 145–167 (2002)CrossRef
4.
F.C. Chen, M.H. Dunham, Common subexpression processing in multiple-query processing. Knowl. Data Eng. IEEE Trans. 10(3), 493–499 (1998)CrossRef
5.
A. Cosar, E.P. Lim, J. Srivastava, Multiple query optimization with depth-first branch-and-bound and dynamic query ordering. in Proceedings of the second international conference on Information and knowledge management (ACM, 1993), (pp. 433–438)
6.
A. Cosar, J. Srivastava, S. Shekhar, On the multiple pattern multiple object (MPMO) match problem. Army High Perform. Comput. Res. Cent. (1991)
7.
A.A. Diwan, S. Sudarshan, D. Thomas, Scheduling and caching in multi-query optimization. In Proceedings of 13th International Conference Management of Data (2006)
8.
S. Finkelstein, Common expression analysis in database applications. in Proceedings of the 1982 ACM SIGMOD international conference on Management of data (ACM, 1982), pp. 235–245
9.
F. Polat, A. Cosar, R. Alhajj, Semantic information-based alternative plan generation for multiple query optimization. Inform. Sci. 137(1), 103–133 (2001)CrossRefMATH
10.
H.H. Lee, W.S. Lee, Adaptive two-level optimization for selection predicates of multiple continuous queries. J. Intell. Inform. Syst. 39(2), 317–334 (2012)CrossRef
11.
R. Lee, M. Zhou, H. Liao, Request Window: an approach to improve throughput of RDBMS-based data integration system by utilizing data sharing across concurrent distributed queries. in Proceedings of the 33rd international conference on VLDB (2007), pp. 1219–1230
12.
X. Lin, M. Orlowska, An Integer Linear Programming approach to data allocation with the minimum total communication cost in distributed database systems. Inform. Sci. 85(1), 1–10 (1995)CrossRefMathSciNet
13.
G. Nan, M. Li, Energy-efficient query management scheme for a wireless sensor database system. EURASIP J. Wirel. Commun. Netw. (2010)
14.
S.G. Nash, A. Sofer, Linear and Nonlinear Programming, vol. 692 (McGraw-Hill, New York, 1996)
15.
S. Papadomanolakis, A. Ailamaki, An integer linear programming approach to database design. in Data Engineering Workshop, 2007 IEEE 23rd International Conference on (2007), pp. 442–449
16.
J. Rao, K.A. Ross, Reusing invariants: a new strategy for correlated queries. in ACM SIGMOD Record, vol. 27, No. 2, (1998), pp. 37–48
17.
A. Rosenthal, U.S. Chakravarthy, Anatomy of a Modular Multiple Query Optimizer. In VLDB (1988), pp. 230–239
18.
P. Roy, S. Seshadri, S. Sudarshan, S. Bhobe, Efficient and extensible algorithms for multi query optimization. in ACM SIGMOD Record, vol. 29, No. 2, (2000), pp. 249–260
19.
T.K. Sellis, Multiple-query optimization. ACM Trans. Database Syst. (TODS) 13(1), 23–52 (1988)CrossRef
20.
I.H. Toroslu, A. Cosar, Dynamic programming solution for multiple query optimization problem. Inform. Process. Lett. 92(3), 149–155 (2004)CrossRefMATHMathSciNet
21.
E. Wong, K. Youssefi, Decomposition—a strategy for query processing. ACM Trans. Database Syst. (TODS) 1(3), 223–241 (1976)CrossRef
22.
T. Dokeroglu, S.A. Sert, M.S. Cinar, Evolutionary multiobjective query workload optimization of Cloud data warehouses. Sci. World J. (2014)
Metadata
Title
Integer Linear Programming Solution for the Multiple Query Optimization Problem
Authors
Tansel Dokeroglu
Murat Ali Bayır
Ahmet Cosar
Copyright Year
2014
Book
Information Sciences and Systems 2014

Print ISBN: 978-3-319-09464-9

Electronic ISBN: 978-3-319-09465-6

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-09465-6_6

Premium Partner

    Image Credits