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

In article <38q2li$p83@infmx.informix.com> proberts@informix.com (Paul Roberts) writes: > 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". > > 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. I do believe you. > Is this a kind of "datamining", in that we are trying to (a) uncover > regularities in the data and then (b) find the exceptions? > 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 answer is "yes" to (a) above. But once you've isolated your pattern and stored the relationship (department -> setof(course)), a fairly simple SQL query will give you (b). If you're feeling fancy, you can store the relationship as (department -> signature(setof(course)), where signature returns some hash value for the set (Lipton has a paper on "fingerprinting sets" that would work for this). Then a very simple SQL query will get your answer pretty fast, because you've transformed the relationship to be 1-1 instead of 1-n. The problem, though, is not the set-valued nature of the right side of your relationship (though this is awkward to query in SQL). The real problem is *finding* the relationship you desire. There's two subproblems there: (1) crisply defining what you desire, and (2) implementing an efficient retrieval in a relational system. Any easy solution to problem (1) is likely to be only partially satisfactory -- you're going to be forced to choose some statistical notion of "regularity", which may or may not capture everything you really want. Problem (2), in your case, could probably be solved inefficiently with standard SQL, and maybe more efficiently with the kinds of datamining algorithms coming out in the research literature (e.g. the work of Agrawal, et al.) Regards, Joe Hellerstein