SQL query space and time complexity estimation for multidimensional queries Online publication date: Thu, 27-Nov-2008
by Hassan Artail, Hadi El Amine, Fehmi Sakkal
International Journal of Intelligent Information and Database Systems (IJIIDS), Vol. 2, No. 4, 2008
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Intelligent Information and Database Systems (IJIIDS):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook