Assignment 4
Distributed: Dec 3 - Student Solutions: Dec 7 - Resolved: Dec 7/9

Information Systems for Business Applications, Harold Boley, Winter 1998

Here some of the material from various lectures is recapitulated and deepened. You should also try to construct and solve your own versions of these and earlier assignments.

a) Define an operator that counts the number of all occurrences of a given item (atom or tuple, ground or non-ground) as a top-level element of a given tuple. (Hint: Try to adapt the recursive structure of repall in opstup.bat.) The operator may either be a function occfun(item,tuple) or a relation occrel(item,tuple,occurrences). For instance, the occfun-function call occfun(oranges,[apples,oranges,bananas,oranges,oranges,peaches]) should return 3, while occrel(oranges,[apples,oranges,bananas,oranges,oranges,peaches],Occ) should bind Occ to 3. In either version, what is the result of a call with the item [_,_] and the tuple [[apples],[apples,oranges],[X,Y],[oranges,peaches],[]]? What happens if the tuple is a variable?

b) Several times we needed a tuple-appending (or -concatenating) function appfun such that, in "..."-notation, appfun([a1,...,aM],[b1,...,bN]) returns the tuple [a1,...,aM,b1,...,bN] of length M+N, (informally, the adjacent brackets "],[" are reduced to the comma). Note that (1), even for N=0, [a1,...,aM|[b1,...,bN]] = [a1,...,aM,b1,...,bN] (informally, the adjacent "|[" and the corresponding "]" are erased), and (2) len([a1,...,aM]) = M is our builtin for efficient tuple-length computation. Now consider the following "..."-less equations about appfun:

  1. appfun([],[]) = []
  2. appfun(K,[]) = K
  3. appfun([],L) = L
  4. appfun([E1],L) = tup(E1|L)
  5. appfun([E1|[]],L) = tup(E1|appfun([],L))
  6. appfun([E1],L) = tup(E1|appfun([],L))
  7. appfun([E1,E2],L) = tup(E1,E2|L)
  8. appfun([E1|[E2]],L) = tup(E1|appfun([E2],L))
  9. appfun([E1,E2],L) = tup(E1|appfun([E2],L))
  10. appfun([E1,E2,E3],L) = tup(E1,E2,E3|L)
  11. appfun([E1|[E2,E3]],L) = tup(E1|appfun([E2,E3],L))
  12. appfun([E1,E2,E3],L) = tup(E1|appfun([E2,E3],L))
  13. ...
  14. appfun([H|R],L) = tup(H|appfun(R,L))
  15. appfun(tup(H|R),L) = tup(H|appfun(R,L))
  16. tup(appfun(K,L)) = appfun(tup(appfun(K,L)|[]),tup())
  17. appfun(J,appfun(K,L)) = appfun(appfun(J,K),L)
  18. len(appfun(K,L)) = len(appfun(L,K))
  19. len(appfun(K,L)) = +(len(K),len(L))
  20. len(appfun(J,appfun(K,L))) = +(len(J),len(K),len(L))
  21. [] = appfun([],[])
  22. . . .
Which of these equations are true "axioms" or "theorems" about tuple appending? Which subset of them is (minimally) necessary as defining "axioms" of tuple appending (e.g. via ":&"-assertions in RelFun)? Which "non-axiom theorems" are subsumed by (i.e., a special case of) the "axioms" of appending? Which "theorems", when applied from left to right, could essentially enhance the efficiency of expressions involving appfun?

Define a tuple-appending relation apprel such that apprel([a1,...,aM],[b1,...,bN],App) binds App to [a1,...,aM,b1,...,bN]. What is the (deterministic or non-deterministic?) result of an "inverse" call of the form apprel(TupA,TupB,[a1,...,aM,b1,...,bN])? What is the value of len(tupof(apprel(TupA,TupB,[apples,bananas,oranges,peaches])))?

c) In "A comparison of SQL and RelFun" (sql.script) we used the following member definition:

az member(X,[X|_])!.
az member(X,[_|Y]) :- member(X,Y).
The "!" makes the member relation deterministic by `cutting' computation after its first clause (a fact), so that the second clause (a rule) cannot be used in the successful case that the "search item" X also appears as the first element of the "searched tuple" [X|_]. Reformulate this as an equivalent definition using naf (our negation-as-failure primitive) instead of "!" (the cut symbol). (Hint: First replace one anonymous variable "_" by a named one such as U). Change the member definition into a non-deterministic version; compare and explain the difference for a ground call (containing no variable) and for the non-ground call (containing the variable What) member(What,[i,s,b,a]).

Which member version should be used for the RelFun query below such that it becomes equivalent to the SQL query below? Would the non-deterministic member version change any query result of the dialog sql.bat?

% SQL:
% SELECT Position
% FROM Employee_statistics
% WHERE Salary IN (75000,65000,45000);

% RelFun:
Formulate the above equivalent queries as an equivalent English sentence. Can, for the database given by sql.bat, the above SQL query be rewritten using BETWEEN instead of IN?

d) The fragment of the NUTRIMINE information system on pages 23-28 of Knowledge Bases in the World Wide Web consists of a purely relational and a mixed functional-relational version. Which clauses would have to be changed to produce a purely functional version? `Functionalize' these clauses. (Hint: Rewrite facts as constantly true functions and 1-premise ":-"-rules as ":&"-equations.)

Execute nutrimine.bat. Enrich the call nutramount(strawberry) by a suitably parameterized qsort call such that the nutrient-amount pairs are ordered according to decreasing mg/kg amounts.