Title: SQL query space and time complexity estimation for multidimensional queries

Authors: Hassan Artail, Hadi El Amine, Fehmi Sakkal

Addresses: American University of Beirut, Department of Electrical and Computer Engineering, P.O. Box 11-0236, Riad El-Solh, Beirut 1107 2020, Lebanon. ' American University of Beirut, Department of Electrical and Computer Engineering, P.O. Box 11-0236, Riad El-Solh, Beirut 1107 2020, Lebanon. ' American University of Beirut, Department of Electrical and Computer Engineering, P.O. Box 11-0236, Riad El-Solh, Beirut 1107 2020, Lebanon

Abstract: This paper tackles the issue of estimating database query space and time complexities. Initially, queries without joins are considered and classified into five categories in accordance with complexity (type and number of clauses) in a progressive manner. The storage space and execution time complexity measures for each category are then derived after translating the queries into their algebraic representations and then deriving possible relations that accounts for the different factors (i.e., clauses found in the statement). Joins were then considered and similar complexity expressions were derived. Some experiments were carried out against a database of four tables that were populated using a data generation tool, and involved monitoring the execution time with the aid of a performance monitoring software, so as to give insights into the |join| costs. It is shown that the obtained trends exhibit general agreement with the theoretical expressions for both space and time complexity.

Keywords: SQL queries; query processing; query space; time complexity; SQL databases; complexity analysis; execution time.

DOI: 10.1504/IJIIDS.2008.021448

International Journal of Intelligent Information and Database Systems, 2008 Vol.2 No.4, pp.460 - 480

Published online: 27 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article