`
`T
`
`.
`
`_
`
`,
`
`I
`
`‘_
`
`~.
`,:
`A
`"InIeInationeIISymposjgm.
`'
`.
`'
`A
`m Info—Tech 94. .
`
`
`
`5
`
`
`
`
`
`”It
`October 11-13, 1994
`
`Kobe Chamber of Commerce and Industry
`
`Program & Abstraéfi
`
` Sponsored by
`
`
`
`O
`
`Hyogo Prefectural Government“
`City of Kobe
`Kansai Institute of Information Systems
`
`Suppofied by
`.
`.
`
`Ministry of International Trade & Industry
`
`Petitioner MicroSoft COrporation 4 EX. "1078, p;C6€éi‘r'
`
`Petitioner Microsoft Corporation - Ex. 1078, p. Cover
`
`

`

`international Symposium“lofo-Teoh ’94”; October 11-13, 1984, Kobe. Japan
`“nun—-nuns—unusu-nun—.m..«.-——pu—~g——.———.—~u—_v~.—~..~uu—s~-_—-nn—-
`
`
`
`Zelig: Automating Database Provision for the World—~Wide Web*
`
`Carlos A. Vgrelg *‘i
`Na tionnl Center for Supercomputing Applications
`University of Illinois at Urbaua»Champaign
`cvarcla @ncsa. rziuc. edu
`~
`
`Abstract
`
`The World~Wide Webibriogs a global information universe into existence using available technology
`chrnors~Lee et a1. 1992}. In order to fully realize the benefits of this information system, methodologies
`need to be dovelopod for the creation of scripts that query existing databases and produce effective user
`interfaces, Present practice falls short of this goal in two areas; first, interface changes require direct
`‘
`modification of the scripts, and second. user interfaces are hard, in the sense that they don't adapt to
`database usage.
`
`We presenr Zelig. a schemawbased approach to HTML document generation that addresses both these
`problems. First, Zelig uses ZH‘I‘ML schemata, which are HTML documents commented with directives
`for docurrient generation. And second, Zolig contains an expert module which gives advice regarding the
`underlying data structures and interface design issues. This approach allows an? or evolving database
`applications that keep track of usage and self—adapt to increase database efficiency and to improve
`human~computer interaction As an example, we have used this approncjn to automatically generate four
`different 3751 ms! interfaces to the 0280 phone: nameservcr database software.
`Notes
`
`" This is a reprint with minor modifications of {Yards and Hover 1994] to be presented at Inlo'rech ’94, Japan.
`** This paperls available in hypertext at the WV URL: ltttp://fiakor.ncsa.uluc. edw8080/ITP4szzl
`Underlined items are bypcrllnks. Interface figures are links to the cormpontling programs.
`1. Introduction
`
`In order to fully realize the benefits of the World—Wide Web, we need to be able to effectively
`interchange inlormarioa with existing databases. Common Gateway Interface scripts [McCool
`1993] are programs dovoloped to perform this communication between database servers and WWW
`clients.
`
`‘7
`
`Fig 1. Purpose of a script in a WWW server [Bemers~Lee & Cailliau 1992].
`
`:
`These scripts are written in any programming language (like C, CH or PERL) and their main
`
`13
`
`Petitioner Microsoft Corporation - EX. 1078, p. 1
`
`Petitioner Microsoft Corporation - Ex. 1078, p. 1
`
`

`

`
`
`functions are;
`
`v To receive the infomalion from the WWW client under the hypertext transfer protocol
`(http) [Berncrs~Lee 1993].
`_
`c To perform a query for the database server. allowing the WWW server to act as a database
`client.
`c To parse the database server results.
`c To generate an HTML document [Berncrs~Lee & Connolly 1993} and send it to the VNAV
`client.
`
`We are addressing two difficulties that CGI script developers find very often: how to modify their
`generated user interfaces without changing the source code of the programs, and how to generate
`flexible enough interfaces to meet the needs of very different types of users.
`in order to modify the user interfaces created by C61 scripts. currently developers have to go
`through a difficult two—level process. First, to change the script that generates the hypertext
`documents. Then. to make sure that the generated documents satisfy the original interface
`specifications. Our schema—based HTML generation reduces the complexity of this task by using
`schemata, where changes to the interface can be performed more directly.
`Another problem lies in the generation of soft user interfaces to existing databases. Current WWW
`hypertext interfaces to existing databases [Ng 1993] are hard, in the sense that they do notevolve
`according to usage statistics or particular user data inputs. This issue becomes crucial if we consider
`the difficulty in predicting the usage of a world-wide accessed database both in terms of the way in
`which data is used and the change in demand for items over time. We have followed a
`schema—based approach, inspired by other program synthesis researchers [Dershowitz 1983,
`Bhansali 1991], to overcome this problem.
`The presented approach allows the interface and the database to evolve based on usage statistics and
`expert rules for database design and humanwomputer interaction. Thus, we have identified two
`main components in the problem of generating design evolution decisions for database applications
`at run~tirnez changes in the underlying data structures and in the user interface.
`Following is a guide to the paper: In section 2, we present a methodology for schema selection and
`instantiation based on current database transaction results end ZH‘I‘ML schemata. Section 3 is a
`description of the mm‘n heuristics uscd for modification to underlying data structures and user
`interfaces. Section 4 presents several running examples based on the database software for phone
`directory nameservcrs developed at CCSO {Burner 1992]. Finally, in section 5. we present some
`conclusions.
`
`2. Schema~Besed HTML Generation
`in traditional HTlvfl. generation, user interfaces are created by scripts directly. This implies that
`changes to interfaces have to be performed at the level of the source code of the script. We present a
`methodology based on schemata, to allow designers to debug and maintain the user interfaces
`without directly changing the scripts.
`In this section, we will explain theinformation that is provided by the schemata to the scripts for
`document generation. Then, we will give a description of ZHTML, the language to write these
`schemata, which is an enhancement to HTML incorporating directives for database interface
`generation.
`The scripts base their hypertext generation notonly on the current parsed database query results, but
`also on existing ZHTML schemata. We can further categorize this information as:
`o Current database transaction results. These are the results generated by a query to a
`database. We assume that the script knows how to interact with the database server, parse its
`results, and standardize the query information to the following taxonomy:
`
`l4
`
`Petitioner Microsoft Corporation - EX. 1078, p. 2
`
`Petitioner Microsoft Corporation - Ex. 1078, p. 2
`
`

`

`l
`
`zraversaLrype (which can vae the, value TABLES, RECORDS. or FIELDS) and returns the
`output from ZETML body instantiated to each of tho loop elements in the, query.
`
`As an example. this is a schema for browsing a phone database. Wc will Show two different
`instantiazions depending on two different user queries:
`
`o 311;; fig; QIIQD' (233mm asks for the names and phone numbers of all entries with the name
`Hardin sorted ascondenrly. Our schema instanfiates such a query to this ETML file, which
`in turns is displayed by the browser as hypertext:
`
`
`
`
`
`0 $2113; 5929116 smog gamma asks for the same entries, but it also queries their address.
`Additionally the order is descendant, as opposed to ascendent. This the generated H11 ML file
`and its corresponding nxmgcxt 011mm.
`
`3. Soft WWW Database Applications
`
`Current WWW hypertext interfaccs to existing databasos are hard, in the sense, that may do not
`evolve according to usage statistics or particular user data inputs. This issue becomes crucial if we
`considcr the; difficulty in prodicling the usage of a world-wide accessed database both in terms of
`the way in which data is used and the change in demand for items over time. We have idemificd
`two main components in the problem of generating design cvoiufion decisions for database
`applications at run—time: changes in the underlying data structures and in the mast mterfacc.
`
`'
`
`‘7
`
`Petitioner Microsoft Corporation - EX. 1078, p. 3
`
`Petitioner Microsoft Corporation - Ex. 1078, p. 3
`
`

`

`Fig 2. Difference between hard and soft (16358115 [Varela & Hayes {9931'
`
`Modifications to the underlying data structures of the dalabase are intended to optimize access time
`and storage space in a global manner {they are directed to the database server, and are invisible to
`the WWW clients.) These modifications include database physical reorganization issues such as
`sorting tables and creating and deleting indexes. Our proposed methodology allows two specific
`dale structure changes {Varcla &. Hayes 1993]:
`
`. simplification of many-twmauy relationships between objects because of large branching
`factors, and
`o creation of new objects versus field replication to improve access time-,5.
`
`The rules for derivingvthe changes in data structures. were written in OPSS. a production system
`developed at CMU [Forgy 1981}.
`
`3.2. User Interfaces
`
` 3.1. Underlying Data Structures
`
`Modifications to the user interface are intended to provide a more effective human—computer
`interaction for database operations. Different users may have very different views of the data,
`individual interfaces need not be the some, instead they should evolve as a result of collected usage
`statistics. This interface evolution includes:
`
`- changing default values to reflect most commonly accessed data,
`a reorganizing the order of user interface actions, to make variables with high variance first.
`These are the vazinbles inthe forms whose value is more often changed from the default
`value.
`«v changing the level of access to certain database operations (like sorting, filtering and
`reporting options) according to their usage. Frequently used operations would be directly
`accessible, while rare operations would go to a second level of access (following a link.)
`This would allow the generation of smaller documents and provide a more friendly
`interface.
`
`4. An Example: The CCSO Phone Namescrver Database
`
`We have automatically generated four different interfaces following our schema—«based approach to
`writing scripts. If you are reading this abstract in a forms—based WWW browser, such as NCSA
`Mosaic [NCSA 1993]. you can follow the links to execute these interfaces.
`
`
`
`*‘
`
`w rs— ed
`
`'
`
`i
`
`using chemxsmonx tag.
`
`18
`
`Petitioner Microsoft Corporation - EX. 1078, p. 4
`
`
`
`l
`
`Petitioner Microsoft Corporation - Ex. 1078, p. 4
`
`

`

`5.
`.1
`e13
`
`iiA r
`
`o On an application level.
`The most general database information. For example: name, number of tables,
`default query tabic.
`o On an object level.
`The information for a specific object of our application. For example the table
`PEOPLE may have: name, number of records. number of fields. default field for
`queries.
`0 On afield level.
`
`The most specific infomation about a query for a given record. For example: field
`names, default field values, current field values, length, typo. and access policy.
`
`. Existing ZHTML schemata. Tnesc are provided by the interface designer, but can be easily
`created by modifying an HTML document with the desired output from the current database
`query. We have created several schemata for the phone database cxample:
`o WAS-based user interface schema.
`This schema is based on the Wide Area Information Servers system [Kahlc &
`Medlar 19911] and uses an m <ISIN'DEX> tag. It is important to note that there
`are many indexed databases in the Web that use this information system as the basis
`for database search.
`0 Forms—based user interface schema.
`
`This schema makes use of the forms~based WWW brewers to provide a more
`friendly userinterface with menus and widgets to perform the most common
`database operations.
`0 Applicatomspccific user interface schema
`This schema is usually an advanced interface tailored to the specific needs ofa
`database user interface. It still allows cyclution, in the sense that certain constructs
`don‘t imply any order or level of access in the generated HTML documents.
`
`A ZHIML schema is an HTML document which has been annotated with comments, which are
`used as directives for the script. These comments are parsed and executed by the script, and the
`resulting text is placed instead of the original comment This is performed at run—time, using the
`current database query results. Future work includes writing script code generators departing from
`these schemata.
`
`The ZH'I'ML commonts are similar to HTML constructs. They are generally of the form:
`<IZTAG> ZH’I‘ML body <l/ZTAG>
`
`”there are several chig directives with different functionality, including: print a variable value, run
`an external function printing its output, conditionally include the ZH'I'ML body. traverse all the
`current database records invoking chig recursively on the ZHTML body and traverse all the fields
`in a specific object.
`
`Following are the main constructs of this Document Type, even though a formal Document Type
`Definition (like the DTD shown for HTML in [Bowers—Lee & Connolly 1993]) is still in progress:
`. < lZPRIN’I‘ variable>
`
`returns the current value of an HTML form variable, or an application—level variable. If the
`variable is object~ievel orfield—level, then it needs to be in the scope of a ZI-‘OR tag.
`- <1 ZRUN ext emalfifn>
`runs the script function extemaljn and returns its output.
`c < 3 ZIP cond~expr> ZHTML body <! IZIF>
`returns the output from ZHTML body if cond-axpr is true. It returns the null string
`otherwise.
`
`0 < ! ZFOR TYPE: era versa 1_ time) ZHTML body < 3 IZFOR>
`traverses all the tables. records or fields of the current query, depending on the
`
`17
`
`
`
`Petitioner Microsoft Corporation - EX. 1078, p. 5
`
`Petitioner Microsoft Corporation - Ex. 1078, p. 5
`
`

`

`
`.
`.
`Em,
`
`
`imam:
`
`
`
` Q
`
`
`vvv.a,
`w
`
`
`
`
`
`Ef
`
`
`
`E E
`
`E
`
`Fig 3b. A simple user igtedgcc for this database application. It uses a form and is not
`sophisticated in the output handling, yet it is a useful and simpie gateway to phone
`directories.
`
`«DO‘VQflW-kh) ‘0rr>;f~»a
`In
`“
`.542
`IBM»
`
`n1, -*
`-;w
`
`‘1‘». E
`
`'
`o
`., ,
`
`
`“15.5..“ n,
`
`
`
`
`
`
`..‘~..~:
`
`
`
`.
`T
`,
`.
`
`
`:aaawnggi;
`.
`
`
`m s2 3e:
`
`
`
`
`
`"hi“?! ‘
`tat:- v:
`_- £2;
`an. ,
`
`
`
`
`fax.t t
`
`" 232‘ Wm;-
`
`M ~ .. n52
`
`
`Fig 3c. AW using forms, and parsing the database output to allow
`different sorting, filtering and showing options. The usage given to these options is
`fundamental towards the generation of advice regarding both the user interface and the
`underlying data structures. This schema has been written to be used by different database
`
`18
`
`Petitioner Microsoft Corporation - EX. 1078, p. 6
`
`
`
`Petitioner Microsoft Corporation - Ex. 1078, p. 6
`
`

`

`
`
`
`
`"‘nQJuaAuw—acm-
`
`applications. in other words it is domain independent.
`
`'
`
`v
`31118:?
`
`Fig 3d. And finally an advancm Sis-oz interface for this database application. This interface is
`very domain specific. in the sense thatit has been adapted to work mainly for the phone
`database. The idea is to lot the programmer move from the previous application to this one
`by making simple changes to the generated code.
`"
`
`There are some additional CSO nameserver database interfaces found in the WW, for reference
`and comparison:
`
`a g gcgo Pbgnolxgol: by Ed Kubaitis at CCSO. UIUC.
`c
`an for £2.39 PH goon by Jim Browne at NCSA, UIUC.
`- iii HZ gtaff Phone Book by Andi Kaner at E'I‘H Zuerich, Switzerland.
`
`5. Conclusions
`
`The presented methodology offers an evolving solution to database interface design using an expert
`system. This schema—based approach to HTML rum-time document generation, allows us to make
`modifications to WWW database applications easily by changing the schemata instead of directly
`changing the scripts which generate the hypertext documents. This approach also gives the interface
`designers some freedom in the schemata selection method. which proves useful for generating soft
`user interfaces.
`
`7
`
`As a result of having soft database applications, we have improved previous methodologies in two
`ways. On the one hand, there is increased efficiency in the underlying data structures resulting in
`faster access to the data. On the other hand, there is a more effective communication between the
`database and the users, who may have different views of the same information. This is of great
`signfiicnnce because of the greatly varying needs of the different users in the WWW.
`
`While the initial cost of programming parsers for the ZH'IML schemata may be high, the long
`term benefits of the automatic generation of interface design far Guru/eight the initial effort.
`Ultimately. this procedure offers the user a more efficient, fully customized interface, further
`‘\
`closing the gap between information provision and use.
`Admowlcdgcments
`
`19
`
`
`
`Petitioner Microsoft Corporation - EX. 1078, p. 7
`
`Petitioner Microsoft Corporation - Ex. 1078, p. 7
`
`

`

`
`
`Thanks to the NCSA Softvvare Development Group for their support to the first author, comments
`on this paper and excellent research and working environment.
`
`References
`
`erner —
`
`1
`
`2
`
`T. Berners—Lee. Hyperzext Transfer Protocol Requirements. Internet Working Draft. CERN. Work
`In progress.
`http://t'nfo. cem. ch/hypertext/WWW/Prolocals/HTTP.12th
`Berners—Lge et al. 12221
`T. Berners—Lee, R. Cailliau, J. Groff, B. Pollermann. World—Wide Web: The Information
`Universe. Electronic Networking: Research, Applications and Policy, 2(1), pp. 52~58, Meckler
`Publications, Westport CT, Spring 1992.
`‘
`prJ/firifo. cem. ch/pub/www/doc/ENRAPJZOZpS
`lBerners—Lee & Cailligu 122g
`T. Homers—Lee, R. Cailiiau. World—Wide Web. Submitted to Computing in High Energy Physics
`1992.
`
`*‘"
`
`fiprl/irzfo.cern.ch/pub/www/dac/chepQwawps
`(Ecrncrs-Lee & Connolly 12271
`T. Bernese—Lee, D. Connolly. Hypertext Markup Language: A Representation of Textual
`Information and Metaz'ry’ormation for Retrelval and Interchange, Internet Working Draft. CERN,
`Atrium Technology Inc. Work in progress.
`ht!p.’//Enf0.cemch/hypertexz/WWW/Marki/p/HWLhim!
`[Bhansali 1,991]
`‘
`S. Bilansali. Domain—Based Program Synthesis Using Planning and Derivational Analogy. PhD.
`thesis. University of Illinois at Urbana—Champaign. May 1991.
`[Dcrshowitz 1983]
`N. Dershowitz. The Evolution ofPrograms. Birkhauser, Boston, 1983.
`[Dorncr 1992]
`..
`S. Dormer. The CCSO Nameseiver, Server— Client Protocol. Computing and Communications
`Services Office. University of Illinois at Urbana—~Champaign. July 1992.
`[Forgy 1981]
`Porgy, Charles L. OPSS User’s Manual. Department of Computer Science, Carnegie Mellon
`University.
`[Kahle & Medlar 1991]
`B. Kahle and A. Median An Information System for Corporate Users: Wide Area Information
`Servers. ConneXions -— The Interoperability Report, 501), pp 2—9, Interop, Inc., Nov. 1991.
`
`.
`
`Rob McCool. National Center for Supercomputing Applications, University of Illinois at
`Urbana—Champaign. Common Gateway Interface Overview. Work in progress.
`‘ http.‘//Izoohoo.ncsa.uz‘uc.ed11/cngovervfew.html
`..,
`'
`EQSA 12931
`National Center for Supercomputing Applications; University of Illinois at Urbana—Champaign.
`NCSA Mosaic. A WWWBrowsez: Work in progress.
`http:/Avwwncsa. uiuc. edu/SDG/Sofmare/Mosat’c/Docs/heIp—abour. html
`{Ng 1293
`I. Ng. GSQL: A Mosaic—SQ], gateway. National Center for Supercomputing Applications.
`University of Illinois at Urbana—Champaign. Work in progress.
`http://www. ncsa. uz'uc. edit/SDG/People/jason/pub/gsql/bacbirrafili e re. hrml
`{Varela & Hayes 1993]
`C. Varela, C. Hayes. Automating Design ofDatabase Management Systems. Department of
`Computer Science. University of Illinois at Urbana—Champaign. Technical Reportr.
`.
`y arela and Hayes 1224
`*
`C. Varela, C. Hayes. Zelz'g: Schema—Based Generation of Soft WWW Database Applications. First
`International Conference on the World Wide Web, Geneva, Switzerland, May 25—29, 1994. URL:
`http://fiaker.ncsa.uiuc.eclu:8080WV94hnnl
`
`2O
`
`Petitioner Microsoft Corporation - EX. 1078, p. 8
`
`Petitioner Microsoft Corporation - Ex. 1078, p. 8
`
`