Transcript Query Processing

Query Processing
Basic Concepts

Query Processing – activities involved in
retrieving and manipulating data from
the database:


SQL query translation into low-level
language implementing relational
algebra
Query execution
2
Phases of Query Processing
3
Relational Algebra


Relational algebra defines basic
operations on relation instances
Results of operations are also relation
instances
4
Operations

Most of these operation can be
summarized as being concerned with:



Manipulation (editing and modifying)
Presentation
Analysis (indexing and searching)
5
Range of Operations
Operation
Text
Audio
Graphic
Image
Animation
Video
Manipulation
• Character
• String
• Editing
•Sample
•Waveform
•Audio editing
•Primitive editing
•Structural editing
•Shading
•Geometric
•Pixel operation
•Filtering
•Primitive editing
•Structural editing
•Frame manipulation
•Pixel operation
Presentation
•
Formatting
• Encryption
• Sorting
•Synchronization
•compression
•Conversion
•Mapping
•compression
•Lighting
•Rendering
•viewing
•Compositing
•Compression
•conversion
•Synchronization
•Compression
• rendering
•Synchronization
•Compression
•Video effects
•Mixing
•conversion
Analysis
•Indexing
•searching
•Indexing
•searching
•Indexing
•searching
•Indexing
•searching
•Indexing
•searching
•Indexing
•searching
6
Query Decomposition





Analysis
Normalization
Semantic analysis
Simplification
Query restructuring
7
Relational Algebra Expressions



The result of a relational operation is a
relation instance
Relational algebra expression combines
relation instances using relational
algebra operations
Relational algebra expression produce
the result of a query
8
Simple SQL Query
SELECT <select-list>
FROM <table ist>
WHERE <search condition>
Group By <grouping column list>
Having <search condition>
9
Conceptual Evaluation
Strategy for Simple Query




Compute the cross-product of tables in
from-list
Delete those rows which fail the
qualification condition
Delete all columns that do not appear in
the select-list
If DISTINCT clause is specified,
eliminate duplicate rows.
10
Nested Queries

Query block:




Single SELECT_FROM_WHERE expression
May include GROUP BY and HAVING
Query block – basic unit that is
translated into RA expression and
optimized
SQL query is decomposed into query
blocks
11
Querying MMDBMS

Process of querying multimedia can
approach in two ways:


‘What’ information can be retrieved
‘How’ information can be retrieved
12
‘What’ Approach

Divided into 3 levels of complexity

Level 1, Retrieval of Primitive Features



Such as color, shape, texture, spatial location and object
movement.
Query Ex.: “Find clips of objects flying from top-right to
bottom-left of screen”
Level 2, Retrieval of Logical Process


Related to the identity of object within the media
Query Ex.: “Find a clips of an aero plane taking-off”
13
‘What’ Approach (cont.)

Level 3, Retrieval of Abstract Attributes



Associated with an understanding of the nature or purpose of
the object
Query Ex.: “Find a picture of nutritional disasters”
Level 2 and 3 are regarded as Semantic
Media Retrieval.

However, Success in answering multimedia query is largely
limited to level 1. The difference between simple queries at
level 1 and those at level 2 and 3 has been called the
semantic gap.
14
‘How’ Approach

This approach can be classified on the
basis of whether is retrieved by:



Attribute-based retrieval
Text-based retrieval
Content-based retrieval
15
‘How’ Approach

Attribute-based retrieval (ABR)



ABR is a method that uses a set of structured attributes in the
same way as traditional DBMS.
It uses essentially the similar principles, except that these must be
able to cope with gigantic media object such as video clip.
This method can be particularly effective with text. However, the
method does not make use of the rich content of image and
retrieve information so that is essentially limited to level 1 queries.
16
‘How’ Approach

Text-based retrieval (TBR)



TBR methods work by adding annotations, usually brief
descriptions combined with some structured data.
An example of system with this capability was the Kodak’s picture
exchange.
Disadvantage of the system is that they are very difficult in
practice.
17
‘How’ Approach

Content-based retrieval (CBR)



CBR is developed to try to overcome some of the difficulties of
TBR.
The idea is that the important details can be extracted from the
media
by automatic method which will be more efficient for data capture
and reliable for retrieval.
18
Ontology

Providing a shared understanding of the
application domain that can be communicated
between people and computer and
incorporated in the database as part of the
metadata.

It means that key information about the kind of object in the
database can be captured and reused many times for many
different queries with any kind of media data.
19
Metadata Usage in Querying


Considering role of metadata for media
separation
Considering design to classify metadata and
relate this to three type of information
retrieval



Content Independent – used in ABR
Content Descriptive – used in TBR
Content Dependent – use in CBR
20
Role of Metadata in Querying
Query Metadata
Conceptual data view
Meta-Correlation
Ontologies
Image Metadata
Text Metadata
Media dependent
Media independent
metadata
Media dependent
Media preprocessor
Media preprocessor
Text
Image
Example of role of metadata in Querying
Physical
Storage view
21
Query Language
Structured Query Language


Query languages are generalized computer
language that is used to interrogate database
and information systems.
Query languages can be classified according
to database query languages or information
retrieval query languages.
Marina G. Erechtchoukova
23


Structured Query Language (SQL) scope includes
data insert, query, update and delete, schema
creation and modification, and data access control.
SQL was developed at IBM by Donald D. Chamberlin
and Raymond F. Boyce in the early 1970s. This
version, initially called SEQUEL (Structured English
Query Language), was designed to manipulate and
retrieve data stored in IBM's original quasi-relational
database management system.
Marina G. Erechtchoukova
24


The most common operation in SQL is the query,
which is performed with the declarative SELECT
statement. SELECT retrieves data from one or more
tables, or expressions.
Standard SELECT statements have no persistent
effects on the database. Some non-standard
implementations of SELECT can have persistent
effects, such as the SELECT INTO syntax that exists
in some databases.
Marina G. Erechtchoukova
25

Queries allow the user to describe desired
data, leaving the database management
system (DBMS) responsible for planning,
optimizing, and performing the physical
operations necessary to produce that result
as it chooses.
Marina G. Erechtchoukova
26

A query includes a list of columns to be
included in the final result immediately
following the SELECT keyword. An asterisk
("*") can also be used to specify that the
query should return all columns of the
queried tables. SELECT is the most complex
statement in SQL, with optional keywords and
clauses that include:
Marina G. Erechtchoukova
27


The FROM clause which indicates the table(s)
from which data is to be retrieved. The FROM
clause can include optional JOIN subclauses
to specify the rules for joining tables.
The WHERE clause includes a comparison
predicate, which restricts the rows returned
by the query. The WHERE clause eliminates
all rows from the result set for which the
comparison predicate does not evaluate to
True.
Marina G. Erechtchoukova
28

The GROUP BY clause is used to project rows
having common values into a smaller set of
rows. GROUP BY is often used in conjunction
with SQL aggregation functions or to
eliminate duplicate rows from a result set.
The WHERE clause is applied before the
GROUP BY clause.
Marina G. Erechtchoukova
29


The HAVING clause includes a predicate used to filter
rows resulting from the GROUP BY clause. Because it
acts on the results of the GROUP BY clause,
aggregation functions can be used in the HAVING
clause predicate.
The ORDER BY clause identifies which columns are
used to sort the resulting data, and in which direction
they should be sorted (options are ascending or
descending). Without an ORDER BY clause, the order
of rows returned by an SQL query is undefined.
Marina G. Erechtchoukova
30
Query Language
Object Oriented Query Language
Evolution of Design Approach
in Multimedia
Object Oriented Query
Language
Figure 1 : Media class and Its subclass
Object Oriented Schema
Declaration
Event & Content-Based Queries
for Image / Video Data

Spatial

Temporal
Spatial Object
Temporal Object
Queries for Multimedia

Multimedia Document Retrieval

Playout Control
Thanks for Your Attention