Results 1 to 3 of 3
  1. #1
    Join Date
    Nov 2002
    Posts
    21

    query computational complexity

    Can anyone suggest way or resources of how i can calculate the computational complexity of select query? i.e. its order O()

  2. #2
    Join Date
    Sep 2002
    Location
    UK
    Posts
    5,171

    Re: query computational complexity

    Originally posted by Sandro Psaila
    Can anyone suggest way or resources of how i can calculate the computational complexity of select query? i.e. its order O()
    Means little to me - but try searching via Google.

  3. #3
    Join Date
    Oct 2002
    Location
    Baghdad, Iraq
    Posts
    697

    Re: query computational complexity

    Originally posted by Sandro Psaila
    Can anyone suggest way or resources of how i can calculate the computational complexity of select query? i.e. its order O()
    If you mean tools that will take some SQL statement (as well as info about the tables it's referring to) and estimate its complexity, I doubt it. A large reason the relational model exists is to give the DBMS widest possible latitude in picking the best algorithm, where "best" is a tradeoff between space complexity (how much RAM, disk, etc is used) and time complexity. (how much CPU time is used) That is to say that there is no straightforward mapping between the logical database value and its physical implementation.

    So if you were a query planner, you'd probably want to recast the statement in relational algebra. (And you'd probably try many different permutations.) For each operation, you'd have one or two operands. You could work out the worst case, best case and average case number of rows for each operation. In some expressions, for example a series of cumulative restricts, the order is never going to be worse than O(N). In other cases you can cause the complexity to explode, for example by repeatedly performing cartesian products.

    You should have a look at the extensive references in C.J. Date's Introduction to Database Systems, specifically those for chapter 17.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •