Project Requirements Document

1.0 Introduction

The BDE [Block Diagram Editor] program is an interactive tool for drawing and editing diagrams and structure charts. The persistent network database used by BDE to represent drawing elements, links and text is supported by the CHGEN code generation tool [Wang].

SYMTXT is a document management and compression utility that was built to provide cross-reference facilities for ASCII documents [Molloy]. SYMTXT processes ASCII input documents into a symbol/token table representation. Word tokens are stored in a dictionary structure [SY table]. The ASCII text is represented as a series of TK table row entries that reference word tokens stored in a dictionary table [SY table] via foreign keys.

The 94 Spring BDESYM team incorporated the SYMTXT project into BDE [Tong]. Symbol reference [YR Table] and text block [XB Table] tables were added to the BDE schema to support linkage to the SYMTXT symbol/token table representation for BDE text fields. Macros were added [pr_set/get_sym and pr_set/get_tokset] to replace pr_get/set_str to support retrieval and update of symbol reference and text block data.

The 94 Fall BDESYM team provided a pr_get/set_str facility that utilized table attribute data [TA table] to hide the requirement for specialized SYMTXT access functions from the BDE applications programmer [Mkayed]. Revised pr_get/set_str macros provided by the 94 Fall BDESYM team determined whether specialized access functions were required [pr_set/get_sym and pr_set/get_tokset functions] for string fields by inspecting the table attribute table [TA table] at execution time.

The efforts of the 94 Spring and 94 Fall BDESYM teams were never integrated into the BDE software baseline. Improvements and maintenance changes made to the BDE software baseline over the past year have not been incorporated into the BDESYM code base. As a result, attempts to re-make the 94 Spring and 94 Fall BDESYM versions have failed due to X11 library changes and other environmental changes [e-mail from Dr. Lechner 3/9/96].

The 96 Spring BDESYM team plans to integrate the 94 Spring and 94 Fall BDESYM efforts into the current BDE software baseline. Additionally, the following improvements to BDESYM are planned.

1. The polymorphic pr_get/set_str macros introduced by the 94 Fall BDESYM team require searches of the TT and TA Tables for each request. The 96 Spring BDESYM team will revise the pr_get/set macros to inspect the current TT and TA table position before initiating a search.
   
2. The current BDESYM design creates a TK table row for single space characters between words in text. The TK table schema will be altered to include a one character prefix space character count field that will be used to indicate the number of space characters preceding the symbol.
   
3. Presently, short words [three characters or less] are stored as inline data in the TK table row [tktyp field]. By storing short words as inline text, the symbol dictionary aspect of the BDESYM architecture is being circumvented. These short words should be treated as normal symbols with SY row entries.
   
4. Currently, BDESYM supports compressed storage of repeated character strings by storing the repeated character and the repeat count in the TK row entry. By encoding this information in the TK row entry's SY foreign key field the tktyp field can be eliminated from the TK table schema, reducing the memory and storage requirements.

2.0 Plans

The 96 Spring BDESYM project plans to segment the project into three build and test cycles. The first build and test effort will integrate the work of the 94 Spring BDESYM team into the current BDE software baseline. The second build and test effort will incorporate the work of the 94 Fall BDESYM team. The final build and test cycle will incorporate the 96 Spring team improvements.

The 94 Spring BDESYM team changes that will be integrated into the current BDE base are outlined below.

2.1.1 Schema Changes.

The 94sbde_schema.sch file referenced by Dr. Lechner's e-mail will be used as a base for the planned schema changes.

• HG Table Add foreign key pointers for YR and XB tables
• HN Table Add foreign key pointers for YR and XB tables
• HI Table Add foreign key pointers for YR and XB tables
• HA Table Add foreign key pointers for YR and XB tables
• SD Table New Table [symbol dictionary]
• YR Table New Table [symbol reference descriptor]
• TK Table New Table [token descriptor]
• XB Table New Table [text block descriptor]

2.1.2 Header File Changes.

bdesym.h header file for BDESYM

symtxt.h header file for SYMTXT

sym_sy_def.h header file for SYMTXT

2.1.3 Source Module Changes [SLOC Impact].

The 94 Spring BDESYM Team revised the CHGEN program to support additional "iskey" values to denote text fields that referenced symbol reference [YR Table] or text block [XB Table] foreign keys. Manual alterations were then made by the 94 Fall team to the header file produced by CHGEN. The native CHGEN macros were replaced with specialized pr_get/set_str macros that utilized the TT and TA tables to determine the appropriate action at execution time.

The 96 Spring BDESYM Team will review the CHGEN 9.5 changes made by the 94 Fall BDESYM Team to determine whether the changes made by that team can be integrated into CHGEN Version 10. Initial analysis shows that the CHGEN changes made by the 94 Fall team to support 'x' and 'y' key values were isolated to three CHGEN modules [add_pc_cp_entries.c, parse_schema.c and chgen_externs.h]. These does not appear to be any direct intersection between the CHGEN 9.5 and the CHGEN 10 changes.

If the CHGEN 9.5 changes can be integrated into CHGEN Version 10, the 96 Spring team will integrate the CHGEN changes and utilize the additional "iskey" values to denote symbol and text block references.

If upon further analysis, the CHGEN 9.5 integration effort is determined to be problematic, the same functionality can be supported by encoding the field attribute into the comment field of the input schema [YR table reference or XB table reference]. CHGEN will store this information in the TA row entry for that field. At execution time, pr_get/set_str code can interrogate the TA table to determine whether a call to a specialized access routine is required.

The polymorphic pr_get/set_str macros suggested by the 94 Fall BDESYM team search the TT and TA Tables on each request. The clustering of pr_get/set_str requests for the same table and field during BDE operation is not unexpected. The initial loading of the virtual memory network database from external storage is one example of request clustering. The 96 Spring BDESYM team will revise the generated pr_set/get_str macros to inspect the current row position in the TT and TA tables before initiating a table search.

Minor changes to the CHGEN gen_defines.cc module will be required to revise the pr_get/set_str macro code written to the generated header file at schema generation time.

The 96 Spring team BDE modifications introduce optimizations to BDESYM text handling functions to reduce memory and storage requirements. The planned changes focus on reducing the storage requirements for TK row entries by replacing the tktyp field in the TK table with a one character prefix space count and encoding information that was stored in the tktyp field into the TK table's SY foreign key field. The technical design for the encoding mechanism for SY foreign keys is detailed in the appendix to this document [SY Foreign Key Encoding Approaches document].

In the current BDESYM architecture, the SY foreign key in the TK table is used for three purposes:

1. SY foreign keys with zero version and symbol reference components, and a tktyp field of '9"xx', indicate that the tktyp field represents a repeated character string. This provides a mechanism for compressed storage of a string containing repeated characters. For example, a string of seven space characters can be compressed with a single space character stored with a repeat count of seven.
2. SY foreign keys with zero version and symbol reference components, and a tktyp field of '8xxx', indicate inline storage of a short symbol. Short words [three characters or fewer] are directly stored in the tktyp field.
3. A SY foreign key with a non-zero symbol reference component is a true foreign key pointer to a SY table row. In this case, the tktyp field redundantly stores the foreign key symbol reference.

The 96 Spring BDESYM project will implement code improvements in the following areas.

1. Currently, TK table rows are created for single space characters between words in text. The TK table schema will be altered to include a one character prefix space character count that will indicate the number of space characters that precedes the symbol.
2. Currently short words are stored as data in the TK table row [tktyp field]. By storing short words as inline text, the symbol dictionary aspect of the BDESYM architecture was being circumvented. These words should be treated as symbols, and SY row entries created.
3. By encoding information into the SY foreign key field [detailed specification information is available in the appendix to this document] the tktyp field in the TK Table can be eliminated.

3.0 Impact of 96 Spring BDESYM Changes.

3.1 Eliminate tktyp field from TK table Schema

In addition to the schema change, elimination of the tktyp field will impact 27 SLOC in the SYMTXT project code. The impact to the pr_load and pr_dump routines will be corrected by regeneration of the schema. The remaining impact will be in the sy_tk_mgr routine [text decomposition] and sy_pj_mgr [text regeneration] routines.

3.2 Alter approach toward encoding repeated character strings & short symbols.

The changes required to alter the encoding approach for repeated character strings and short symbols is fairly well isolated to the SYMTXT routines that support the encoding and decoding of character strings. It does not appear that changes to the lex grammar used by SYMTXT will be required to implement these changes.

Additionally changes will be required to SYMTXT and BDESYM code that is sensitive to the "SY000000" SY foreign key value in the TK row will require alteration. This key value had been used to indicate that the TK row represented either a inline token or repeated string, rather than a true SY Table foreign key. This will impact 8 SLOC in both the BDESYM and SYMTXT projects.

3.3 Eliminate TK row entries for single characters between words.

At present, the BDESYM design requires that a TK table row be created to represent the single space character between text words.

To support the prefix space count, a new field will be added to the TK Table schema. The prefix space count field will contain a count of the number of space characters that are to precede the symbol on output. This design approach will support a maximum of 255 space characters between symbols in text.

We plan on delivering five documents as part of the 96 Spring BDESYM project. Several of these documents will be provided as on-line Web pages (HTML Format).

4.1 Project Requirements Document.

This document will outline the 96 Spring BDESYM project requirements. The project deliverables will be detailed in the document. A project plan that includes a timeline for project tasks will also be included in the document.

4.2 SY Foreign Key Encoding Approaches Design Approach Document.

[Molloy] Molloy, John and Husssainee, Kehkashan, SYMTXT-Final Report, 1/18/94, remus:/usr/u/factmp/lechner/93f523/93fsym/base/doc/symtxt_doc.txt.

[Mkayed] Mkayed, Rim and Das, Sanat, Final Report Software Engineering 94f523 BDESYM & CHGEN Team, 2/28/96 [sic], /usr/proj3/case/94f523/94fbde/rmkayed/report/94fbdesym.ps.

[Tong] Tong, Duc, Islam, Sahibul and Chiou, Shao-Fong, Final Report Software Engineering 94s523 BDESYM Team, 5/19/94, remus:/usr/u/factmp/lechner/94s523/94ssym/base/doc/94ssymFinalReport.ps.gz.

[Wang] Wang, Chien-Yuan, Ko, Ching-Chih, Chen, Ke-Chiang and Wu, Chih-Yung. CHGEN User's Manual Version 10, 5/15/95, /usr/proj3/case/95s523/genv10/base/doc/gen10_manual.ps.

96 Spring BDESYM Team

Bob Connell

Bob Costello

3/26/96 - Version 1.4