VLDB Journal 2009, Probabilistic schema mappings

"Data Integration with Uncertainty"

SIGMOD 1997, Online Aggregation

"Online Aggregation"

This paper proposes a new online aggregation interface that permits users to observe the progress of their aggregation and control execution on the fly. The system provide an answer for an aggregate query as long with confidence and a confidence interval. While the query is executed, the confidence increases.

Related work:
(a) Online Analytical Processing (OLAP)
(b) "fast-first" query processing that returns the first few tuples of the query
(c) APPROXIMATE: if the query is stopped before completion, a superset of the exact answer is returned in a combined extensional/intentional format.

When the records are retrieved in random order, a running aggregate can be viewed as a statistical estimator of the final query result.

Performance goals:
(a) minimum time to accuracy
(b) minimum time to completion
(c) pacing

Problems:

(1) statistically meaningful estimates of the precision of running aggregates are available only if records are retrieved in random order. This can be guaranteed by:
(a) hash scans: records are stored in an unspecified order. the method of CHOICE
(b) index scans: scanning an index returns tuples either in order based on some attributes (B+ --trees), or in groups based on some attributes (hash or multi-dimensional indices). Both of these techniques are inappropriate for online aggregation queries
(c) sampling from indices: NOT implemented in this project
(2) sort-based grouping algorithms are inappropriate for online aggregation: sorting is a blocking algorithm thus no output can be produced until the entire input has been processed and the aggregate for a group is computed to completion before the second group is considered.
(3) Sort-merge join are unacceptable for online aggregation
(4) hybrid hash join is useful only the inner relation is small, and in particularly if it fits into the buffer space
(5) pipeline hash join is a non-blocking hash join that treats its inner and outer relations symmetrically. Is slower than hybrid but it may fit better the online aggregations
(6) nested-loop join is the safest technique


TO DO: hybrid-hashing: what is this ? "Hashing methods and relational algebra operations." -K.Bratbergsengen, VLDB 1984

Solutions:

(a) Index Striding : the groups that have only few data are updated very infrequently. To avoid this, a new index search schema, that uses a weighted round-robin technique among all groups) is used. this technique discovers the groups first and then retrieves the tuples in a round-robin fashion.

REFERENCE:

"Online Aggregation" -Joseph M.Hellerstein, Peter J.Haas, Helen J.Wang

"Online Aggregation" -Joseph M.Hellerstein, Peter J.Haas, Helen J.Wang

CIDR 2009, SciDB

"Requirements for Science Data Bases and SciDB"

Put together a set of requirements for a new science database system. The collection of data comes from astronomy, particle physics, fusion, remote sensing, oceanography and biology.

Main problems with the already existing models:
-- tables are a natural data model but, usually, it does not match the users needs
-- there is an increasing need for array data model but simulating arrays on top of tables is difficult and inefficient.
-- biology and genomics users want graphs and sequences which cannot be supported by tables or array data model
-- users with solid modeling applications want a mesh data model
-- there is a need for a mix of specialized DBMSs

SciDB supports multi-dimensional, nested array model with array cells containing records, which in turn can contain components that are multi-dimensional arrays.

UDF can be used to enhance arrays. Any function that accepts integer arguments can be applied to the dimensions of an array to enhance the array by transposition, scaling, translation and other co-ordinate transformation.

Operator supported (by category):
--> structural operators: creates new arrays base purely on the structure of the inputs.
------ ex: subsample -> takes as input the array and a predicate over the dimensions of A and outputs an array with the same number of dimensions as the input but will generally have a smaller number of dimension values.
------ reshape -> converts an array to a new array with a different shape that can include more or fewer dimensions, possibly with new dimension names, but the same number of cells. (ex: 2x3x4 array can become a 2x6x2 array or 8x3 array...etc)
------ structured-join -> restricts its join predicate to be over dimension values only
------ add dimension
------ remove dimension
------ concatenate
------ cross product

--> content dependent : the result depends on the data that is stored in the input array
------ ex: filter -> takes as input an array and a predicate over the data values that are stored in the array's cells are returns another array, with the same dimension of the initial array and NULL values for the case when the predicate evaluates to false.
------ aggregate -> takes an n-dimensional array, a list of k-grouping dimensions and an aggregate function. The output will be an array.
------ content-based Join -> restricts its join predicate to be over data values only. The output is a concatenated array with NULL cells if the predicate evaluates to false. (ex: cjoin on a m-dimensional array and an n-dimensional array is an (m+n) dimensional array.
------ apply
------ project

SciDB Features

SciDB supports the notion of history dimension. When a cell should be updated but the old value must be retained, a new dimension must be added to the array. If an update comes, the transaction adds values into appropriate cells for history=1. A new update or insertion will be written in the appropriate cell for history=2 and so on.
SciDB supports change of partitioning scheme over time. In this way, a first partitioning scheme is used for time less than T and a second partitioning scheme for time > T
FIXME: partitioning means to change dimension ?

Storage manager partition a node into disk blocks. SciDB will divide the incoming load stream into site-specific substreams. Each one will appear in the main memory of the associated node. When the main memory if full , it will form the data into a collection of buckets, compress each bucket and write it to disk.

SciDB allows uses to recreate an array by remembering how it was derived.

SciDB has as future work to handle uncertainty data, namely normal distribution for data elements. They way it approaches this problem is to copy a particular observation into multiple partitions if the observation is close to a partition boundary. In this way they ensure that "uncertain" spatial joins can be performed without moving data elements.

An INTERESTING case that fits to this scenario is the eBay search engine. They want to see how relevant is the keyword search engine. For example, given a keyword and a list of possible links related to that keyword, which one was relevant for the user. Relevant means which one was clicked by the user. Having this in mind, how can the search algorithm be modified to give a better answer next time ?

REFERENCE:

"Requirements for Science Data Bases and SciDB", M Stonebraker, J. Becla, D. Dewitt, K. Lim, D. Maier, O.Ratzesberger, S.Zdonik

ICDE 2006: UNIT

"UNIT: User-centric Transaction Management in Web-Database Systems" -Huiming Qu, Alexandros Labrinidis, Daniel Mosse

When user requests must be answered as fast as possible and using the most recent data possible, freshness and timeliness are the measures that must be take into account.
Types of user satisfaction degradation: Rejection, deadline misses, freshness misses.

USM (User Satisfaction Metric): Admission control + update frequency modulation
Admission control =adjust the user query workload by dropping those transactions which threaten the system USM
Update frequency modulation =updates the workload by intelligently reducing the frequency of updates to data that have minimal harm to the overall user-perceived freshness

General feedback control loop is used to make adjustments.

Use success ratio (=the ratio of the user queries over all user queries)
*PLUS the gain for user queries that have been accepted by the system, finished before their deadline and used fresh data
*PLUS the penality for user queries that failed, differentiated based on the type of failure.

How it works:
--> degrades the updates for the data item that the system spends too much time updating and only few queries need to access them. Use Lottery Scheduling to chose which update item to make less frequent. The larger the ticket value, the higher the probability it will be chosen as the victim, and its update frequency will be decreased.
--> once the item is chosen to be degraded its current period is increased with a certain percentage (10 %)
--> upgrade updates needs to be done when degrading updates affects the query freshness and the degrading cost becomes the leading cost in USM

TO DO: read this for the feedback control loop details:
Kang, Son, Stankovic. "Managing deadline miss ratio and sensor data freshness in real-time databases", TKDE 2004

Reference:
"UNIT: User-centric Transaction Management in Web-Database Systems"
OR
"UNIT: User-centric Transaction Management in Web-Database Systems"

ICDE 2007: Quality Contracts

"Preference-Aware Query and Update Scheduling in Web-Databases" -Huiming Qu, Alexandros Labrinidis

QC: Quality Contracts -> combines response time (QoS) and staleness (QoD)
QUTS (Query Update Time Sharing): adaptive algorithm to maximize the total profit from submitted QCs

QUTS make use of two level scheduling scheme that dynamically allocates CPU resources to updates and queries according to user preferences.

There are 3 policies:
1. FIFO: queue containing both updates and queries; are executed according to their arrival time
2. FIFI-UH: two queues -one for the updates and one for the queries. Updates have priority
3. FIFI-QH: two queues -one for the updates and one for the queries. Queries have priority

Average Staleness = # of unapplied updates

QUTS: is able to take the "best" profit dimension of the other policies: high QoS from QH and high QoD from UH using static QC design
QUTS: perform very close to ideal case when we vary qos_max and qod_max over time

Reference:
"Preference-Aware Query and Update Scheduling in Web-Databases"
or
"Preference-Aware Query and Update Scheduling in Web-Databases"