|
Database
Transformation,
Synthesis and Playback Technology
by David
M. Schwartz, CEO, ImaginOn, Inc. 24 October 1996
Synopsis
The current level of technology in database software
is hierarchical relational databases and the search engines
that access them. This technology works well for most of
the local data storage, retrieval and presentation tasks
undertaken by businesses and institutions. Nonetheless,
even in these "normal" areas problems have always occurred
at the boundaries between databases and among databases
of different formats. For tasks outside the normal course
of business management, traditional database structures,
methodologies and tools rarely perform adequately. These
areas of inadequate performance include large chaotic networks
such as the Internet, real-time accessed databases such
as film, video and audio clips, and extremely complex, re-entrant
dynamic data structures such as large computer programs.
ImaginOn
technology solves the access, retrieval and presentation
problems associated with problematic data structures and
systems such as those mentioned above by applying the principles
of database transformation, network synthesis and
automated adaptive playback. Database transforms
are the processes by which a source database structure and
its contents are converted into an output database that
has a specified relationship to the source. Network synthesis
is the process by which a multidimensional network is created
according to a set of rules. Automated adaptive playback
is the process by which the data within any network structure
can be presented sequentially on a non-linear path jointly
determined by the user's preferences and the rules of the
process. To date, three distinct commercial applications
of ImaginOn technology have been identified: interactive
film authoring and playback, world wide web data processing,
and automated testing of computer programs.
Background
The history of mainstream business computer database
technology is the story of the transition from flat-file
databases to relational databases. In the engineering community,
hierarchical databases of both flat and relational types
have been utilized in specialty applications like computer
aided design and project management. Flat-file databases
consist simply of data entries in the form of records containing
a set of fields delineated from one another by commas (or
other character). Records are either separated by an end-of-record
character, or by the implied boundary of a fixed record
length. Flat-file databases are accessed by reference to
the record number itself or by searching for a user-defined
string (set of characters) within the database, which will
then return the ID numbers of all records that contain the
string.
Relational
databases represent an improvement over flat-file databases
in that the database is addressable down to the field level.
This provides powerful sorting capabilities to the user.
A cross-section of a relational database can be retrieved
based on attributes within a specific field or by combinatorial
logical (Boolean) operations on all fields. For example,
in the California DMV database, finding all the families
with the surname "Jones" who own 1972 Ford sedans is a simple
matter of sorting the database for "Jones and Ford and sedan
and 1972".
Hierarchical
relational databases have the additional feature of "nesting".
Nesting refers to a multi-level aspect of the database.
In computer aided design, the top level of a design is frequently
a simple block diagram showing the main sections of the
design, such as CPU, Memory, I/O, Peripherals, and Power
Supply. The connections to and from each block are indicated.
The next level in the hierarchy is the design of each section
itself. Then, within each section there may be custom integrated
circuits that are themselves the subject of another level
down in the hierarchy. With a hierarchy, the user gains
the ability to access data specific to the level of detail
under investigation, without the additional detail contained
in the next level down. The limits of a database search
can then be defined in terms of depth as well as relationships
within a level.
Independent
of database type and structure, the problem of information
access and retrieval has typically been approached with
a single primary specification: find the data of interest
and deliver it. For extremely large, complex and far-flung
databases this approach is analogous to the command "visit
every apple orchard in the world and bring back only the
sweetest apples". The search engine dutifully visits every
apple orchard, finds the closest thing to "sweetest" and
harvests those. The result is one big pile of apples. Too
big, usually. The user is then faced with sampling every
apple in the pile. Even then, some useful information remains
hidden. For example, if the very sweetest apples all came
from one region, that could only be determined by another
search or post-processing of the tags on all the apples.
Thus, sometimes it is the connection among
data items, as opposed to the items themselves that is the
most valuable information.
Anyone
who has attempted to use the Internet for research or entertainment
has encountered the inadequacy of the current generation
of software to some extent. The symptoms are slow access
times, erroneous search results, recirculating linkages,
pointers to defunct data sets or locations, dead-end links
and screen after screen of useless web pages. One approach
to improving the situation has been the application of "Intelligent
Agents". The idea is that these software robots will assist
the user by handling some of the grunt-work associated with
web data access, retrieval and presentation. At most, these
tools will automatically log onto the net, go to a list
of web sites and then download the data from them to the
user's hard disk drive. In every case, the robot has to
be trained; told what pages to go to and what kind of data
to download. They are not much help, but better than nothing.
When the
database is digital videotape clips or other real-time data
such as digital audio the nature of the problem is not so
much the scope or size of the database, but the requirement
that the data be retrieved in real time, at the frame rate
or sample rate of the content. Slow-motion or interrupted
playback of visual and audio material is generally not of
much interest. For databases of video clips on local disk
drives or databases spread across networks, seamless access
from one data item to the next is difficult and in many
cases impossible. The present generation of database technology
is not designed for real-time data processing.
For a
database composed of the executable (assembly language)
code of a computer program, a set of input data, control
vectors (user input), and output space (display memory or
other target), the present generation of database technology
is virtually useless. At most, the frequency of occurrence
of specific words or strings can be discovered, or some
parts of the structure can be deduced. Little knowledge
about the correctness of the code can be gained.
Specialized
analysis software does exist that can "snoop" while a program
executes, creating a database containing information about
the history of program execution and dataflow through the
program. But, these tools are intrusive, provide limited
functionality and consequently are not widely used.
ImaginOn
System
ImaginOn's technology is contained in three functional
areas; transformation, synthesis and playback. Although
it is convenient to separate the software operations of
the system into these parts, in actual use the distinction
is not always clear. This fuzziness arises when some functions
are called by more than one part of the system and when
some operations are performed in parallel.
Transformation
Database transformation is based loosely on the digital
signal processing (DSP) model. Whereas the data in DSP is
usually derived by sampling a real-time signal of some sort,
the input data in the ImaginOn system is some pre-existing
database. Any database will do; a text file, a directories
of filenames, images, video clips, a network of data servers,
whatever. The input to the transform function is the source
database (or source databases) and the output is a subset
of the source database. Between input and output is a "black
box" containing the transform engine and its filters. The
transform procedure is similar in theory to the creation
and operation of finite impulse response (FIR) filters on
digitally sampled signals such as audio or video waveforms.
Like digital signal processing with transform functions,
database transformations can be tuned, that is to
say filters can be designed or transform functions specified
appropriate to the input data and optimized to create output
suited to the user's particular needs. Filtering
functions can be performed on the database in the temporal,
spatial and frequency domains.
An example
of a temporal filter is updating an output database by sampling
a source database at specific time intervals. A spatial
filter can delete content from a database to meet storage
requirements. A frequency-based filter can create an output
database by including items only if they are pointed to
(addressed) more than a specified number of occurrences
from other nodes in the source database. Of course, filtering
can be based on more than one dimension at a time and to
varying degrees or extent in each dimension. Virtually
all of the filtering techniques developed for DSP can be
applied in database transformations. To name a few:
decimating, bandpass, high-pass, low-pass, comb, shelving,
and notch.
In the
web processing application of ImaginOn technology, "WebZinger",
the transform function produces a condensed format suitable
for high-speed access during playback. The DSP analogy to
this is lossy data compression. Comparing the input versus
the output databases, ImaginOn performs compression in
four ways:
1. Reduction
in scope of the database
The number of nodes made available for processing is
less than the number of nodes in the source network.
The extent of the scope is determined by storage availability
and time limitations.
2. Decimation
of the number of nodes within the scope of the process
Many of the nodes processed are deleted, never appearing
in the output database. The extent to which a selected node
matches the node selection criteria is saved as a data array
in a format like that of the selection criteria data array
itself. Nodes may also be selected by other filtering
functions such as time or frequency of reference by other
nodes.
3. Bandpass
filtering of the data within each node
Only a fraction of the total data within a node is reformatted
and saved. The parameters of the filter are set by the user
or the default parameters are used. Filtering may be of
any type, including by data class (audio, video, still image,
text, etc.), by time (for example, only take the data pertaining
to specific dates), by frequency of update (for example,
only take data that is updated hourly), or spatially (for
example, take data from twenty geographically diverse sites),
etc.
4.
Link information is reduced or deleted
Since only qualified nodes are included
in the output database, all of the links representing unused
nodes along them path to a selected node can be replaced
with a single vector which is a synthetic link that never
existed in the source database. Likewise, all unused links
pointing out of a selected node are deleted, except those
at terminal nodes. At terminal nodes (those at the end of
a series of linked nodes), the unused outward pointing links
are saved for future use in a transformation that is started
from that terminal node.
Synthesis
A synthetic network, in the context of this discussion,
is one that does not exist either in nature or as a pre-existing
manmade structure. The process of network synthesis is,
considered by itself, nothing new. Multidimensional tree-like
data structures, their creation and implementation, have
been a part of computing since day one. It is the close
coupling of ImaginOn network synthesis with ImaginOn database
transformation that yields tree-like networks that are novel
and useful. In synthesis, the output database created
by the transformation process is structured as a network
in "n" dimensions according to a set of rules using
parameters that are set by the user, or the default settings.
The purpose of the structure is threefold: the structure
serves as "rails" that the playback engine can traverse,
the non-linear sequential organization preserves much of
the original connectivity information that was present in
the source database before transformation, and a time axis
is implied. It is the combination of the "rails" and the
implied time axis that provides the user with the illusion
of virtual motion in "dataspace" during playback of the
transformed database.
Networks
synthesized by ImaginOn are variable in size, shape and
complexity. Each of these variables can be set by the user.
Size refers to the total quantity of data that is contained
in the synthetic network. Shape refers to the relationship
between the depth (or height) of the tree and its width.
Complexity refers to how many dimensions, or branches, radiate
from each node in the tree. While there are no theoretical
limits to any of these variables, there are obvious practical
considerations that pertain to storage limitations, display
limitations and computational time. Similarly, there is
no requirement that structures be symmetrical, though for
ease of conceptualization, symmetrical trees are preferred.
ImaginOn
synthetic networks are stored in computer memory as a database
of items commonly referred to as "objects". Each object
of a given class in the structure, for example, trunk node,
branch node and data page contains within it pointers to
the actual physical location of the data it references as
well as pointers to any other object it is linked to in
the tree structure. When such a synthetic network is embodied
as a schematic drawing, the objects are graphic library
elements and the links are defined in a text file known
as a "netlist". Since the graphical elements can also be
represented as sets of x,y coordinates, the entire synthetic
network can be stored as ASCII text in human-readable files,
if so desired.
By definition,
the synthetic network is hierarchical. The top level of
the hierarchy is represented by the nodes along the trunk
of the tree. The next level down contains the first layer
of branches and so on down through layers of branches to
the lowest level which contains the leaves. Since the actual
physical address of the source data from which the transformed
data was obtained is stored along with the data for each
node in the tree, new synthetic networks can be created
which are continuations of any previous network by performing
a new transform on the source database beginning at that
point.
Playback
Since the present generation of database technology
was developed primarily for business and scientific uses,
the underlying concept behind data presentation in database
products is information transfer; from computer to user.
Static screen displays of complex data and comprehensive
printouts of search results are the norm. Rapid access to
large quantities of search results is typically supported
by graphical lists of contents, or indexes, from which the
user can select the next page display. When the results
database is extremely large, even indexed displays may require
large numbers of keystrokes and many hours of viewing time
to zero-in on a specific item of interest.
Conventional
data presentation methods such as graphical browsers and
relational database formatted-field displays require the
user to indicate what the next display screen
will be and when it will be displayed. Typically,
the user accomplishes this by clicking on a "next" button
or a line of displayed hypertext which is a "hot-link".
There is no way to avoid this one-page-at-a-time procedure.
ImaginOn offers a completely different model of data presentation,
similar in some respects to the way consumer entertainment
products work. The concept of "playback" is utilized in
the same sense that VCRs play back videotape, or CD players
play back music.
ImaginOn's
playback technique is based on an adaptive algorithm that
determines both what will be displayed next and when it
will be displayed. This feature allows the user to be completely
passive, or as active as they want to be during the data
presentation process. When the user decides to be a completely
passive viewer, ImaginOn playback is automated according
to it's internal rules. This capability is fundamental to
ImaginOn's computer software program testing application.
The analogy
between a VCR's playback of videotape and ImaginOn's playback
of an output database appropriately describes the seamless
nonstop continuous nature of the presentation, but does
not encompass the new features provided by the system. These
unique capabilities include dynamic path selection through
the database, adaptive automation, variable playback resolution,
and hierarchical playback.
Dynamic
path selection
During playback, the user traverses a path through Imaginon's
synthetic network organization of the output database. The
path may start anywhere in the network, though the default
is the first Trunk Node. The actual vector the user follows
through the network is dynamically determined, assuming
the user provides some direction. The user's selection
of the path vector is made with one key, or button, by responding
to the alternating branch choices visually presented
(or presented by audition, in the case of an audio database)
at Trunk Nodes and Branch Nodes. The next data item is then
immediately presented, without an interruption in the display
or audio output. Should the user fail to make a selection,
playback is continued along a default path, without interruption,
after a predetermined number of alternating choice presentations.
Adaptive
automation, autoplay and adaptive transforms
Every time the user makes a selection, thus determining
the current path vector, the user's profile is updated to
reflect the state of the match between the present node's
selection criteria and the user's profile. In this
way, the playback algorithm "learns" about the user's preferences.
If, after guiding playback for a while, the user ceases
to make selections, playback may be continued automatically
utilizing those stored preferences. In effect, the playback
algorithm acts on behalf of the user, as adapted from the
history of the user's path through the synthetic network.
Either the adapted user profile, or the initial user profile
may be selected to play back a database path automatically,
without user intervention. This mode of operation is called
"autoplay".
The ImaginOn
playback software maintains a history of all user preferences
and selections since the time of program initialization.
This user history may be used by the database transform
process to set the selection criteria and filters for creation
of a new output database to be made from any source database.
The new output database can be grafted onto the existing
synthetic network, or a new network can be created. If "learned"
criteria are used to drive the database transformation,
the transformation itself can then be considered adaptive
with respect to the user's history of preferences.
Variable
playback resolution
By setting the playback parameters for holding data pages
on screen time and the rate at which the alternating branch
choices "flip", the overall speed of path playback can be
controlled by the user. When these hold and flip times are
set very low, a fast-forward effect results. This provides
the user with a kind of skimming,
low-resolution view of the paths.
Hierarchical
playback
If the user does not select autoplay mode and never
makes a branch choice, playback proceeds by default from
Trunk Node to Trunk Node. Since Trunk Nodes represent the
main "stems" of the n-dimensional tree, the user will only
see data pages along those main, top-level paths. If the
user makes only one branch choice per Trunk Node, only the
first Branch Node off of each Trunk Node is displayed, thus
providing a view of the data along only the first layer
of branches in the tree. This manner of playback proceeds
successively down through the layers of the tree. Thus,
hierarchical playback in which only paths down to a user-selectable
level of interest in the synthetic network are enabled.
|
