Inter-Office MemorandumToInterest ListDateApril 2, 1982FromRick CattellLocationPalo AltoSubjectDatabase Application GoalsOrganizationCSLfor calendar year 1982XEROX Filed on: [Indigo]Doc>DBApplications.memo, .pressIntroductionThis is a summary of my plans for the Cedar database system and its applications this year, toorganize my thoughts and to get some feedback and ideas.My short-term goal is to test the functionality of CedarDB and to demonstrate it to the CSLaudience. The underlying goal is to generate enough interest to recruit manpower for otherdatabase applications and, more importantly, manpower for basic database work that is needed toadequately support database applications. My long-term goal is interesting database reasearch inCSL.The vehicle we chose for an initial application is the message handling system Walnut. I will brieflydescribe the design of Walnut, as an example of an application design and to illustrate applicationneeds. After that we will discuss Cedar database applications in general.Walnut phase oneLet's call Walnut 1.0 the version of Walnut that Willie-Sue Haugeland and I want to have generallyusable by June. Walnut 1.0 provides four kinds of Cedar Viewers visible to the user:1.Control window: This window is the one that appears when Walnut is started. Itprovides menu commands to fetch new mail, create a new message form (item 4 below)and create a new "mail file" in the Laurel sense (item 2 below, which we call a messageset). The control window also reports when new mail is available, the user's password isinvalid, or any error is recognized by the Walnut system.2.Message-set display window: This window roughly corresponds to the top window of thethree in Laurel. It displays a list of messages, their senders, dates, and subjects. LikeLaurel, there is a special active message set for each user into which new mail is initiallyinserted. This viewer for this message set is automatically put up, along with the Walnutcontrol window, when Walnut is started. Unlike Laurel, one may have many message setson the screen at the same time. Pointing at one of the messages and red-buttoningproduces an instance of item 3 below, a message displayer. A menu of commands at thetop allow adding and deleting messages from the message set, as well as the standardviewers commands (Grow, Destroy, etc.).3.Message display window: This window roughly corresponds to the middle window inLaurel. It displays a message in the database. The menu of commands at the top includeAnswer and Forward, which produce an appropriately initialized instance of a messageform (item 4 below), DeleteMsg, which deletes the message itself and removes it from allmessage sets, and the standard viewers commands. The message display window, like]gpi c8q]rX -q7Br ]q]r -q7Br Yq]r-q 7Br]WSsr M; Gt Dr^ C@8 @P >Q = R ;T : 660 5U>% 3J 0t -zrI +U (u r+'FC%8u$>rO"9 ur: 1*J<~D3v9Dn' Cur9%3 ;L 9 3R  =_.Database Application Goals2Laurel, does not allow editing. Unlike Laurel, the user can point and red-button amessage field to see a database item named there. For example, selecting the "In-Reply-To" field causes the message to which this replied to be displayed (another messagedisplay window). Selecting the "Subject" or "Message-Set" items causes thecorresponding subjects or message sets to be displayed (which enumerate messages on thatsubject or in that message set, which can in turn be selected). Selecting persons in the"To", "From", and "cc" fields causes the person to be displayed (phone number, officenumber, picture, or whatever the database happens to contain). I will discuss this "pointto see it" idea in the next section, on the Squirrel system.4.Message editor window: This window roughly corresponds to the bottom window inLaurel. It displays a message form which the user can edit with Tioga. Some of thefields will be initialized according to whether the message editor window was created bythe "Answer", "Forward", or "New Form" commands. The message editor window wasdesigned to be almost independent of the rest of Walnut, so that we could make a stand-alone tool for sending messages. Its commands include "Send" and "File"; the lattersimply puts the message into the database without sending it, e.g. for the user's messagesto himself (this feature is disabled for the stand-alone version). Walnut also includes a mechanism for logging all user operations on messages and message sets, andreplaying the log if some hardware or software failure destroys the database. This feature isprimarily necessary due to shortcomings of CedarDB:1.We have no reason to believe CedarDB will be reliable enough to entrust with one's mailon a long-term basis. For that matter, we have no reason to believe that Walnut or therest of Cedar will be reliable enough for routine mail handling, either, since thecomponents are experimental and not always protected from one another. 2.CedarDB does not currently deal efficiently with very large character strings, such as onemight encounter in the bodies of messages. We therefore store pointers to messagebodies in the log file rather than the message bodies themselves in the database. When one or both of these shortcomings is remedied, the need for the log mechanism will probablydisappear.The Walnut log replay program, due to clever design of the log format to be upward compatiblewith Laurel mail file format, can also double as a mechanism to read Laurel mail files into adatabase.Unfortunately, the log has its drawbacks: it will grow without bound as the user reads messages,even if they have been deleted. This is particularly a problem when users delete an order ofmagnitude more messages than they keep, as the old messages still exist in the log. A dumpprogram is necessary to periodically dump the database into the log, discarding the deletedmessages. We may also find it necessary to implement a special optimization, that truncates the logfile after every user session.There are other difficulties in implementing Walnut. Two major ones are a result of itsimplementation as multiple processes:1.Portions of Walnut may asynchronously call the CedarDB, CedarGV, and Viewerspackages. In some cases it is not clear where monitors should best be inserted to avoidanomolous behavior. I want to be able to run more than one database application at atime, which suggests that the DBView interface to CedarDB will have to be thesynchronization point. Although for independent reasons we are making most databaseaccess in Walnut go through a single interface where synchronization could be done, itappears to be about as hard to do synchronization there as DBView. Unless a bettersolution comes along, I therefore propose to do the synchronization in DBView. frGb/$`I_2!][\:\6"ZRY2#W4&U< Rur8QN>O>NFOL@K> FI=H6D E $> C^ B3 >5"=SP;@:KH 70*554&+ 0@ /h ,<] *K )4 & >" $] #J !} Q +9 t IX % D"6U 90ur; 5 N =\UmDatabase Application Goals32.When one component of Walnut modifies the database, e.g. a message is removed from amessage set, other component's displays may be rendered invalid. This problem does notarise in Laurel since only one window of each type is allowed. It looks as though anysolution to this problem will eventually be forced to handle the general case of notifyingall database windows of the update. I therefore propose to add this notification facility toSquirrel, which already keeps a list of application viewers on the database. Walnut phase one is partially implemented at the time of this writing. We expect to have all of thebasic features implemented and reliable enough for wide use (but no wider than Cedar!) by June.We have deferred our less modest aspirations to Walnut phase two, which is described later.Squirrel phase oneSquirrel is a package to make database applications easier to build, and to make multiple databaseapplications act in an integrated way from the user's point of view.The development of Squirrel has been broken into two phases: phase one, largely completed inJanuary 1982, which provides the basic facilities crucial to the development of Walnut; and phasetwo, to which we deferred functions less important to getting Walnut phase one to a minimallyusable state.Squirrel provides integration of database applications in two ways:1.CedarDB currently allows only one database open at a time. Squirrel opens the database,and notifies application programs sharing the database when it is closed or re-opened.Also, application programs are notified when a change is made to the database, to allowthem to update their data structures or screen display.3.Squirrel makes it easy for applications to follow a uniform user interface paradigm, inwhich the user sees one Cedar Viewer on the screen per database entity, an object-oriented menu of commands upon a database entity, and a consistent interpretation ofuser selections on the screen. Squirrel recognizes three primary types of application viewers: displayers, editors, and queryers. Adisplayer displays a database entity, provides a menu of commands upon it, and shows theinformation the database contains about the entity. For example, for a message displayer, themessage's header and body would be displayed, along with commands such as Answer, Forward,and Delete. An editor looks much like a displayer, but allows the user to modify the informationabout the entity, and usually has a different set of commands. For example, a message editor iscreated in response to a NewForm or Answer command; the user fills in the fields and invokes themessage editor's Send or File command. A queryer also looks like a displayer and editor, but theuser may fill in the fields with values, boolean expressions of values, or other application-interpretedinformation; the queryer represents all entities in its domain which satisfy the constraints. Whenthe user invokes the query, the entities satisfying it are displayed and may be browsed or printed. A Squirrel window on the screen provides the user application-independent database functions, suchas commiting or aborting a transaction, dumping or loading the database, or erasing portions of thedatabase. The Squirrel window also allows the user to explicit invoke a displayer, editor, or queryeron a particular entity type (a domain). If no application has registered itself for the given domain,Squirrel provides a default application-independent displayer, editor, and queryer, the Palmbrowser/query system. Squirrel and Palm have proven indispensible in debugging applicationprograms, as there is no other simple way to examine and modify the database a program is using.The Palm facilities have also completely obviated the need for some application programs. Forexample, for some personal databases (a wine database, and a database of phone numbers andaddresses) we have found the Palm tools not only adequate but quite useful. frG bM`S_5!]<\Q ZN W^` U2- RG Ot LXrP JD G\ F$<% D P C ?C <*.;AK 9=897 4:W2512)+/ ,@u rurur *urF ){O '; &sur; $-3 #j7) !*ur bh 30 ZO /(: \ 'f urA   K (3  T K ,. K C>[lDatabase Application Goals4In summary, Squirrel provides the application program:1.a library of handy procedures to set up Viewers, particularly those that fit the standardparadigm,2.a library of handy procedures for database access, again particularly for using thestandardized paradigm,3.a central registration mechanism for coordinating opening and closing of the database,database updates, and calls from one application to another dealing with an entity theformer has no mechanism to deal with, and4.application-independent tools for debugging, dumping, loading, editing, and viewingdatabases. Cedar DBMSThe CedarDB system of 1Q81 had proven somewhat lacking in two aspects: (1) the performance ofthe underlying file system, Juniper, and (2) the machinery each application needed on top ofCedarDB (to do adequate integrity checking and their routine data operations). Alpine runningunder CedarDB is designed to remedy the first problem; the DBView level running on top ofCedarDB is designed to remedy the second.The development of the DBView interface to CedarDB has been broken into two phases in afashion similar to Squirrel. The first phase, which includes all of the design save two more complexfeatures not immediately necessary to Walnut, was completed in January 1982. It provides integritychecking of the data in a variety of ways, facilities to make it feasible for more than one applicationto share a single database, and some more powerful operations than present in the old DBTuplesinterface. The main two features deferred to phase two are views and environments. Views make applicationsharing of databases easier by allowing procedurally defined relations, and also allow encoding ofoperations on entities as procedures stored in the database. Environments allow databases thatcontain both public and private portions to appear as a single database to the owner of a privateportion. Environments will also provide a simple form of "layers" in the PIE sense, to encapsulateupdates to a database in a useful form. Environments will necessitate changes below the view levelof CedarDB, to allow database segments to be logically independent files, as well as changes to theDBView implementation. Views only require changes to the DBView implementation. There exists animplementation of environments that allow public/private databases and requires only DBView changes, creating twoinstances of the lower level database code; I may consider this if the pressure for combined public/private databasescontinues to increase.The lack of environments is a serious problem right now. There is no way to open both a publicdatabase (e.g., whitepages) and a private database (e.g., user mail) at the same time and have thetwo interact in a reasonable way. We can only copy whitepages into private mail databases or bewilling to store our mail in public (unprotected!) databases. The lack of multiple transactions onthe same machine is similarly a serious problem with respect to concurrent database access bymultiple applications. Squirrel can notify applications of database updates or transactionopen/close, or do some user interface coordination between applications, but there's no way we cando much more than experiment with really sharing databases between applications until many man-months have gone into these problems and into Alpine. I therefore view Walnut and otherapplications as interim experiments; I'm hopeful that these experiments will help rather thancompound the problem by bringing in more motivated manpower. The DBView interface willmake it a little easier to retrofit applications to these extensions than the old DBTuples interface. frG b6 ^H\ X!2W SL Q6P) L,'J Gbt D7r= BY A. P ?6# >&) :B 9w] 7P 6oW 4)5 3g 0;uru r .G -32- + U *+B! ( Y '#): %Pq $>T #-H ! trB S l%; S dM (+)0 \H B TH ;" L(/ 05b =Z`Database Application Goals5Some other shortcomings of CedarDB we are coding around in application programs for now (e.g.via the log mechanism in Walnut). I hope to reduce the need for these short-term measures in thesecond phase of CedarDB development.The motivation and design of changes to CedarDB are discussed in [Indigo]Database>ViewLevelDesign.press, readable but not yet completed at the time of this writing, so no more details of theDBView interface will be given here. Walnut phase twoA variety of facilities more powerful than Laurel are made possible by the storage of mail in adatabase. They are not essential to the use of the system, so are deferred to a second phase. Twofacilities that come immediately to mind are:1.Message Queryer: A query-by-example-like viewer which lets a user fill in fields andproduces a message set of messages satisfying the query. This tool can be built at variouslevels of aspirations, allowing the fields to be boolean expressions or even nested viewerswhich describe the entities desired recursively as queries. The simplest form of this toolcan be implemented directly with the primitive DBView DomainSubset operation, so thisis a simple task. The properties of querying message entities are little different fromquerying other application entities, so a variant of this code can probably be copied intoSquirrel for use by other applications.2.Mail Sorting: There are two times when the user might desire to sort mail on somecriteria. One is on receipt, when the user might like to see messages sent directly tohimself before those sent to distribution lists (unless they are from his boss). Orsomething like that. This might better be implemented by simply routing selectedmessages to a special message set representing higher-priority mail. The other case ofsorting is on old mail, perhaps to order a message set in some nice way or to producenice output for printing.The features of phase two will largely be a result of feedback from phase one, so I will say no morenow. Squirrel phase two, and other database applicationsA query tool is one of the most notably lacking facilities in Squirrel. For most application Ienvision, including Walnut, we need a query-by-example tool or some equivalent thereof.Producing the query response as an entity set on the screen nicely integrates it with the otherfacilities, e.g. the user can select the entities to view them with the application displayers. It is alsoimportant to do some kind of simple report generation. A simple but powerful way to do this is toprovide yet another entity-based form in which the user marks the entity properties to be printed,and the output formatting. This can be the same form as the query, although a separate one maybe easier for the user to understand.The other major facility Squirrel lacks is the abilty to view and update the data schema. Thisfacility can be added naturally by registering displayers and editors for data schema entities. Thedata schema editors should modify not only the schema but also all existing data (to fit the newschema). The ability to make data schema changes to an existing database is already becoming animportant need, as the time has become prohibitive to dump and reload a database in text form todo updates with a text editor. The prohibitive time seems primarily to be in reloading, so dumpingis still a viable mechanism for backing up a database. I believe performance improvements couldbe made in reloading, but it is an intrinsically expensive job to lookup and type-check incomingdata so potential improvements are limited. frG bF `,5 _$ [= Zfq2r X% Ut RrC Qc O- Kur-JJH|DF2)EtOC MBl4&@' <u rD;eF9<8]Q6B5UC3 0&> /! +t3 (r S 'F%2 %_ $>1: "D !620 C .% .1 ~=' ur vI P nJ O f V +( >YpVDatabase Application Goals6A major topic not even touched by Squirrel phase one and two is use of graphical display ofdatabases. I believe there is an order of magnitude improvement possible in database access bybrowsing, zooming, moving, and thinking in a spacial dimension in database display. This will haveto wait for a Squirrel phase three, I'm afraid, but I can see it as upward compatible with the lessambitious initial Squirrel and application displays. It isn't clear whether the performance of CedarGraphics is yet adequate to make graphical database display (say, as boxes and lines on the screenand the ability to move and zoom around) a usable product. But I have the seed of this idea in myhead and would like to see it pursued. Another dimension in which Squirrel phase two could move is procedural storage. Applicationviewer implementations can be stored as bcds referenced in the database itself; this is actually mucheasier than it sounds. This makes coordination between different application programs even easier,and simplifies the task of building applications with active components like alarms. We'll have tosee how important this becomes.The three applications I am most interested in seeing after Walnut, particularly because they allintegrate with Walnut as a single useful database, are:1.Whitepages. A database of people, organizations, phone numbers, addresses, perhapseven photos. Note there are both public private versions of whitepages, and the userwould like to see both superimposed.2.Calendar/alarm. A database of events a person would like to schedule. There might be"day" entity viewers, and "month" entity viewers, for example. Note there can be bothpublic and private databases of events, too.3.Super notebook. A database of one-sentence to one-page ideas, interconnected andindexed in a database of bibliographic references, project notes, etc. I have a lot of ideason this from trying to build such a thing at CMU. Note yet again that this applicationhas both public and private sections. Enthusiasm is great for such applications; several lab members have already spoken to me recentlyabout undertaking these. The right combination of facilitators are in place: Viewers, the newCedarDB, Squirrel, and Cedar. All of these have only recently become really useful systems, andmy plan and my prognosis is that more than one very successful database application will take offthis year. It is even more satisfying to me that as a result of the recent CedarDB and Squirrelwork, Walnut and other applications will be unlikely to become separate monolithic programs thatare dead ends with respect to uniform user interaction paradigms, sharing databases betweenapplications, and upward compatibility with database system enhancements. frG bT `!> _A" ]^ \T ZS YG W( TV#9 RH QNc OL NF KP I7 Eu rIDPB$ >u r8= V;, 7u r 66]4K 2%t .r*7 -z? +00 *rA (K 'i7) %6% $aI =G TIMESROMAN  TIMESROMAN TIMESROMAN LOGO TIMESROMAN  TIMESROMAN    & 08j/;9ԩ!DBApplications.memoCattellApril 2, 1982 10:42 AM