SQL query space and time complexity estimation for multidimensional queries. (1st December 2008)

• Record Type: Journal Article
• Authors: Artail, Hassan; El Amine, Hadi; Sakkal, Fehmi
• Is Part Of: International journal of intelligent information and database systems. Volume 2:Number 4(2008)
• Page Start: 460
• Page End: 480
• Publication Date: 2008-12-01
• Subjects: SQL queries -- query processing -- query space -- time complexity -- SQL databases -- complexity analysis -- execution time; Database management -- Computer programs -- Periodicals; Information retrieval -- Computer programs -- Periodicals; Information storage and retrieval systems -- Computer programs -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligent agents (Computer software) -- Periodicals; 006.33
• Languages: English
• ISSNs: 1751-5858

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.