- Incorporate the information quality aspect into query planning
- Quality criteria: source-specific, query-specific and attribute-specific
- IQ (Information Quality): is the aggregation of the scores used to rank the sources and plans
- Three phase approach to quality-driven information integration
Thursday, February 11, 2010
VLDB99QDrivenIntegration -Naumann
"Quality-driven Integration of Heterogenous Information Systems", Felix Naumann, Ulf Leser, Johann Christoph Freytag
Friday, February 5, 2010
Journal of MIS1996BeyondAccuracy-Wang-Strong
"Beyond Accuracy: What Data Quality Means to Data Consumers" - Richard Y. Wang, Diane M. Strong ( MIT )
- Approaches to study data quality: intuitive, theoretical, empirical
- Attributes of the quality of data: accuracy, timeliness, precision, reliability, currency, completeness, relevancy, accessibility, interpretability
- Overall the most important attributes: accuracy and correctness
Thursday, August 27, 2009
Monday, July 20, 2009
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
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
Thursday, July 16, 2009
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
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
Subscribe to:
Posts (Atom)