Home » forums » LtU Forum

Explaining database query or constraint-satisfaction failures

Let's say that you have a logic database (or a relational database, or a constraint store, etc.) and the user issues a query that returns no results. It would be nice to be able to explain to the user why the query failed, perhaps identifying some subset of clauses that are mutually unsatisfiable or suggesting modified constraints. It looks to me like most of the work in this area takes the same approach as this paper by Parke Godfrey, finding maximal subqueries that succeed and minimal ones that fail and proceeding from there. (Judging from the citations to Godfrey's paper, this has been a hot topic in recommendation systems lately; I am surprised that it hasn't, as far as I can tell, caught on more generally in the constraint or logic programming communities -- although there may be some related work using different names for the same concepts.)

The capacity to explain failures and guide the user to a successful query seems awfully useful. I'm wondering if anyone is aware of (1) any other approaches for suggesting modifications to failing queries, or (2) any general-purpose constraint solving toolkits or logic programming systems that offer this functionality.

By Will Benton at 2009-07-02 14:06 | LtU Forum | previous forum topic | next forum topic | other blogs | 5749 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

In a type-inference setting

Bastiaan Heeren's thesis on Top Quality Type Error Messages covers the constraint-satisfaction portion of this question fairly thoroughly in a context likely to be of interest to LtU readers.

By Douglas McClean at Thu, 2009-07-02 14:15 | login or register to post comments

Thanks!

I am also interested in the type-inference context, so this is doubly useful.

By Will Benton at Sun, 2009-07-05 19:35 | login or register to post comments

Explanation-based Constraint Programming

This may be related to Explanation-based Constraint Programming, which computes explanation during the constraint solving process, an explanantion (or nogood) being "a subset of the current constraints system of the problem that, left alone, leads to a contradiction."

By pcdavid at Thu, 2009-07-02 17:38 | login or register to post comments

I think it is

The concept of the minimal failing subquery (from Godfrey's paper and related work) is related to explanation-based constraint programming, I think. I was not aware of this work; thanks for the pointer!

By Will Benton at Sun, 2009-07-05 19:37 | login or register to post comments

Logic Breakdown

I would imagine the query (SQL, if you will) must be broken down into steps much like a debugger can break down high level language constructs into individual op-codes. We humans do this logic breakdown when debugging SQL; removing joins until the problem has been isolated. This is eerily similar to what we humans do when we lack a debugger, or even a way to print out values: cutting the code in half, and in half again, until the problem is isolated.

By klahnako at Sun, 2009-07-05 12:54 | login or register to post comments

Zeller's Delta Debugging method: general technique

http://www.google.com/search?q=delta+debugging

By Z-Bo at Fri, 2009-07-10 18:33 | login or register to post comments