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"