Journal
PODS'15: PROCEEDINGS OF THE 33RD ACM SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS
Volume -, Issue -, Pages 173-184Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2745754.2745771
Keywords
Big data; query answering; complexity
Funding
- NSFC [61133002, 61421003]
- 973 Program [2012CB316200, 2014CB340302]
- Shenzhen Peacock Program [1105100030834361]
- Guangdong Innovative Research Team Program [2011D005]
- EPSRC [EP/J015377/1, EP/M025268/1]
- Google Faculty Research Award
- EPSRC [EP/M025268/1, EP/J015377/1] Funding Source: UKRI
Ask authors/readers for more resources
This paper investigates the feasibility of querying big data by accessing a bounded amount of the data. We study boundedly evaluable queries under a form of access constraints, when their evaluation cost is determined by the queries and constraints only. While it is undecidable to determine whether FO queries are boundedly evaluable, we show that for several classes of FO queries, the bounded evaluability problem is decidable. We also provide characterization and effective syntax for their boundedly evaluable queries. When a query Q is not boundedly evaluable, we study two approaches to approximately answering Q under access constraints. (1) We search for upper and lower envelopes of Q that are boundedly evaluable and warrant a constant accuracy bound. (2) We instantiate a minimum set of variables (parameters) in Q such that the specialized query is boundedly evaluable. We study problems for deciding the existence of envelopes and bounded specialized queries, and establish their complexity for various classes of FO queries.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available