home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / database / theory / 395 < prev    next >
Encoding:
Text File  |  1992-08-26  |  2.8 KB  |  67 lines
  1. Newsgroups: comp.databases.theory
  2. Path: sparky!uunet!mcsun!sun4nl!wn1.sci.kun.nl!cs.kun.nl!markjan
  3. From: markjan@cs.kun.nl (Mark-Jan Nederhof)
  4. Subject: Representing unions of Cartesian products
  5. Message-ID: <1992Aug26.152708.12949@sci.kun.nl>
  6. Sender: news@sci.kun.nl (NUnet News Owner)
  7. Organization: University of Nijmegen, The Netherlands
  8. Date: Wed, 26 Aug 1992 15:27:08 GMT
  9. Lines: 56
  10.  
  11.  
  12. I am looking for an efficient way to store and manipulate unions of Cartesian
  13. products. 
  14.  
  15. The application domain is abstract evaluation of certain 
  16. programs (e.g.  datalog programs) and analysis of formal grammars 
  17. (context-free grammars extended with features/parameters over a finite domain).
  18.  
  19. Our goal is to determine the set of parameters with which a
  20. nonterminal can generate a terminal string. If this is done by means of
  21. bottom-up analysis then we need the following operations:
  22.  
  23. -For two or more sets of tuples of the form A_1 * A_2 * ... * A_n, 
  24. for fixed n, we have to compute the union in an efficient form.
  25. (The operator * denotes the Cartesian product.)
  26. Here the sets A_i consist of atomic values.
  27.  
  28. -For two unions of Cartesian products in such an efficient form, call
  29. them C_1 and C_2, we have to compute a third set C_3 in the same form
  30. which represents C_1 - C_2.
  31. (The operator - denotes the subtraction of sets of tuples.)
  32.  
  33. -Let us consider two unions of Cartesian products in such an efficient 
  34. form, call them again C_1 and C_2. We now have to compute the set C_3
  35. which represents the set of tuples
  36. {(a_1, a_2, ..., a_n) | (b_1, ..., b_m) <- C_1 AND
  37.                         (c_1, ..., c_k) <- C_2 AND
  38.                          R (a_1, ..., a_n, b_1, ..., b_m, c_1, ..., c_k)},
  39. where R is some relation which for some fixed pairs of its arguments says
  40. that they should have the same value. 
  41. (The operator <- denotes inclusion.)
  42. This operation would be needed in case of a grammar rule with two
  43. members (with m and k parameters respectively; R is determined by 
  44. ``consistent substitution''). 
  45. You can generalise this to arbitrary grammar rules.
  46.  
  47.  
  48. This query is inspired by two things:
  49. -The sets of atomic values are typically too big to represent sets of
  50. tuples in a naive way by one element for every tuple.
  51. -When the union of sets of the form A_1 * A_2 * ... * A_n is computed
  52. then very often these sets overlap, and are even ``almost the same but not
  53. quite''.
  54.  
  55. At this moment I am using a representation where a union of Cartesian
  56. products is transformed into another such that the Cartesian products do
  57. no longer overlap (i.e. they have no tuples in common).
  58. If possible I merge two Cartesian products into one.
  59. These transformations are however rather expensive.
  60. Does anyone have a better suggestion? references to papers?
  61.  
  62. I suggest follow-up at comp.compression
  63.  
  64. Mark-Jan Nederhof
  65. University of Nijmegen
  66. The Netherlands
  67.