SQL Query theory question - single-statement vs multi-statement queries

Question

When I write SQL queries, I find myself often thinking that "there's no way to do this with a single query". When that happens I often turn to stored procedures or multi-statement table-valued functions that use temp tables (of one sort or another) and end up simply combining the results and returning the result table.

I'm wondering if anyone knows, simply as a matter of theory, whether it should be possible to write ANY query that returns a single result set as a single query (not multiple statements). Obviously, I'm ignoring relevant points such as code readability and maintainability, maybe even query performance/efficiency. This is more about theory - can it be done... and don't worry, I certainly don't plan to start forcing myself to write a single-statement query when multi-statement will better suit my purpose in all cases, but it might make me think twice or a little bit longer on whether there is a viable way to get the result from a single query.

I guess a few parameters are in order - I'm thinking of a relational database (such as MS SQL) with tables that follow common best practices (such as all tables having a primary key and so forth).

Note: in order to win 'Accepted Answer' on this, you'll need to provide a definitive proof (reference to web material or something similar.)

Southerly

Before you can answer this question, you need to be a lot more specific on what you mean by "SQL in theory". The SQL used in practice varies between DBMSes and between DBMS versions. You need to standardize on a standard set of SQL constructs. E.g., what types of subqueries do you allow? Furthermore, you may want to abstract away some details, e.g., the most common "SQL query theory", which uses relational calculus or algebra as an abstraction of SQL, treats tables as sets of rows, not ordered lists of rows. – Tightfisted

Answer 1

At least with the a recent version of Oracle is absolutely possible. It has a 'model clause' which makes sql turing complete. ( http://blog.schauderhaft.de/2009/06/18/building-a-turing-engine-in-oracle-sql-using-the-model-clause/ ). Of course this is all with the usual limitation that we don't really have unlimited time and memory.

For a normal sql dialect without these abdominations I don't think it is possible.

A task that I can't see how to implement in 'normal sql' would be: Assume a table with a single column of type integer

For every row 'take the value at the current row and go that many rows back, fetch that value, go that many rows back, and continue until you fetch the same value twice consecutively and return that as the result.'

Isopiestic

Wow very interesting... however it seems to me (if I understand correctly) that although this is a single statement, it's not quite in the spirit of my question in the sense that you have the ability to iterate the result table. I guess I was thinking more along the lines of "set theory". Still, the fact that this achieves Turing-complete status, and the reference to the fact that most SQL (I'm assuming this implies MSSQL) "probably isn't" is good enough for a win, I think, even though I'm still not sure what the end answer to my "real" question is. – Southerly

Answer 2

I believe it is possible. I've worked with very difficult queries, very long queries, and often, it is possible to do it with a single query. But most of the time, it's harder to mantain, so if you do it with a single query, make sure you comment your query carefully.

I've never encountered something that could not be done in a single query.
But sometimes it's best to do it in more than one query.

Memnon

To add some info: at my job, we have databases that the backup exceeds 60 go. We work with very large tables and very large data. For the type of work that we do, the queries can do many pages, so it's often best to do more than one query or to use work tables. – Memnon

I mean that when you write it in your program (i work in C++), you have to scroll down many pages before reaching the end of the query. – Memnon

Answer 3

I can't prove it, but I believe the answer is a cautious yes - provided your database design is done properly. Usually being forced to write multiple statements to get a certain result is a sign that your schema may need some improvements.

Nordic

Answer 4

I'd say "yes" but can't prove it. However, my main thought process:

• Any select should be a set based operation

• Your assumption is that you are dealing with mathematically correct sets (ie normalised correctly)

• Set theory should guarantee it's possible

Other thoughts:

• Multiple SELECT statement often load temp tables/table variables. These can be derived or separated in CTEs.

• Any RBAR processing (for good or bad) now be dealt with CROSS/OUTER APPLY onto derived tables

• UDFs would be classed as "cheating" in this context I feel, because it allows you to put a SELECT into another module rather than in your single one

• No writes allowed in your "before" sequence of DML: this changes state from SELECT to SELECT

• Have you seen some of the code in our shop?

Edit, glossary

• RBAR = Row By Agonising Row
• CTE = Common Table Expression
• UDF = User Defined Function

Edit: APPLY: cheating?

SELECT
    *
FROM
    MyTable1 t1
    CROSS APPLY
    (
        SELECT * FROM MyTable2 t2
        WHERE t1.something = t2.something
    ) t2

Minister

I just read about the 'apply' and it sounds to me as cheating as well. It calls a function which isn't really a SQL entity but implemented in T-SQL, or whatever it is called. – Isopiestic

Answer 5

In theory yes, if you use functions or a torturous maze of OUTER APPLYs or sub-queries; however, for readability and performance, we have always ended up going with temp tables and multi-statement stored procedures.

As someone above commented, this is usually a sign that your data structure is starting to smell; not that it's bad, but that maybe it's time to denormalise for performance reasons (happens to the best of us), or maybe put a denormalised querying layer in front of your normalised "real" data.

Givens