Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!ames!ucbcad!ucbvax!decvax!decwrl!labrea!Shasta!brain
From: brain@Shasta.STANFORD.EDU (Sam Brain)
Newsgroups: comp.databases
Subject: Re: Optimization algorithms
Message-ID: <1024@Shasta.STANFORD.EDU>
Date: Mon, 8-Dec-86 23:55:50 EST
Article-I.D.: Shasta.1024
Posted: Mon Dec  8 23:55:50 1986
Date-Received: Wed, 10-Dec-86 03:03:48 EST
References: <8612010047.AA14252@BORAX.LCS.MIT.EDU> <9768@sri-spam.istc.sri.com>
Distribution: world
Organization: Stanford University
Lines: 27

>   i'd like the generality of grep in my searches, that is,
	...
>   for example, "dan" would match the first names "Dan" and "Daniel", the
>   last name "Danielson", and the company called "Danskin".  i currently
>   key on first and last names, business name, and (at least now) month
>   of birthday to get a quick printout of people who have birthdays
>   this month. 
>   ... I can't figure out
>   how to create an efficient way of finding an index from a partial
>   key short of using a linear search.  perhaps there might be a way in
>   a relational type database.

Since all your examples are fragments at the beginning of the word,
it seems you could create inverted indices, (which are, of course
sorted lexicographically) i.e. ISAM- or B-tree-type structures, one for each
field you want to key on. This would give the added flexibility of saying
things like:

	'find lastname = "Dan*" or firstname = "Ge*"'
			or
	'find lastname = "Dan*" and firstname = "Ge*"'

depending on what you were looking for. Of course you couldn't find
strings of the form "*niel*" etc.

Most DBMSs have inverted indices of one type or another. And haven't I
seen B-tree code on {mod|net}.sources?