ACM Multimedia 98 - Electronic Proceedings

SQL+D: Extended Display Capabilities for Multimedia Database Queries

http://cs.utep.edu/chitta/papers/sqld

ACM Copyright Notice

Abstract

The answer to queries posed to multimedia databases contains multimedia objects. To display these objects, a browser or an ad-hoc program is usually required. In [BGS98] we presented SQL+D, which gives users the ability to specify, within a SQL query, a screen layout to be used to show the answer to a query. In this paper, we present a greatly revised version of SQL+D. Among other improvements, it now has a Database Interface that allows local and remote access to databases, a way to specify temporal presentations, and data visualization features that allow specification of complex graphs and charts.

Keywords

Multimedia, Query Language, Database, Display, Visualization, Presentation, Time Constraints

Table of Contents

• Introduction
• Database Interface
• Changes to Display Specifications
• SQL+D Queries
• SQL+D Query Syntax
• Display Elements and Grouping
• Graphs and Charts
• Graphs
• Charts
• Temporal Presentations
• Simple Presentations
• Complex Presentations
• Evaluation of Temporal
Constraints
• Specifying Temporal Presentations in SQL+D
• Related Work
• Bibliography

1 Introduction

To display answers to queries to multimedia databases other than in a traditional "spreadsheet" fashion, a programmer needs to write a graphical interface in Power Builder or a programming language. Another option is to use a multimedia browser, such as the one presented in [Ca96]. However, this forces the user to follow the paradigm used by the browser, instead of allowing the freedom of a query language.

The design of special graphical interfaces for these query results becomes even more challenging if we wish to specify not only how but when the different multimedia elements should be shown, in what is called a multimedia presentation or temporal presentation.

In [BGS98] we proposed the first version of an extension to SQL, SQL+D, that allows users to dynamically specify how to display answers to queries posed to multimedia databases. It provides tools to display multimedia data plus other traditional GUI elements such as boxed text, checkbox, list, and button. The architecture of SQL+D was presented in [BGS98] . A schematic is shown in Figure 1.

The new version of SQL+D, presented here, includes:

• The full implementation of the Database Interface, allowing users to= connect to local and remote ODBC (or JDBC) compliant database, such as ORACLE or Microsoft Access.

• Simplified display specifications syntax and instantiation of display elements.

• Implementation of directed and undirected graphs as a visualization aid for extracted data.

• Implementation and new syntax of charts with categorization, directed and undirected graphs for advanced visualization of data.

• Implementation and expanded features for temporal presentations with time constraints using simple and intuitive in-the-query specifications.

• Research efforts in temporal presentations have focused on a fixed set of elements and constraints [CHIMP,CPS96], rather than on generalized specifications for a whole answer set.

SQL+D differs from other efforts in that it is specifically designed for querying multimedia databases. It emphasizes in-the-query, by-the-user specification of the display of the output data. In contrast, others have focused on specification of the query, data visualization, or data browsing. SQL+D allows all of these, and we have done browsers and visual querying applications as a proof of concept. By proposing SQL+D as a language extension to SQL, we intend to maintain the flexibility that allowed SQL to be adopted as the query language of choice by a great number of database management systems and browsers, as well as by many programming languages that allow embedded SQL queries. If, instead of a browser or data visualization application, we provide an interpreter for SQL+D or a class or a dll that can be included in a program, we are providing those DBMS, browsers and programming languages with the querying power of SQL, plus with a very powerful toolset to construct multimedia displays and presentations with no programming involved.

Table of Contents

2 Database Interface

JDBC consists of a set of classes and interfaces written in the Java programming language that provides a standard API for developers to write database applications using pure Java.

JDBC includes a driver to handle the low-level interface with the database, and a set of classes for high-level programming. With them, we have constructed a true Database Interface to work with SQL+D, allowing the Interpreter to access local and remote databases. This feature allows us to access databases through the Internet. We are currently working on a web-based interface for SQL+D.

As shown in Figure 1, the Interpreter requests a connection to the database, obtained by the Database Interface, then it allows querying the database through SQL+D queries. It splits the SQL+D query into two parts: the SQL query and DISPLAY specifications. It sends the SQL part of the query to the Database Interface, which writes the result in a file. The DISPLAY specifications are stored in another file. These two files are sent as input to the Display Controller, which analyses the data in these two files and shows the multimedia display.

We are currently working in a more advanced implementation where only a portion of the data is sent at any one time, keeping the connection to the database open so that new records are brought in as needed to speed up query processing.

There have been some data models that consider non-traditional or user-defined data types, such as the Object Oriented and Object Relational data models [St96] . Such a data model will be the optimal implementation of a multimedia database. But, switching from one data model to another is very costly. The relational model can be used, with certain limitations, if the database contains only the file names of the different multimedia elements, and it is at display time that the actual elements are loaded. This is the model we assume here. The Display Controller loads the files and displays them using its built-in display mechanisms.

However, SQL+D is not intended to be used solely with relational databases. The current draft of the ANSI/ISO revision to SQL (known as SQL3) incorporates object extensions, and user defined abstract data types among other features that facilitate multimedia data storage in an object oriented fashion [SQL3] . SQL+D serves its purpose equally well in this environment.

Database Interface

3 Changes to Display Specifications

3.1 SQL+D Queries

An SQL+D query consists of a standard SQL query, or an SQL query plus a DISPLAY statement. The purpose of an SQL+D query is to specify the records of a database that need to be retrieved, given certain conditions, and to specify how the different attributes of the records should be arranged on an output screen and what kind of display mechanism should be used to display them.

Execution of a DISPLAY statement crates a visible display area or display window on the computer monitor, where data is to be displayed. The display window contains the following elements:

1. A single main panel that contains all other elements.

2. A set of navigation buttons that allow the user to move from record to record, quit the display window, and interrupt presentations.

3. A set of uniquely identified container panels.

4. A number of data elements , that are either:

• constant data elements, such as fixed text or image files, not database-dependant, or
• attributes from the database, a subset of the attributes used in the SELECT clause.

5. A number of display mechanisms , which display data using a pre-determined format and protocol. Display mechanisms include a video player, an image display, an audio player, a document display, and GUI elements such as a button or a checkbox.

6. A set of display elements, formed by a data element together with its corresponding display mechanism.

7. Optionally, a temporal presentation specification.

8. Optionally, an automatic skip specification.

The following expressions capture the top-level new syntax of an SQL+D query:

<query>	->	<SQL Query> | <SQL Query> DISPLAY <disp specs>
<disp specs>	->	panel <id>, <container panels> WITH <disp element> [ SHOW <presentation> ] [ AUTOSKIP <time length> ]
<container panels>	->	<panel list> ON <id>.<loc>[(<layout>)] | <panel list> ON <id>.<loc >[(<layout>)], <container panels>
<panel list>	->	panel <id> | panel <id>, <panel list>
<id>	->	<alphabetic> | <alphabetic> <alphanumeric>
<loc>	->	North | South | East | West | Center
<layout>	->	Horizontal | Vertical | Overlay

Here, the new syntax allows for nested panels to be grouped and placed together using a single statement, indicating a layout : horizontal, vertical, or overlay. This same grouping feature was added to display elements , and will be discussed in the following subsection. Particularly, the "overlay" attribute allows panels to be placed on top of panels, and then shown at different times during a presentation. The relative location of a panel (and also of display elements) is now indicated using a "." as separator.

Changes to Display Specifications

3.2 Display Elements and Grouping

For each data element that needs to be displayed, the user specifies a how and a where . It is in this area where the impact of grouping is felt the most, making display specifications simpler.

In the initial version of SQL+D the user needed to specify element by element how and where to display it. This made some panel specifications with multiple elements cumbersome to write. For example, the SQL+D query to create the screen shown in Figure 2 required two more panel specifications and two more display element specifications, plus a lot more thinking to arrange all the panels and data elements than the query made using the new syntax, shown in Query 1.

The new syntax for the display element specifications looks as follows:

<disp element>	->	[ALL | DISTINCT] <data elem list> AS <disp mechanism> [<id>] ON <id>.<loc>[(<layout>)] [<trigger>] | <disp elem list> ON <id>.<loc>[(<layout>)] [<trigger>] | <graph specs> | <chart specs>
<disp elem list>	->	[ALL | DISTINCT] <data elem list> AS <disp mechanism> [<id>] | [ALL | DISTINCT] <data elem list> AS <disp mechanism> [<id>], <disp elem list>
<data elem list>	->	<data elem> | <data elem>, <data elem list>
<data elem>	->	Attr | <constant>
<constant >	->	filename | "char string"
<trigger>	->	TRIGGER query filename [( <parameters> ) ] | TRIGGER executable filename [( <parameters> )]

Another advantage of the group option is that it makes the specification of overlays clearer. Before, it was assumed that when two display elements were specified on the same location, the user meant an overlay of the second over the first. Using the new syntax, the overlay of polygons over an image would be indicated as follows:

Also, now the user can uniquely identify a display specification, so that it can be used in a presentation. The identifier of a display element is given right after the display mechanism is identified. For example, for an attribute "Video Clip" to be displayed as video, we can specify:

and later refer to this particular display element as "V₁". This way, one attribute or constant might be displayed in more than one way and the two used in a presentation independently.

The display mechanisms themselves remained unchanged. Their syntax follows.

<disp mechanism>

->

audio | list | video | oval | text | button | checklist | image | choice | polygon | boxedtext | document | user defined data type

Changes to Display Specifications

Table of Contents

---

4 Graphs and Charts

SQL+D allows charts and graphs to be defined as part of the display specifications. Even though some systems have been proposed [Cr97,AS94] that allow users to design screens that display query results as plots, graphs, and charts, they do not allow or is difficult to specify directly the display of results of online and ad-hoc queries.

4.1 Graphs

Graphs in SQL+D are used in its mathematical sense: a nonempty set of vertices and a set of vertex pairs (v₁, v₂), called edges form a graph. In SQL+D, we specify a graph by specifying its vertices and edges as follows:

<graph specs>

->

nodes(Attr1, Attr2, ..., Attrn) AS <disp mechanism> ON <id> [<trigger>] | edge(Attr1 TO Attr2) [LABEL string | LABEL Attrn] ON <id> [<trigger>] | edge (Attr1, Attr2) [LABEL string | LABEL Attrn] ON <id> [<trigger>]

Graphs are defined by their nodes and edges. Semantically, the attributes listed in the nodes statement become the valid arguments in either of the edge statements: the first one, with the (Attr₁ TO Attr₂) argument, specifies a directed edge from node Attr₁ to node Attr₂. The second one specifies an undirected edge between the two nodes.

Example 1.

Consider a database for a University Undergraduate Studies plan, containing class ids and prerequisites for each career, and other general information about the curriculum required for students to earn different degrees. Part of the schema looks as follows:

PREREQ (id, prereq)

CLASS (id, name, descrip)

REQ (major, classid)

where all the attributes of all the relations are character strings.

We are interested in displaying a directed graph of the classes needed to complete a Bachelor in Computer Science. The query would look as follows in SQL+D:

SELECT	REQ.id, PREREQ.prereq
FROM	PREREQ, REQ
WHERE	REQ.major = "BSCS" AND REQ.prereq = PREREQ.id
DISPLAY	panel main
WITH	nodes(classid, prereq) AS boxedtext ON main.Center, edge(prereq TO classid) ON main.Center

Query 2. Query to display a directed graph representation of the CS degree plan.

The query results are shown in Figure 3. Only a single instance of each value is shown as a node, and the edges, as specified in the WITH clause by edge(prereq TO classid), go from a node with value V₁ to a node with value V₂ whenever there is a tuple (V₂, V₁) in the answer set. A list of the edges shows up on the right portion of the screen to aid the user when identifying edges.

Figure 3. Display generated by Query 2

Graphs and Charts

4.2 Charts

Charts of four different types can be specified in SQL+D: pie, bar, line and xy-scatter charts. To specify a chart, the user enters a two or three-tuple with values to plot in any of these charts. We will refer to the two-attribute definition as an "xy chart" and to the three-attribute definition as a "categorized chart". The following syntax is used to specify charts:

< chart specs>	->	(AttrX, AttrY) AS <chart elem> ON <id> [<trigger>] | (AttrX, AttrY, AttrZ) AS <chart elem> ON <id> [<trigger>]
< chart elem>	->	linechart | barchart | piechart | xyscatter

The two-attribute specification is straightforward: Attr_X is used as the X axis (range) for line, bar and scatter charts, and Attr_Y as the Y axis (value). For the pie chart, Attr_X gives the categories in which the chart is to be divided, and Attr_Y is evaluated to assign the proportional arc to that category.

Example 2.

Consider a database to keep statistical information about the recreational activity prefered by people in different states. The schema looks as follows:

ACTIVITY (state, activity, pop)

where all the attributes are character strings.

To see how the people in Texas spend their free time, we might submit Query 3. In this query, we included both a bar chart and a pie chart , to see the different displays that might be obtained with the same data. The resulting display is shown in Figure 4.

SELECT	ACTIVITY.activity ACTIVITY.population
FROM	ACTIVITY
WHERE	ACTIVITY.state = "Texas"
DISPLAY	PANEL main
WITH	(activity, pop) AS barchart ON main.West, (activity, pop) AS piechart ON main.East, "Recreational Activities Preferences" AS boxedtext ON main.North

Query 3. Query to display a bar chart of prefered recreational activities.

The two-attribute line chart is similar to the bar chart. A categorized chart will group values on Attr_Z (categories) and plot all the resulting Attr_X, Attr_Y series in the same xy plane, using a different color for each category.

Figure 4. Display generated by Query 3.

Graphs and Charts

Table of Contents

---

5 Temporal Presentations

The terms multimedia document, multimedia or temporal presentation, have been used in the literature interchangeably. We will distinguish a multimedia document from a multimedia presentation or temporal presentation as follows:

Multimedia document.

A multimedia document is composed of a set of elements of different types (such as video, audio, document, image, and others) together with a set of spatial requirements or constraints.

Multimedia presentation.

A multimedia presentation or a temporal presentation P is composed of a multimedia document and a set of absolute or relative temporal constraints. It has a specific duration |P| associated to it, plus a start point S_P and an end point E_P.

We define absolute and relative temporal constraints as follows:

Absolute temporal constraint.

An absolute temporal constraint involves only a specific element e and/or P, S_P, and E_P.

Relative temporal constraint.

A relative temporal constraint involves two or more elements and/or P, S_P, and E_P.

SQL+D lets the user specify multimedia documents and multimedia presentations that apply to the answer set of a database query. A multimedia document is specified by the panels and the display elements in the WITH clause, and this specification is like a template. When the answer set becomes available each tuple is displayed using the template. That is, each tuple becomes a multimedia document.

We are interested in specifying a generic presentation that will work for all the documents, just as we specified a generic document in the WITH clause. We have classified presentations as simple (which we also call "slide show") or complex , which will be further discussed in the following subsections.

5.1 Simple presentations

The simplest of multimedia presentations, as used generally in the literature, is what we have defined as a multimedia document. It doesn't obey any explicit time constraints, but only space constraints. An SQL+D DISPLAY clause can be understood as a simple presentation that shows all the specified elements at the same time at given locations.

One step further in complexity shows a set of such multimedia documents as a slide show, one after the other, placing a single time constraint on the length of time each document is shown. We need only to define the duration of the (simple) presentation P. In SQL+D, this is achieved by adding an AUTOSKIP clause at the end, after the WITH clause, with the desired time length specification |P|. The start point S_P is the point in time when all the elements of the tuple are loaded into the document, and its end point E_P is equal to S_P + |P|. The syntax for AUTOSKIP was presented in Section 3.1.

The duration can be fixed, in minutes, seconds and hundreths of a second, or it might be calculated. For example, AUTOSKIP 3 displays each tuple for 3 seconds, while AUTOSKIP LEN(V₁) displays each tuple for as long as it takes V₁ to run. AUTOSKIP MAX(V₁, A₁) checks which of V₁ and A₁ takes the longest to run, and then displays the record for that long before going to the next.

Temporal Presentations

5.2 Complex presentations

SQL+D also provides for more complex presentations, where several objects are shown obeying given time constraints.

Basically, to specify a complex presentation, the user needs to add a SHOW clause to the SQL+D query. The spatial constraints of the elements on the screen are specified in the DISPLAY clause. There, each display element must be identified uniquely. This unique identifier is then used within the SHOW clause to specify the temporal constraints for a presentation.

5.2.1 Evaluation of Temporal Constraints

Temporal constraints might be defined for all objects, including objects that we regularly do not associate with time, like a fixed image or text. We use a simpler definition of temporal constraints than the one presented by Candan, Prabhakaran and Subrahmanian in [CPS96] .

What the user specifies in a SQL+D query is internally translated to mathematical expressions (the actual temporal constraints). Formal algorithms are followed to evaluate the temporal constraints and find a final "plan" for the presentation, with absolute starting times for all elements. Depending on the type of elements involved in an unfeasible presentation, SQL+D applies different conflict resolution policies.

Complex Presentations

5.2.2 Specifying Temporal Presentation in SQL+D

To express presentations in SQL+D,m the user needs first to "visualize" the presentation, just as he needed to visualize the screen layout in order to define it as an SQL+D query. To design a temporal presentation, the user "sketches" the presentation on a time line using different layers to accommodate the display elements as desired, like the sketch shown in Figure 5, corresponding to the presentation described in Example 3. L₁ and L₂ are virtual "layers" that aid the user in incorporating all the elements into a presentation. This sketch can then be translated into temporal constraints in a SHOW clause.

Figure 5. Sketch of a presentation, using layers for overlapping display elements.

The SHOW clause indicates for all or some of the attributes displayed, how they should be presented: how long they should be shown, in which order, and in which combination. There are many presentation commands available, and a specification can be as complex or as simple as desired.

The simplest commands specify that the presentation sequence of two attributes is serial if the attributes are separated by semicolon or the word THEN, or parallel if separated by "||" or by the word SYNCH (synchronous).

The length of time an attribute or other display element is displayed is either its total running time or an (optional) time length specification. If the total running time of an element is less than the indicated time length, then it runs its length plus a "silence" or "pause" for the remainder time and then the presentation continues as specified.

Example 3.

Say an Environmental Agency employee wishes to use a database with information about the great monuments of the world for a special presentation. The schema looks as follows:

The presentation specifications can be sketched as shown in Figure 5, and is translated into the SHOW clause of the following SQL+D query:

A sequence of the resulting presentation is shown in Figure 6 and Figure 7. All layers start at the beginning of the presentation. The user can also specify an offset.

The user has options as far as how to express the presentation. For example, for the presentation above, instead of writing V ON L1 and then A FOR LEN(V) ON L2, it would be equivalent to say V SYNCH A. These options are intended to facilitate the mapping between time/object layered diagrams into SQL+D statements.

This query might also be entered to the system via a graphical query interface, so the user doesn't have to write the actual SQL+D query, but in this paper, we want to emphasize how queries are expressed in SQL+D and the features of SQL+D for temporal presentations, not how queries are entered.

To specify a time length, the user can use one of the following functions:

• LEN(display element): returns the duration of the specified display element.
• LEN(SHOW): returns the calculated running time of the temporal presentation specified in the SHOW clause. Can only be used in an AUTOSKIP clause.
• MAX(e₁, e₂, ...,e_n), where e_i is a display element: returns the duration of the element from e₁, e₂, ...,e_n that runs the longest.

Related Work

SQL+D is related to work in the areas of multimedia data display, multimedia database querying, browsing, analyzing and visualization. A full analysis of how it compares in these three areas to other work is presented in [BGS98].

Version 2 of SQL+D touched deeper on data visualization and presentation, so an updated analysis in these two areas is presented in the full version of this paper, available at http://cs.utep.edu/chitta/papers/sqld

Bibliography