ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Information Synthesis in Statistical Databases.

Wee Keong Ng, Chinya V. Ravishankar: Information Synthesis in Statistical Databases. CIKM 1995: 355-361
@inproceedings{DBLP:conf/cikm/NgR95,
  author    = {Wee Keong Ng and
               Chinya V. Ravishankar},
  title     = {Information Synthesis in Statistical Databases},
  booktitle = {CIKM '95, Proceedings of the 1995 International Conference on
               Information and Knowledge Management, November 28 - December
               2, 1995, Baltimore, Maryland, USA},
  publisher = {ACM},
  year      = {1995},
  pages     = {355-361},
  ee        = {db/conf/cikm/NgR95.html, http://doi.acm.org/10.1145/221270.221638},
  crossref  = {DBLP:conf/cikm/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Given a statistical database containing a set of summary tables, this paper examines the complexity of retrieving data from the database in order to satisfy a query. In particular, we consider the case when the query cannot be directly satisfied via a single summary table and requires two or more summary tables. We show that a system of linear equations can be constructed from a set of summary tables whose solution(s) satisfy a query in oarying degrees. We derive a formula for determining the degree of acceptability of the solution as a function of the characteristics of the summary tables which derive the algebraic system. We also show that selecting the optimal set of summary tables from the database that yields the best solution to the query is NP-complete. These findings offer important insights into the retrievability of information from a statistical database when designing a statistical query processor.

Copyright © 1995 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

CIKM '95, Proceedings of the 1995 International Conference on Information and Knowledge Management, November 28 - December 2, 1995, Baltimore, Maryland, USA. ACM 1995
Contents BibTeX

Online Edition

Citation Page BibTeX

References

[1]
Meng Chang Chen, Lawrence McNamee: On the Data Model and Access Method of Summary Data Management. IEEE Trans. Knowl. Data Eng. 1(4): 519-529(1989) BibTeX
[2]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
BibTeX
[3]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[4]
Sakti P. Ghosh: Statistical Relational Tables for Statistical Database Management. IEEE Trans. Software Eng. 12(12): 1106-1116(1986) BibTeX
[5]
...
[6]
Georges Hébrail: A Model of Summaries for Very Large Databases. SSDBM 1986: 143-151 BibTeX
[7]
Francesco M. Malvestuto: The Derivation Problem for Summary Data. SIGMOD Conference 1988: 82-89 BibTeX
[8]
Francesco M. Malvestuto: A Universal-Scheme Approach to Statistical Databases Containing Homogeneous Summary Tables. ACM Trans. Database Syst. 18(4): 678-708(1993) BibTeX
[9]
Francesco M. Malvestuto, Marina Moscarini: Query Evaluability in Statistical Databases. IEEE Trans. Knowl. Data Eng. 2(4): 425-430(1990) BibTeX
[10]
Zbigniew Michalewicz (Ed.): Statistical and Scientific Database Management, 5th International Conference SSDBM, Charlotte, NC, USA, April 3-5, 1990, Proccedings. Lecture Notes in Computer Science 420 Springer 1990, ISBN 3-540-52342-1
Contents BibTeX
[11]
Wee Keong Ng, Chinya V. Ravishankar: A Physical Storage for Efficient Statistical Query Processing. SSDBM 1994: 97-106 BibTeX
[12]
Wee Keong Ng, Chinya V. Ravishankar: A Tuple Model for Summary Data Management . COMAD 1994: 0- BibTeX
[13]
...
[14]
Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Francisco Mata: A Language and a Physical Organization Technique for Summary Tables. SIGMOD Conference 1985: 3-16 BibTeX
[15]
H. Sato: Handling Summary Information in a Database: Derivability. SIGMOD Conference 1981: 98-107 BibTeX
[16]
...
[17]
Arie Shoshani: Statistical Databases: Characteristics, Problems, and some Solutions. VLDB 1982: 208-222 BibTeX

Referenced by

  1. Christos Faloutsos, H. V. Jagadish, Nikolaos Sidiropoulos: Recovering Information from Summary Data. VLDB 1997: 36-45
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
CIKM 1995 Proceedings, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:01:51 2009