Re: Things that are hard to do in SQL (datamining?)

This is quite a long answer to a rather long question... >From: proberts@informix.com (Paul Roberts) >Subject: Things that are hard to do in SQL (datamining?) >Date: 28 Oct 1994 05:36:50 GMT >X-Informix-List-Id: <news.9532> > >I seem to keep re-encountering a certain kind of problem for which, >as far as I can see, it particularly hard to attack with SQL. I was >wondering whether anyone else has any deep - or shallow - insights >about it. > >For instance, imagine that we had a table which associated each >employee with a department, and another table which told us which >courses each employee has taken: > >-- EMPLOYEE -- -- ATTENDED -- > >emp_id dept emp_id course_id date_taken >------ ---- ------ --------- ---------- > > 1 FIN 2 AA 01/01/93 > 2 SALES 2 AD 01/01/94 > 3 SALES 3 AA 01/01/92 > 4 MIS 1 AA 01/01/92 > 5 FIN ..... > 6 FIN > ..... > >Now, someone comes along and says "You can see that the Finance (FIN) >people all get to attend pretty much the same classes eventually. In >fact it generally works out that all the people in any given department >mostly attend the same classes in the end. We'd like you to draw up a >list of who should attend which class in order to cover material they >have missed. That is, who hasn't attended a class that most of the people >in their department have attended?" > >And to prevent it being too easy, there is overlap: maybe FIN and >MIS people tend to take "principles of accounting", MIS and SALES >tend to take "negotiating to Yes!". And there may be exceptions: >just because employee #7 took "how not to harrass coworkers" doesn't >mean that everyone is his department ought to take the same course. Oh good; I'd hate to think it was simple:-) >Crucially, there is no table that relates DEPARTMENT to COURSE. We >are expected to figure out this relationship by looking at the data in >the two tables given and seeing "what's normal". This is true, but there is a way of working out which courses are used by members of which departments, namely by joining the Employe and Attended relations. For (lots) more on this, see below. >I don't know whether this sounds like a very contrived problem, and >whether you'll believe me when I say that it keeps coming up. A similar >situation is "All our products come in a number of types (development, >runtime, maint, etc). You'd expect products in the same product line >to all come in the same set of types. So, locate missing product >types" - e.g. `hey, where is runtime maintenance for I-SQL V1.2.3.4 ; >all the other versions of I-SQL have a runtime maintenance!' It doesn't sound too contrived to me. It sounds pretty plausible, in fact. >Is this a kind of "datamining", in that we are trying to (a) uncover >regularities in the data and then (b) find the exceptions? I would say yes, it was. >The basic problem, it seems to me, is that we are really comparing >the relation between an entity (an employee, a software product) >and a SET of items (courses taken, types-available), when the data >given are relations between those entities and individual items. > >The problem is perhaps too vaguely stated to ask for "the solution", >but I curious as to whether others have come across the same sort >of thing, and if so do you have any insights. This problems demonstrates that humans are wonderfully good at perceiving patterns, and that it is quite difficult to express these patterns for computers to understand. Consider the problem Paul posed. We need a list of courses attended by people in departments, with a count of the number of times the course has been attended: -- Query 1 SELECT UNIQUE A.Dept, A.Course_id FROM Employee E, Attended A WHERE E.Dept = A.Dept INTO TEMP Dept_Courses; We now need to screen out the non-obligatory courses. Presumably we have a table which defines these: NON_OBLIGATORY dept course_id MIS SH -- how not to harrass coworkers So, now we can derive a list of course which everyone in a given department should attend. -- Query 2 SELECT D.Dept_id, D.Course_id FROM Dept_Course D WHERE D.Course_id NOT IN (SELECT N.Course_id FROM Non_Obligatory N WHERE N.Dept = D.Dept) INTO TEMP Mandatory_Courses; Of course, this assumes that there is no obligatory course C for any department D which no employee of D has attended course C. If there are such courses, we need a table which defines these too. For sake of simplicity, such courses will be ignored. Now you can start analysing each employee in turn. We need to identify the employees who have not attended all the mandatory courses for the department they work in. -- Query 3 SELECT E.Emp_id FROM Employee E WHERE EXISTS (SELECT * FROM Mandatory_Courses M1 WHERE M1.Course_id NOT IN (SELECT M2.Course_id FROM Mandatory_Courses M2, Attended A WHERE A.Emp_id = E.Emp_id AND M2.Dept_id = E.Dept_id ) ) This can be translated as: list all the employees for whom there is some mandatory course for the department which they work in which is not in the list of courses that the employee has attended. This sort of correlated sub-query is designed to give optimizers headaches. Actually, you probably want to know which courses those employees have not attended: -- Query 4 SELECT E.Emp_id, M1.Course_id FROM Mandatory_Courses M1, Employee E WHERE M1.Dept_id = E.Dept_id AND M1.Course_id NOT IN (SELECT M2.Course_id FROM Mandatory_Courses M2, Attended A WHERE A.Emp_id = E.Emp_id AND M2.Dept_id = E.Dept_id ) This has the side effect of being simpler to process, and shows how Query 3 can be simplified into Query 5: -- Query 5 SELECT UNIQUE E.Emp_id FROM Mandatory_Courses M1, Employee E WHERE M1.Dept_id = E.Dept_id AND M1.Course_id NOT IN (SELECT M2.Course_id FROM Mandatory_Courses M2, Attended A WHERE A.Emp_id = E.Emp_id AND M2.Dept_id = E.Dept_id ) Turning back to the more general issue: is there any way of automating such analyses? I rather suspect not, especially with existing systems. To be able to automate the analysis of "list the employees who have not attended all the mandatory courses for members of the department in which they work, and list the courses which each such employee has not attended", you would