Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!comp.vuw.ac.nz!steve
From: steve@comp.vuw.ac.nz (Steve Cassidy)
Newsgroups: comp.lang.prolog
Subject: Partial Orders
Message-ID: <1991Feb27.032403.23920@comp.vuw.ac.nz>
Date: 27 Feb 91 03:24:03 GMT
Sender: news@comp.vuw.ac.nz (News Admin)
Organization: Dept. of Comp. Sci., Victoria Uni. of Wellington, New Zealand.
Lines: 39
Nntp-Posting-Host: climie.comp.vuw.ac.nz


I need some help in finding an appropriate representation for
my data. I am storing a set of objects (they are, in fact, rules
for translating text to speech) for which I have an ordering
relation (generality -- the rule applies to more pieces of text) which
defines only a partial ordering on the objects (eg. x>y -- yes; 
x>z -- dunno; x>w -- no).

I need to do three operations: 
  'traverse' -- look at the least general rule first, and so on
                until a match is found (ie maybe not to the end)
  insert -- insert a new object into the partial ordering
  delete -- delete an object from the partial ordering

'traverse' is done more frequently than insert and delete but
all are done quite often.  There will be between five and fifty
objects in each partial ordering. The test for ordering is 
relatively expensive in this case as it requires a match of the 
two rules.

It seems that to do insert I need to compare the new object with
all existing objects to find its place in the ordering, is there
any way that I can avoid doing this? (for instance, if I know that
x>y I know I don't have to compare x with anything smaller than y -
but can I take advantage of this?)

So, is there an efficient way of representing this as a prolog
datastucture? I would prefer to do updates without copying (a la
difference lists), but be able to 'garbage-collect' deleted
items (probably by copying) every now and then.

Thanks,

Steve Cassidy

Computer Science,                     steve@comp.vuw.ac.nz
Victoria University of Wellington,    ====================
Box 600,                              Voice:  +64 4 715328
Wellington, New Zealand.              Fax:    +64 4 712070