Default database / namespace

[Robert Wittams]

Hi, 

Warning: I may be clueless! Don't flame too hard ;-)

I've been reading about eros and KeyKOS for a few days and I am really
excited by the possibilities that eros offers. 

I understand that persistence means that a lot of current uses of the
filesystem in acl based systems are no longer required. But there are
still a lot of situations in which it will be necessary to organise keys
& data, and having a unified namespace is a goal towards which most OSs
seem to be moving. 

Of course as this is not mandated by the eros kernel, any implementation
provided is merely a default and can be removed or ignored (by not
passing the key to access it to any objects that do not need it).

If an object posseses a write key to the namespace (ie it can bind
things in to the namespace), it has a channel to communicate to any
other object which can read the namespace. This must be prevented, so,
for example, a sandboxed domain which wanted access to *a* namespace can
be passed a key to a recently constructed one, or a filtered view of the
"old" namespace. The key would obviously need to be explicitly passed in
all situations. And most native eros programs would never need a
namespace key. 

Having been impressed by the ideas presented by Hans Reiser in this
paper:
http://devlinux.com/projects/reiserfs/whitepaper.html
and also the Microsoft COM/OLE idea of a moniker, 
I propose that the default namespace of eros be flexible enough to
subsume heirarchical, keyword, and relational systems.

Also, it should be possible to stack namespaces, and mount them at any
point within each other.

So, the way I think this could be done:

An interface "namespace" with these operations:
	get(query)         - return an object matching a query. May be a set.
	link(query, key)   - add an association into the database for the key. 
	unlink(query, key) - remove an association for the key. 
			     Need both as multiple objects may be linked 
			     to the same criteria. 
	bind(query, key)   - maybe should be called mount? 
			     Key must be to another namespace. any querys which match go into
this namespace for further searching. Any "link" operation will try to
link from the top down, on any namespaces which have a write key. 
	unbind(query, key) 

	( maybe there needs to be a way to ask which namespaces are bound in
currently,
	  or maybe this comes in the answer to get() ? )


And a set:
	length() - returns length of set, or -1 for unknown length (eg from a
search that hasn't yet finished)
	get(index) - returns a key to an object. 

	( I don't know whether the set should be able to tell you a name for
the object in the database or not...) 
	
Then multiple implementations of this interface can be defined. 

So, for example - user logs in. Standard log in stuff brings up their
user interface, with their namespace. This is persistent like the rest
of eros, so any namespaces previously bound in are still there. So, the
user has these things bound:

/desktop/  - from the users desktop manager. also represented by icons
on the screen.  
/work/     - a capabilty from her employer, bound in - holds things
worked on by her and colleagues
/encyclopedia - an encyclopedia, bound into the system
/linux  - her "legacy" linux filesystem
/accounts - her accounts, held in an RDBMS
/mail - her mail box
/websites/
/websites/imdb - a frontend to the internet movie database
/websites/google - """ to google
/ - a "record" oriented namespace.
/ - a "file" oriented namespace. 
/ - a generic namespace. ( for any keys)


and she does these queries:

/linux/usr/local/bin - returns a set which has the contents of that
directory under linux

/mail/["harry"] - a set of all the mail associated with the word
"harry". Her mail system associates based on mail contents. 

["harry"] - a union of all the things in all the namespaces that are
associated with harry. Eg her mail, a google search, encyclopedia
entries etc. 

Anyway, once you have a key out of the namespace, you check the alleged
key type, and do what you like with it. I think something like
QueryInterface could be very useful here.

So, then she sticks some stuff in the namespace.

She has a key, k1 to a file (it is a stream of bytes) about a recipe.
She goes link("/recipes/yumyum", k1)
Then she goes link("[milk cheese flour]", k1)
Then link("[ cooking-time/45mins ]", k1)

What happens is that the namespace asks each namespace on / to link it
to recipes/yumyum . First it asks the record namespace. The key is not a
record, so it
doesn't add it. Next it asks the file namespace. It is a file, so it is
added. 

The rest of the links are the same, as the file oriented namespace takes
things based on thier alleged type, not on the query. 

In this way, efficient storage of things as either records or byte
streams can be achieved. And legacy systems can be bolted in too. 

The things I am wondering about:
	What is the best format for queries? It might not be a character
string. 
	It might be something like a tuple that could be passed in the data
section of an eros message. Then a library routine could create this
from a string. The advantage of this is that different systems could be
supported - eg a windows name parser, a unix name parser, even an SQL
parser. eek. Also, elements of the tuples could be other keys. Meaning
that parts of names could be arbitrary objects, not just strings. Eg in
a record, another record type. 
	
	Is there enough difference between a set and a namespace to warrant a
seperate interface? It might be best to just return another namespace,
then more querying could be done on that. 

	How do you optimise for disk and memory usage bearing checkpointing in
mind?	Is this (eg the indexes) something for which explicit
journaling/IO may make sense?

Does some kind of transaction model need to be supported? If so, in what
form? It might be best to have another interface for this on record
oriented systems. So you do all your heavy database work with
transactions via that interface, but it is still possible to add in /
view stuff via the namespace interface, which internally would use a
transaction for each change. 

Hope some of this made sense, 
Rob