Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
Integer Linear Programming Solution for the Multiple Query Optimization Problem
Date
2014-10-28
Author
Dokeroglu, Tansel
Bayir, Murat Ali
Coşar, Ahmet
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
204
views
0
downloads
Cite This
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.
Subject Keywords
A-star
,
Multiple query optimization
,
Linear programming
URI
https://hdl.handle.net/11511/29953
DOI
https://doi.org/10.1007/978-3-319-09465-6_6
Collections
Graduate School of Natural and Applied Sciences, Conference / Seminar
Suggestions
OpenMETU
Core
Dynamic Programming with Ant Colony Optimization Metaheuristic for Optimization of Distributed Database Queries
Dokeroglu, Tansel; Coşar, Ahmet (2011-09-28)
In this paper, we introduce and evaluate a new query optimization algorithm based on Dynamic Programming (DP) and Ant Colony Optimization (ACO) metaheuristic for distributed database queries. DP algorithm is widely used for relational query optimization, however its memory, and time requirements are very large for the query optimization problem in a distributed database environment which is an NP-hard combinatorial problem. Our aim is to combine the power of DP with heuristic approaches so that we can have ...
Using object-oriented materialized views to answer selection-based complex queries
Alhajj, R; Polat, Faruk (1999-09-01)
Presented in this paper is a model that utilizes existing materialized views to handle a wide range of complex selection-based queries, including linear recursive queries. Such queries are complex because it is almost impossible for naive users to predict the formulation of their predicate expressions. Object variables bound to objects in the result of a query are allowed to appear in the predicate of that query. Also, the predicate definition is extended to make it possible to have in the output only a sub...
Distributed database design with integer linear programming and evolutionary hybrid algorithms
Tosun, Umut; Coşar, Ahmet; Department of Computer Engineering (2013)
The communication costs of remote access and retrieval of table fragments required in the execution of distributed database queries, are the major factors determining the quality of a distributed database design. Data allocation algorithms try to minimize these costs by dividing database tables into horizontal fragments, then assigning each fragment at or near the database sites they are needed more frequently. In this thesis, we propose efficient optimization algorithms for centralized and distributed data...
Improving the performance of Hadoop/Hive by sharing scan and computation tasks
Özal, Serkan; Toroslu, İsmail Hakkı; Doğaç, Asuman; Department of Computer Engineering (2013)
MapReduce is a popular model of executing time-consuming analytical queries as a batch of tasks on large scale data. During simultaneous execution of multiple queries, many oppor- tunities can arise for sharing scan and/or computation tasks. Executing common tasks only once can reduce the total execution time of all queries remarkably. Therefore, we propose to use Multiple Query Optimization (MQO) techniques to improve the overall performance of Hadoop Hive, an open source SQL-based distributed warehouse sy...
Multiple query optimization with depth first branch and bound and dynamic query ordering
Coşar, Ahmet; Lım, Ee Peng; Srıvastava, Jaıdeep (null; 1993-09-01)
In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., a single query can be transformed into a set of closely related database queries. Great benefits can be obtained by executing a group of related queries all together in a single unified multi-plan instead of executing each query separately. In order to achieve this, Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subexpressions, joins, etc.) among a set of query...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
T. Dokeroglu, M. A. Bayir, and A. Coşar, “Integer Linear Programming Solution for the Multiple Query Optimization Problem,” 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/29953.
