Multimedia Database Query Languages and Processing Notes
- Multimedia Database System Workflow:
- Natural Language Query: An exemplary query might be: "Give me all images and their titles, which are similar to my example image and were taken in Berlin, whereupon the similarity to the example image is much more important than its association to Berlin. In addition, the data size should not exceed 2048Kb."
- Declarative Representation: Transferred from natural language or visual interfaces into a formal query language like MOQL or SQL/MM.
- Query Processing & Optimization: Includes a parser, query optimization, and the selection of access algorithms and index structures within the data model.
- Algebraic Representation: The query is converted into a query execution plan based on multimedia algebra.
- Multimedia Data: Involves storage for descriptive information (metadata), images, video, and audio (excluding streaming in this specific context).
- Classical Exact Queries: Target non-multimedia attributes (e.g., file size, date, location string).
- Semantic Queries: Determine results based on descriptions of semantic content, such as the occurrence of specific objects or persons.
- Syntactic Queries: Target basic physical characteristics of the media, such as resolution or frame rate.
- Similarity Queries (Content-Based): Applied to low-level features (e.g., color distributions) to find media with similar features (e.g., "images similar to my query image").
- Correlation Queries: Identify spatial and temporal correlations, such as "a red ball next to a yellow one."
- Universality: Must support querying "classical" database attributes.
- Content-Based (Semantic) Queries: Searching for higher-level objects.
- Spatial Queries: Dealing with the position and layout of objects.
- Temporal Queries: Dealing with time-based sequences (primarily video/audio).
- Content-Based Similarity Queries: Managing feature-level comparisons (low-level).
- Fuzzy Queries: Handling imprecise parameters and ranking.
- Presentation: Options for how the result set is displayed to the user.
History and Categories of MMQL
- History (1980 - 2000):
- Focus on image data (specifically medical images).
- Mainly spatial and similarity-based queries.
- Primarily extensions of existing languages like SQL and OQL.
- History (2001 - 2011):
- General multimedia/multimodal focus.
- Introduction of temporal queries and Relevance Feedback.
- Emergence of new standards like SQL/MM and MPQF.
- Integration of fuzzy logic, user preferences, and thresholds.
- Categories of MMQL:
- 1st Category: Extensions of SQL and OQL: Examples include MOQL, SQL/MM, and de facto provider standards like Oracle MultiMedia.
- 2nd Category: "From Scratch" Languages: Examples include VideoSQL and MPEG Query Format (MPQF).
- Origin: Based on the ODMG object model and Object Query Language (OQL). It extends OQL to handle complex objects, object identity, and path expressions.
- Basic Syntax:
select [ distinct ] projection_attributes from query [ [ as ] identifier ] where query
- Extensions in the WHERE Clause:
- Spatial relations (
spatial_expression). - Temporal relations (
temporal_expression). contains relation (contains_predicate).- Presentation functions using the
present clause.
- Spatial Predicates:
- Points/Lines/Regions:
nearest, farthest, within, midpoint, centroid, inside, cross, intersect, cover, coveredBy. - Directions:
left, right, above, below, front, back, north, south, west, east, northwest, and combinations (e.g., front_left).
- Spatial Functions:
- Calculates values like
length, slope, area, perimeter, interior, exterior, or mbr (Minimum Bounding Rectangle). - Example:
select lake, area(lake.region) from Lakes lake where lake.region coveredBy SachsenAnhalt and area(lake.region) > 10.
- Temporal Relations:
- Based on time intervals with start and end points.
- Relations:
equal, before, after, meet, metBy, overlap, overlappedBy, during, include, start, startedBy, finish, finishedBy. - Continuous Media Functions (Video):
prior, next, firstFrame, lastFrame, firstClip, lastClip, nth. - Camera Motion Predicates:
zoomIn, zoomOut, panLeft, panRight, tiltUp, tiltDown, cut, fade, wipe, dissolve.
- Presentation Functions:
- A new
present clause allows users to define layout: atWindow, play, parStart, display.
- VisualMOQL (DISIMA Project): A visual interface for declarative, content-based queries on "salient" objects. It allows users to define image properties (color, histogram) and relationships (spatial distance/orientation) graphically, which is then translated into MOQL SELECT statements.
- Standardization: ISO/IEC 13249. It defines class libraries as first-class SQL types using SQL:1999 instructions. International standard since 2002.
- Structure:
- Part 1: SQL/MM Framework: Provides overview and conformity rules.
- Part 2: SQL/MM Full Text: Defines UDTs
FullText and FT_Pattern. Includes search methods Contains (Boolean) and Rank (Implementation-dependent real value). - Part 3: SQL/MM Spatial: Defines 2D User Defined Types (UDTs) like
ST_Point, ST_Curve (ST_LineString, ST_CircularString), ST_Surface (ST_Polygon), and collections. - Part 5: SQL/MM Still Image:
- UDT SI_StillImage: Encapsulates
SI_content (BLOB), SI_format, SI_height, SI_width. - UDT SI_Feature: Subtypes include
SI_AverageColor, SI_ColorHistogram, SI_PositionalColor, and SI_Texture. - Similarity Comparison: Every feature has an
SI_Score method that computes the distance between an image and a feature, returning a value between 0 and 1.
- Overview: Standardized since 2008 as Part 12 of MPEG-7. Based on XML Schema and decoupled from specific metadata standards (supports any XML metadata descriptions).
- Main Categories:
- Management: Locating search engines (MMRS); handles scenarios where MMRS are known or unknown.
- Input Query Format: Structure includes
QFDeclaration (resource definitions), OutputDescription (result structure/XPath), and QueryCondition (filters). - Output Query Format: Defines the standardized result list.
- Query Capabilities:
- Supports synchronous and asynchronous modes and timeouts.
- Fuzzy Boolean Operators: AND, OR, XOR with
ScoringFunction, preferenceValue, and thresholdValue. Results in a rank and confidence evaluation.
Result Presentation and SQL+D
- Result Presentation: MMDBS requires complex handling of spatial/temporal info for media composition and synchronization.
- SQL+D: An extension for object-relational SQL allowing display layout specification.
- Example:
SELECT a,v FROM MONUM WHERE country='USA' DISPLAY panel main WITH a AS audio A, v AS video V ON main.Center(Overlay), SHOW V,A.
- Requirements: Definition of a data model (salient object management), MM operations (Similarity Join), and a formal algebra for optimization strategies.
- Similarity Algebra:
- ϵ-similarity (Range Query): X⊆S∧∀x∈X⋅∥q.fq−x.fS∥≤ϵ.
- k-NN Similarity: X⊆S∧Card(X)=k∧∀x∈X;y∈X∖S⋅∥x.fS−q.fq∥≤∥y.fS−q.fq∥.
- Similarity-Based Join Operator (⊗ϵ):
- An asymmetric binary operator applied to image tables.
- Symmetric Join (⊕ϵ): Defined as (M1⊗ϵM2)∪+(M2⊗ϵM1).
- Mine Operator: Formally
Mine(M1 ⊗ε M2) = M2 ⊗ε M1. It significantly reduces the cost of deriving symmetric joins once one side is computed. - Traditional vs. MM Optimization:
- Traditional: Focuses on join order selection and moving selections to the lowest level.
- MM Optimization: Selection predicates (e.g., similarity functions) can be more expensive than joins. The heuristic "Move selection predicates to lowest level" often fails here.
- Selectivity Approximation for Range Queries:
- The selectivity of k-NN is always k, but range query selectivity varies.
- Methods:
- Sampling: Fast but poor for multidimensional data.
- Histogram-based: Good for updates but bucket size grows exponentially with dimensionality.
- Wavelets/DCT: Transformation-based; hard to update.
- Data Density: Uses clustering algorithms (e.g., DBScan) to find the hypervolume of clusters. Effective for predicting but high initial computation time.
- Clustering Algorithm for Selectivity:
- Cluster data using density-based algorithms (DBScan).
- Determine the MBR for each cluster.
- Compute cluster density: Density(C)=Vol(C)#P.
- Approximate selectivity of query point Q with radius r: Selectivity(Q,r)=∑Ci∩Q=∅Density(Ci)×Vol(Ci∩Q).
- Use the error-minimizing clustering for the given query radius.
- Example execution times: Improvement from 89.2s to 45.8s with clustering optimization.