More Web Proxy on the site http://driver.im/

research-article

APPROXIMATE: A Query Processor that Produces Monotonically Improving Approximate Answers

Authors:

J. W. S. LiuAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 5, Issue 6

Pages 1056 - 1068

https://doi.org/10.1109/69.250091

Published: 01 December 1993 Publication History

Abstract

APPROXIMATE, a query processor that makes approximate answers available if part of the database is unavailable, or if there is not enough time to produce an exact answer, is described. The processor implements approximate query processing, and the accuracy of the approximate result produced improves monotonically with the amount of data retrieved to produce the result. The monotone query processing algorithm of APPROXIMATE works within a standard relational algebra framework. APPROXIMATE maintains semantic information for approximate query processing at an underlying level, and can be implemented on a relational database system with little change to the relational architecture. It is shown how APPROXIMATE is implemented to make effective use of the semantic support. The additional overhead required by APPROXIMATE is described.

References

[1]

{1} K. J. Lin, S. Natarajan, J. W. S. Liu, and T. Krauskopf, "Concord: A system of imprecise computations," in Proc. COMPSAC '87, Tokyo, Japan, Oct. 1987, pp. 75-81.

[2]

{2} J. W. S. Liu, K. J. Lin, and S. Natarajan, "Scheduling Real-Time Periodic Jobs using Imprecise Results," in Proc. IEEE Real-Time Syst. Symp., San Jose, CA, Dec. 1987.

[3]

{3} J. Y. Chung, J. W. S. Liu, and K. J. Lin, "Scheduling periodic jobs that allow imprecise results," IEEE Trans. Comput., vol. 39, pp. 1156-1174, Sept. 1990.

Digital Library

[4]

{4} K. P. Smith and J. W. S. Liu, "Monotonically improving approximate answers to relational algebra queries," in Proc. COMPSAC '89, Orlando, FL, Sept. 1989.

[5]

{5} S. B. Davidson and A. Watters, "Partial computation in real-time database systems," in Proc. 5th Workshop Real-Time Software, Operat. Syst., May 1988, pp. 117-121.

[6]

{6} G. Ozsoyoglu, Z. M. Ozsoyoglu, and W.-C. Hou, "Research in time-and error-constrained database query processing," in Proc. Workshop Real-Time Operat. Syst., Software, Charlottesville, VA, May 1990.

[7]

{7} A. Motro, "VAGUE: A user interface to relational databases that permits vague queries," ACM Trans. Office Inform. Syst., vol. 6, no. 3, pp. 187-214, July 1988.

Digital Library

[8]

{8} A. Motro, "Using integrity constraints to provide intensional answers to relational queries," in Proc. 15th Conf. Very Large Data Bases, 1989.

[9]

{9} J. Ullman, Principles of Database and Knowledge Based Systems, vol. 1. Rockville, MD: Comput. Sci. Press, 1988, pp. 121-122.

[10]

{10} K. Liu and R. Sunderraman, "On representing indefinite and maybe information in relational databases," in Proc. 4th Int. Conf. Data Eng., Feb. 1988, pp. 250-257.

[11]

{11} R. Hull and R. King, "Semantic database modeling: Survey, applications, and research issues," ACM Comput. Surveys, vol. 19, no. 3, pp. 201-260, Sept. 1987.

Digital Library

[12]

{12} W. Kim, N. Ballou, H.-T. Chou, J. F. Garza, and D. Woelk, "Integrating an object-oriented programming system with a database system," OOPSLA Proc., pp. 142-152, Sept. 1988.

[13]

{13} A. Goldberg and D. Robson, Smalltalk-80: The Language and Its Implementation. Reading, MA: Addison-Wesley, 1983.

Digital Library

[14]

{14} J. Peckham and F. Maryanski, "Semantic data models," ACM Comput. Surveys, vol. 20, no. 3, pp. 153-189, Sept. 1988.

Digital Library

[15]

{15} H. H. Pang, H. J. Lu, and B. C. Ooi, "An efficient semantic query optimization algorithm," in Proc. 7th Int. Conf. Data Eng., Japan, Apr. 1991, pp. 326-335.

[16]

{16} S. Vrbsky and J. W. S. Liu, "Producing Approximate Answers to Set-Valued and Single-Valued Queries," in Proc. 1st Int. Conf. Informat. Knowledge Management, Nov. 1992, pp. 405-412.

Cited By

Sanati BCheng A(2016)LBBAFuture Generation Computer Systems10.1016/j.future.2015.10.02459:C(125-135)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.future.2015.10.024
Trummer IKoch CSellis TDavidson SIves Z(2015)An Incremental Anytime Algorithm for Multi-Objective Query OptimizationProceedings of the 2015 ACM SIGMOD International Conference on Management of Data10.1145/2723372.2746484(1941-1953)Online publication date: 27-May-2015
https://dl.acm.org/doi/10.1145/2723372.2746484
Lang WNehme RRobinson ENaughton JDyreson CLi FÖzsu M(2014)Partial results in database systemsProceedings of the 2014 ACM SIGMOD International Conference on Management of Data10.1145/2588555.2612176(1275-1286)Online publication date: 18-Jun-2014
https://dl.acm.org/doi/10.1145/2588555.2612176
Show More Cited By

APPROXIMATE: A Query Processor that Produces Monotonically Improving Approximate Answers
1. Information systems
  1. Data management systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Approximate Query Processing with Error Guarantees
Big-Data-Analytics in Astronomy, Science, and Engineering
Abstract
In recent years, with the increase of data and the sophistication of analysis requirements, query processing in databases has become more important. Recently, approximate query processing (AQP) was proposed for efficiently executing database ...
A Structured Approach for Cooperative Query Answering

This paper proposes the use of a type abstraction hierarchy as a framework for deriving cooperative query answers. The type abstraction hierarchy integrates the abstraction view with the subsumption (is-a) and composition (part-of) views of a type ...
Outer Joins and Filters for Instantiating Objects from Relational Databases Through Views

One of the approaches for integrating object-oriented programs with databases is to instantiate objects from relational databases by evaluating view queries. In that approach, it is often necessary to evaluate some joins of the query by left outer joins ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 5, Issue 6

December 1993

185 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © Copyright © 1993 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 December 1993

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sanati BCheng A(2016)LBBAFuture Generation Computer Systems10.1016/j.future.2015.10.02459:C(125-135)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.future.2015.10.024
Trummer IKoch CSellis TDavidson SIves Z(2015)An Incremental Anytime Algorithm for Multi-Objective Query OptimizationProceedings of the 2015 ACM SIGMOD International Conference on Management of Data10.1145/2723372.2746484(1941-1953)Online publication date: 27-May-2015
https://dl.acm.org/doi/10.1145/2723372.2746484
Lang WNehme RRobinson ENaughton JDyreson CLi FÖzsu M(2014)Partial results in database systemsProceedings of the 2014 ACM SIGMOD International Conference on Management of Data10.1145/2588555.2612176(1275-1286)Online publication date: 18-Jun-2014
https://dl.acm.org/doi/10.1145/2588555.2612176
Valsomatzis EGounaris AShin SMaldonado J(2013)Driver input selection for main-memory multi-way joinsProceedings of the 28th Annual ACM Symposium on Applied Computing10.1145/2480362.2480521(818-825)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2480362.2480521
Ilyas IBeskales GSoliman M(2008)A survey of top-k query processing techniques in relational database systemsACM Computing Surveys10.1145/1391729.139173040:4(1-58)Online publication date: 15-Oct-2008
https://dl.acm.org/doi/10.1145/1391729.1391730
Kwon OShin M(2008)LACOExpert Systems with Applications: An International Journal10.1016/j.eswa.2007.05.02234:4(2966-2975)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.eswa.2007.05.022
Amirijoo MHansson JGunnarsson SSon S(2008)Quantifying and suppressing the measurement disturbance in feedback controlled real-time systemsReal-Time Systems10.1007/s11241-008-9048-340:1(44-76)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1007/s11241-008-9048-3
Orman L(2008)Browsing databases with constraint hierarchiesElectronic Commerce Research10.1007/s10660-008-9016-y8:1-2(29-56)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1007/s10660-008-9016-y
Amirijoo MHansson JSon SGunnarsson S(2007)Experimental evaluation of linear time-invariant models for feedback performance control in real-time systemsReal-Time Systems10.1007/s11241-006-9008-835:3(209-238)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1007/s11241-006-9008-8
Amirijoo MHansson JSon S(2006)Specification and Management of QoS in Real-Time Databases Supporting Imprecise ComputationsIEEE Transactions on Computers10.1109/TC.2006.4555:3(304-319)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1109/TC.2006.45
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents