MUD relevant references (was: Re: [MUD-Dev] The grass is always greener...)

Sat Dec 25 02:32:08 CET 1999

"Bruce Mitchener, Jr." wrote:
> Ola Fosheim Gr=F8stad wrote:
> >If there are other list
> >members who feel like getting up to date on database/relation/OO resea=
rch,
> >then maybe we could spawn off a little short term project, ending up w=
ith a
> >survey-paper beneficial to the mudding community?
>=20
> I seem to recall suggesting this type of thing back in the DevMUD days.=
 :)
> That suggestion went exactly nowhere.

Well, I am not going to repeat what I suggested back in the DevMUD days! =
>;)

> That said, on some of these types of
> topics, I'm learning about them for my current project to try and make =
some
> decent decisions on things.  I'm just not into writing papers on that
> research due to lack of time and no real demand.

Well, I didn't mean a peer-reviewed paper published in some fancy journal.
Anyway, a list of references and maybe a short evaluation of their releva=
nce
could be helpful.

> The people doing this type
> of server often are already willing to do the research.  Those unwillin=
g to
> do the research tend to not be doing the type of server that might requ=
ire
> that research.  I've probably insulted any number of people now.

I am of the type that is willing to do the research, but unwilling to
implement it until I really know what I want. Which I still don't. :) I
think I know which direction I am ready to move though.

> I'm open to collaborating with people who are skilled in these areas th=
ough.

What kind of collaboration?  I am not skilled.  That's why I am currently
reading journal papers!

Some context: I basically want a flexible MUD.  I don't want a design to =
be
made in concrete, so I want softer building materials.  I think what I mi=
ght
want to do in the long run is to move towards some kind of flexible E-R
(entity-relationship) model, with some kind of inference engine on top. T=
he
current plan is to look at the possibilities and then get down to earth f=
or
a while...

One issue, if you want flexibility, is to not be too dependent on the
representation of state (that is variables, objects etc). This may be
achieved with heavy functional encapsulation and reuse of prior calculate=
d
expressions for performace reasons (one possiblity is to use hashed
lookups).  Although I've always been facinated by the esthetical aspects =
of
functional programming, I have little actual experience as imperative
programming and OO feels more natural for most problems. Nevertheless, I
decided to browse the Haskell documents, in which I found a paper on
programmer efficiency. Haskell did reasonably well, but something called
Relational LISP did better. The Haskell-loving authors attributed this to
prior training. I got curious about this, but was unable to find much on
Relational LISP on the net. I found something called AP5:

    AP5 is an extension to commonlisp which allows users to
    "program" at a more "specificational" level. By this we mean that
    it allows you to focus more on what you want the machine to do
    and less on the details of how. AP5 is a compromise between
    lisp and the gist specification language.

Which, after browsing the docs, might not be exactly what I want, but the=
n
again, I am not quite sure exactly what I want. Or rather, I may know
exactly what I want, but I don't know if it is feasible or how to impleme=
nt
it with reasonable performance. So for the past couple of weeks I have sp=
ent
some of my spare time with the last few years of issues from journals
published by Springer Verlag, and I have also peeked at some of the ACM
journals. Most of them are too narrow or too far from having practical va=
lue
of course. A few have peeked some interest in me though:

--------

"Deductive Database Languages: Problems and Solutions", MENGCHI LIU,
University of Regina, ACM Computing Surveys, Vol. 31, No. 1, March 1999

Abstract: Deductive databases result from the integration of relational
database and logic programming techniques. However, significant problems
remain inherent in this simple synthesis from the language point of view.=
 In
this paper, we discuss these problems from four different aspects: comple=
x
values, object orientation, higher-orderness, and updates. In each case, =
we
examine four typical languages that
address the corresponding issues.

My comment:
As this is a recent survey it may be an invaluable timesaver. A language
called ROL (Rule-based Object Language) peeked my intersts, but I haven't
had time to look up the reference and look more closely at it yet. None o=
f
the languages were exactly what you would want to build a MUD with of
course.

--------
"The State of Change: A Survey"
Anthony J. Bonner 1 and Michael Kifer 2
in B. Freitag et al. (Eds.): Transactions and Change in Logic DBs, LNCS
1472, pp. 1{36, 1998. (Springer-Verlag)

Abstract: Updates are a crucial component of any database program-
ming language. Even the simplest database transactions, such as with-
drawal from a bank account, require updates. Unfortunately, updates are
not accounted for by the classical Horn semantics of logic programs and
deductive databases, which limits their usefulness in real-world applica-
tions. As a short-term practical solution, logic programming languages
have resorted to handling updates using ad hoc operators without a log-
ical semantics. A great many works have been dedicated to developing
logical theories in which the state of the underlying database can evolve
with time. Many of these theories were developed with speci=0Cc applica-
tions in mind, such as reasoning about actions, database transactions,
program veri=0Ccation, etc. As a result, the di=0Berent approaches have d=
if-
ferent strengths and weaknesses. In this survey, we review a number of
these works, discuss their application domains, and highlight their stron=
g
and weak points.

My comment:
I am going to force myself to read this. Promise!  =3D8-X

--------

"Randomized Binary Search Trees"
CONRADO MART =B4 INEZ AND SALVADOR ROURA
Universitat Polite `cnica de Catalunya, Barcelona, Catalonia, Spain
Journal of the ACM, Vol. 45, No. 2, March 1998, pp. 288 =96323.

Abstract: In this paper, we present randomized algorithms over binary sea=
rch
trees such that: (a) the insertion of a set of keys, in any fixed order,
into an initially empty tree always produces a random binary search tree;
(b) the deletion of any key from a random binary search tree results in a
random binary search tree; (c) the random choices made by the algorithms =
are
based upon the sizes of the subtrees of the tree; this implies that we ca=
n
support accesses by rank without additional storage requirements or
modification of the data structures; and (d) the cost of any elementary
operation, measured as the number of visited nodes, is the same as the
expected cost of its standard deterministic counterpart; hence, all searc=
h
and update operations have guaranteed expected cost 2(log n), but now
irrespective of any assumption on the input distribution.

My comment:
I guess this needs no comment. Except it is amazing that they have
improvemed something as basic as this as late as 1998. I might actually w=
ant
to use it.

--------

"An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed
Dimensions"
SUNIL ARYA & al.
Journal of the ACM, Vol. 45, No. 6, November 1998, pp. 891=96923.

"Undirected Single-Source Shortest Paths with Positive
Integer Weights in Linear Time"
MIKKEL THORUP
Journal of the ACM, vol. 46, No. 3, May 1999, pp. 362=96394.

My comment:
I doubt that I will ever need their approaches, but they may be worth a
peek. Even linear time may be expensive for a mud.

--------

Active Database Systems
NORMAN W. PATON AND OSCAR DI =B4 AZ
ACM Computing Surveys, Vol. 31, No. 1, March 1999

Active database systems support mechanisms that enable them to respond
automatically to events that are taking place either inside or outside th=
e
database
system itself. Considerable effort has been directed towards improving
understanding of such systems in recent years, and many different proposa=
ls
have
been made and applications suggested. This high level of activity has not
yielded a
single agreed-upon standard approach to the integration of active
functionality
with conventional database systems, but has led to improved understanding=
 of
active behavior description languages, execution models, and architecture=
s.
This
survey presents the fundamental characteristics of active database system=
s,
describes a collection of representative systems within a common framewor=
k,
considers the consequences for implementations of certain design decision=
s,
and
discusses tools for developing active applications.

My comment:
If I was writing a generic database then this would have been more useful
than it apparently is to me right now. As far as I can tell seems to be v=
ery
much influenced by prior practice. It may be a resource for ideas though.

--------

"Index nesting =96 an efficient approach to indexing in object-oriented
databases"
Beng Chin Ooi 1 , Jiawei Han 2 , Hongjun Lu 1 , Kian Lee Tan 1
The VLDB Journal (1996) 5: 215=96228

My comment:
Sounded more interesting than it was, but I am not very disk centric. If =
you
intend to use B+-trees and such, yes maybe you should look at it. This is
basically about "H-trees" (Hierarchical trees) which affords indexing of
subclasses and such.

--------

"Conceptual classes and system classes in object databases"
Elvira Locuratolo, Fausto Rabitti
Acta Informatica 35, 181=96210 (1998)

My comment:
If your design involves multiple inheritance, but you need single
inheritance in the implementation for performance issues. Then this might=
 be
worth peeking at.

--------

"Garbage collection in object-oriented databases using transactional cycl=
ic
reference counting"
P. Roy 1 , S. Seshadri 1 , A. Silberschatz 2 , S. Sudarshan 1 , S. Ashwin
1;?
The VLDB Journal (1998) 7: 179=96193

My comment:
Interesting reading for me as my knowledge about garbagecollection is
marginal. As often is the case with academic papers: if you don't want th=
e
paper, then maybe you want their references.

--------

"Byzantine quorum systems"
Dahlia Malkhi, Michael Reiter
AT&T Labs =96 Research
Distrib. Comput. (1998) 11: 203=96213

My comment:
Fault tolerant distribution is really not my top priority, but somebody o=
n
the list may have use for it...

-- =20
Ola Fosheim Groestad,Norway      http://www.notam.uio.no/~olagr/

_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev