riternationa Symposium
`
`fI Info4ech 94
`
`MuLtmdia
`tie 1nformatiorSpciety
`Overconing the Limitations of Trn and Space
`October 11-13 1994
`IKobe Chamber of Commerce and Industry
`
`Program Abstracts
`
`Sponsored by
`
`Hyogo Prefectural Government
`City of Kobe
`Institute of Information Systems
`
`Kansal
`
`Supported by
`
`Ministry of International Trade
`
`Industry
`
`Petitioner IBM – Ex. 1078, p. 1
`
`

`
`International Symposiumlnfo-Tech 94 October
`
`1-13 1994 Kobe Japan
`
`Zelig Automatiig Database Provision for the WorldWide Web
`
`National Center for Supercomputing Applications
`University of Illinois at UrbanaChampaign
`cvarela@ncsauiuc.edu
`
`Abstract
`
`global
`
`The WorldWide Web brings
`information universe into existence using available technology
`iBernersLee eta 1992J In order to fully realize the benefits of this information system methodologies
`need to be developed
`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
`are hard in the sense that
`they dont adapt
`user
`database usage
`
`interfaces
`
`to
`
`We present Zelig schemabased approach
`to HTML document
`that addresses both these
`generation
`problems First Zelig uses ZHTML schemata which are HTh4L documents
`commented with directives
`for docunient generation And second Zelig contains an expert module which gives advice regarding the
`underlying data structures and interface design issues This approach allows soft or evolving database
`applications thatkeep track of usage and selfadapt to increase database efficiency and to improve
`interaction As an example we have used this approachto automatically generate four
`humancomputer
`different WjLirgerfgceg to the CCSO phone nameserver
`database software
`
`Notes
`
`This is
`
`reprint with mtnr snodifictioas
`orfVareia and Hayes 1994 tote presented at InfoTech 94 Japan
`Thirpaperts arailabte in hypertext at theWWW IJItL htip/Ifiaicer.ncsauiuc.edu.808011T94.hrrnl
`Underlined Items arc hyperttnks
`Interface figures arc links to the corresponding prnsjrens
`
`Introduction
`
`In order to fully realize the benefits of the WorldWide Web we need to be able to effectively
`information with existing databases Common Gateway Interface scripts
`interchange
`to perform this communication between database servers and W1VW
`1993 are programs developed
`clients
`
`omw
`
`-E
`
`Fig
`
`Purpose of
`
`script
`
`in WWW server
`
`Cailliau 1992
`
`These scripts are wrinca in any programming language like Cit- or PERL and their main
`
`13
`
`Petitioner IBM – Ex. 1078, p. 2
`
`

`
`functionS are
`
`To receive the jnforinanon from the WWW client under
`1993
`query for the database server allowing the WWW server
`
`http
`
`ToperforTn
`
`the hypertext
`
`transfer protocol
`
`to act as
`
`database
`
`client
`lb parse the database server results
`To generate an HTML document BernerSLee
`
`client
`
`ConnollY 19931 and send it
`
`to the WW\V
`
`tWO difficulties that CCI script developers find very often how to modify their
`We are addressing
`user interfaces without changing the source code of the programs and how to generate
`types of users
`the needs of very different
`
`to meet
`
`through
`
`difficult
`
`that generates
`
`interface
`
`generated
`flexible enough interfaces
`have to go
`In order to modify the user interfaces crated by CCI scripts currently developers
`the hypertext
`twolevel process First to change the script
`documents Then to make sure that the generated documents satisfy the original
`reduces the complexity of this task by using
`specifications Our schemabased HTML generation
`schemata where changes tO the interlace can be perfonned more directly
`to existing databases Current WWW
`interfaces
`of soft user
`Another problem lies in the generation
`they do not evolve
`1993 are hard in the sense that
`so existing databases
`interfaces
`if we consider
`hypertext
`according to usage statistics or particular user data inputs This issue becomes crucial
`in predicting the usage of worldwide 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
`approach inspired by other program synthesis researchers Dershowit 1983
`schema-.based
`Ithansali 1991 to overcome this problem
`
`the difficulty
`
`and the database to evolve based on usage statistics
`approach allows the interface
`The presented
`expert rules for database design and human_computer interaction Thus we have identified two
`design evolution decisions for database applications
`main components in the problem of generating
`and in the user interface
`at runtime changes in the underlying data structures
`we present methodology for schema selection
`guide to the paper In section
`instantiation based on current database transaction results and ZFfTML schemata Section
`description of the main heuristics used for modification to underlying data structures and user
`running examples based on the database software for phone
`presents several
`we present some
`1992. Finally in section
`at CCSO
`developed
`
`Following is
`
`interfaces Section
`
`directory nameservers
`conchtSions
`
`and
`
`and
`
`is
`
`SchemaBased HTML Generation
`In traditional HTML generation user interlaces are created by scripts directly This implies that
`to interfaces have to be performed at the leveL of the source code of the script We present
`changes
`to debug and maintain the user interfaces
`methodology based on schemata to allow designers
`the scripts
`without directly changing
`
`is provided by the schemata to the scripts for
`In this section we will explain the information that
`description of ZHTML the language to write these
`document generation Then we will give
`to HTML incorpor.itiflg directives for database interface
`schemata which is an enhancement
`generation
`
`not only on the current parsed database query results but
`The scripts base their hypertext generation
`this information as
`also on existing ZHTML schemata We can further categorir.e
`Current database transaction results These are the rcsultS generated by query to
`the script knows how to interact with the database server parse its
`database We assume that
`results and standardize the query information to the following taxonomy
`
`14
`
`Petitioner IBM – Ex. 1078, p. 3
`
`

`
`type which can vae the value TABLES RECORDS or FIELDS and returns the
`trcrversal
`from ZIJ7ML body instantiated
`to each of the loop elements
`in the query
`
`output
`
`As an example this is
`instantiations depending
`
`schema for browsing
`phone database
`on two different user queries
`
`wilt show two different
`
`fliefiistqttci.exanipk asks for the names and phone numbers of all entries with the name
`Hardin sorted asccndentiy Our schema instantiates such
`query to this jIMIJjlg which
`in turns is displayed by the browser as hypertext
`
`Qiiracqoerypcap pie asks for the same entries but
`it also queries their address
`as opposed to ascendent This the generated HTML tile
`the order is descendent
`and its corresponding byial
`Additionally
`Soft WWW Data base Applications
`Current WWW hypertext
`to existing databases are hard in the sense that
`they do not
`evolve according to usage statistics or particular user data inputs This issue becomes crucial
`if we
`consider the difficulty in predicting the usage of worldwide accessed database both in terms of
`time We have identified
`the way in which data is used and the change in demand for items over
`two main consponents
`in the problem of generating
`design evolution decisions for database
`applications at mntime changes in the underlying data structures
`and in the user interface
`
`interfaces
`
`15
`
`Petitioner IBM – Ex. 1078, p. 4
`
`

`
`Fig
`
`Difference between hard and soft designs
`
`Hayes 1993
`
`3.1 Underlying Data Structures
`
`Modifications
`
`to the enderlyinS data structures of the database are intended to optimize access time
`global manner they are directed to the database server and are invisible to
`and storage space in
`the WWW clients These modifications include database physical reorganization issues such as
`sorting tables and creating and deleting indxe Our proposed methodology allows two specific
`Hayes 1993
`data structure changes Varela
`
`simplification of manytomany relationships between objects because of large branching
`factors and
`creation of new objects versus field replication to improve access times
`
`The nile.s for deriving the changes in data structures were written in OPS5
`at CMU
`i98l
`
`developed
`
`production system
`
`3.2 User Interfaces
`
`Modifications
`
`to provide more effective humancomputer
`interface are intended
`to the user
`interaction for database operations Different users may have very different views of the data
`interfaces need not be the same instead they should evolve as
`individual
`statistics This interface evolution includes
`
`result of collected
`
`usage
`
`to reflect most commonly accessed data
`changing default values
`reorganizing the order of user interlace actions to make variables with high variance first
`These are the variables in the forms whose value is more often changed from the default
`value
`
`the level of access to certain database operations like sorting filtering and
`changing
`reporting options according to their usage Frequently used operations would be directly
`link
`second level of access following
`accessible while rare operations would go to
`and provide more friendly
`This would allow the generation of smaller documents
`
`interface
`
`An Example The CCSO Phone Nanieserver Database
`four d.ifferent interfaces following our schemabased approach to
`We have automatically generated
`in formsbased WWW browser
`tuch as bICSA
`writing scripts If you are reading this abstract
`1993 you can follow the links to execute these interfaces
`Mosaic
`
`phfa
`
`using the fDML ISItSDEX tag
`
`16
`
`Petitioner IBM – Ex. 1078, p. 5
`
`

`
`On an application level
`The most general
`database information For example name number of tables
`default query table
`On an object
`level
`The information for
`specific object of our application For example the table
`PEOPLE may have name number of records number of fields default field for
`queries
`On afield level
`The most specific information about
`names default
`
`given record For example field
`query for
`field values current field values length type and access policy
`Existing ZHTML schemata These are provided by the interface designer but can be easily
`created by modifying an HTML document with the desired output from the cunont database
`query We have created several schemata for the phone database example
`
`WAISbased user interface schema
`This schema is based on the Wide Area Information Servers system
`i991fl and uses an HTML ISINDEX tag It
`Medlar
`to note that
`there
`is important
`in the Web that use this information system as the basis
`are many indexed databases
`for database search
`Facetsbased user
`interface schema
`This schema makes use of the forxnsbased WWW browsers to provide more
`friendly user interface with menus and widgets to perform the most common
`database operations
`Applicationspecific user interface schema
`This schema is usually an advanced interface tailored to the specific needs of
`database user interface It still allows evolution in the sense that curtain constructs
`dont imply any order or level of access in the generated HTML documents
`
`ZUThIL schema is art HTML document which has been annotated with comments which are
`used as directives fur the script These comments are parsed and executed by the scdpt and the
`resulting text is placed instead of the original comment This is performed at runtime using the
`current database query results Future work includes writing tcript code generators departing from
`these schemata
`
`The ZHTML comments are similar to HTML constructs They are generally of the form
`ZPAG ZHTJL body /ZThG
`
`There arc several Zelig directives with different
`functionality
`variable value run
`including print
`an external function printing its output conditionally include the ZHTML body traverse all
`the
`current database records invoking Zelig recursively on the ZHTML body and traverse all
`the fields
`specific object
`
`in
`
`the
`
`Following are thu main constructs of this Document Type even though
`formal Document Type
`Definition like the DID shown for HTML in
`Connolly 1993j is still
`in progress
`LZPRINy varib1
`returns the current value of an HTML form variable or an applicationlevel variable If
`variable is objectlevel or fieldlevel
`ZFOR tag
`then it needs to be in the scope of
`ZRWr externa.2_fn
`runs th script
`function external Jo and returns its output
`VhIF cond-expr
`baci5 1/ZIF
`2HTNL
`returns the output from ZIJTML body if coed expr is true It returns the null string
`otherwise
`ZPOR YPEcraver-se1 type ZHTML
`body /ZFOR
`the tables records or fields of the Current query depending
`
`traverses all
`
`on the
`
`17
`
`Petitioner IBM – Ex. 1078, p. 6
`
`

`
`Pig 3b
`sophisUcated
`
`directories
`
`le userjntej
`in tbo output handling yet it
`
`is
`
`for this database application It uses
`useful and simple gateway
`
`form and is not
`
`to phone
`
`using forms and parsing the database output to allow
`Fig 3c
`different sorting filtering and showing options The usage given to these options is
`interface and the
`towards the generation of advice regarding both the user
`fundamental
`underlying data structures This schema has been written to be used by different database
`
`18
`
`Petitioner IBM – Ex. 1078, p. 7
`
`

`
`applications in other words it
`
`is domain independent
`
`by making simple changes
`
`Ftg 3d And finally an gçjJ
`ace for this database application This inlet-face is
`very domain specific in the sense that it has been adapted to work mainly for the phone
`database The idea is to let
`the programmer move from the previous application to this one
`to the generated code
`There are some additional CSO nameserver database intethxees found in the WWW for reference
`SO Phonebook
`by lit-i Kubaitis at CCSO IJflJC
`Ewn tosi ceithcby Jim Ilrowne at NCSA URIC
`taffPltonk by Andi Iarmr at ETh Zuerich Switzerland
`
`and cotnparison
`
`ConclusIons
`
`The presented methodology offers an evolving solution to database interface design using an expert
`to HTML nmtime document generation allows us to make
`system This schemabased approach
`modifications to WWW database applications easily by changing
`the schemata
`instead of directly
`the scripts which generate the hypertext documents This approach
`also gives the interface
`some freedom in the schemata
`selection method which proves useful for generating soft
`interfaces
`
`changing
`
`designers
`
`user
`
`As
`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 more effective communication between
`the
`database and the users who may have different views of the same information This is of great
`significance because of the greatly varying needs of the different users in the WWW
`
`While the initial
`
`cost of programming parsers for the ZHTML schemata may be high the long
`term benefits of the automatic generation of interface design far outweiglit
`the initial effort
`Ultimately this procedure offers the user more efficient fully customized interface further
`closing the gap between information provision and use
`
`19
`
`Petitioner IBM – Ex. 1078, p. 8
`
`

`
`Thanks to the NCSA Software Development Group for their support
`research and working environment
`on this paper and excellent
`
`to the first author comments
`
`References
`
`http.//info.cern
`
`ch/hypertextiWWW/Protocos/Jfl7P.htmj
`
`Cailliau Groff
`
`IBernersLee 19921
`Berners-Lee Hypertext Transfer Protocol Requirements Internet Working Draft CERN Work
`in progress
`erUl.1
`Pollermaan WorldWide Web The Information
`BernersLee
`Universe Electronic Networking Research Applications and Policy 21 pp 5258 Meckler
`Publications Westport CT Spring 1992
`ftp.//ifo cern cWpub/www/doc/ENR.4P92O2ps
`IBernersLee
`Caillipu 19921
`Caillian WorldWide Web Submitted to Computing
`BernersLee
`1992
`
`in High Energy Physics
`
`Representation
`
`ftp//info cern ch1pub/www/doc/chep92www.ps
`Connolly 19931
`fBerncrs-.Lce
`BernersLee
`Connolly Hypertext Markup Language
`of Textual
`Jiformarion and Metaitformarion for Retreival and interchange Internet Working Draft CERN
`Inc Work in progress
`Atrium Technology
`htrp//info.cern ch/hypertexilWWW/MarkUp/FITMLhtnl
`IBhansali 1991
`Bhansali DomainBased Program Synthesis Using Planning and Derivational Analogy Ph.D
`thesis University of Illinois at UrbanaChampaign May 1991
`1983
`Dershowitz The Evolution of Programs Birkhauser Boston 1983
`1992
`Dorner The CCSO i/ameserver ServerClient Protocol Computing and Communications
`Services Office University of Illinois at UrbanaChampaign
`July 1992
`Forgy 1981
`Forgy Charles
`University
`Medlar 1991
`Kahle and Medlar Art Information System for Coxporale Users Wide Area Information
`The Interoperability Report 511 pp 29 Interop Inc Nov 1991
`Servers ConneKicns
`
`OPS5 Users Manual Department of Computer Science Carnegie Mellon
`
`Rob McCool National Center for Supercomputing
`Applications University of Illinois at
`common Gateway intemface Overview Work in progress
`UrbanaChampaign
`http//hoohoo.ncsa.uiuc.edu/cgi/overview
`html
`INCSA 19931
`National Center
`for Supercomputing Applications University of Illinois at UrbanaChampaign
`WWW Browser Work in progress
`NCSA Mosdic
`http//ivww.ncsa.uiuc.edrt/SDG/Soflware/Mosaic/Docs/helpabour
`Mg 19931
`Mg GSQL MosaicSQL gateway National Center
`for Supercomputing Applications
`University of Illinois at UrbanaChampaign Work in progress
`http//www ncsa.uiuc edwSDG/PeopleJjason/pub/gsqL/backrrarthere.html
`Hayes 1993
`Hayes Automating Design of Database Management Systems Department of
`Varela
`Computer Science University of Illinois at UrbanaChampaign
`Technical Reportr
`Iyarela and Hayes 19941
`Hayes Zelig SchemaBased Generation of Soft WWW Database Applications First
`Varela
`on the World Wide Web Geneva Switzerland May 2529 1994 URL
`International Conference
`httpfffiaker.ncsa.uiuc.edu8080/VrWW94.html
`
`html
`
`20
`
`Petitioner IBM – Ex. 1078, p. 9