Querying Big Data by Accessing Small Data

Wenfei Fan; Floris Geerts; Yang Cao; Ting Deng; Ping Lu

doi:10.1145/2745754.2745771

Querying Big Data by Accessing Small Data

Wenfei Fan, Floris Geerts, Yang Cao, Ting Deng, Ping Lu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

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.

Original language	English
Title of host publication	Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Place of Publication	New York, NY, USA
Publisher	ACM
Pages	173-184
Number of pages	12
ISBN (Print)	978-1-4503-2757-2
DOIs	https://doi.org/10.1145/2745754.2745771
Publication status	Published - 20 May 2015
Event	34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - Melbourne, Australia Duration: 31 May 2015 → 4 Jun 2015 http://www.sigmod2015.org/

Conference

Conference	34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Abbreviated title	PODS 2015
Country/Territory	Australia
City	Melbourne
Period	31/05/15 → 4/06/15
Internet address	http://www.sigmod2015.org/

Keywords / Materials (for Non-textual outputs)

big data
complexity
query answering

Access to Document

10.1145/2745754.2745771Licence: All Rights Reserved

pods15Accepted author manuscript, 242 KB

http://doi.acm.org/10.1145/2745754.2745771Licence: All Rights Reserved

VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
EPSRC
1/04/15 → 30/09/20
Project: Research
Querying Graph Structured Data: Principles and Techniques
Libkin, L. & Fan, W.
EPSRC
1/11/13 → 31/10/16
Project: Research

Yang Cao
- School of Informatics - Lecturer in Database Systems
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active

Cite this

@inproceedings{9c0f575390824e4f9af32ce5f3ce47e5,

title = "Querying Big Data by Accessing Small Data",

abstract = "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.",

keywords = "big data, complexity, query answering",

author = "Wenfei Fan and Floris Geerts and Yang Cao and Ting Deng and Ping Lu",

year = "2015",

month = may,

day = "20",

doi = "10.1145/2745754.2745771",

language = "English",

isbn = "978-1-4503-2757-2",

pages = "173--184",

booktitle = "Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems",

publisher = "ACM",

note = "34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2015 ; Conference date: 31-05-2015 Through 04-06-2015",

url = "http://www.sigmod2015.org/",

}

Fan, W, Geerts, F, Cao, Y, Deng, T & Lu, P 2015, Querying Big Data by Accessing Small Data. in Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, New York, NY, USA, pp. 173-184, 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Melbourne, Victoria, Australia, 31/05/15. https://doi.org/10.1145/2745754.2745771

TY - GEN

T1 - Querying Big Data by Accessing Small Data

AU - Fan, Wenfei

AU - Geerts, Floris

AU - Cao, Yang

AU - Deng, Ting

AU - Lu, Ping

PY - 2015/5/20

Y1 - 2015/5/20

N2 - 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.

AB - 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.

KW - big data

KW - complexity

KW - query answering

U2 - 10.1145/2745754.2745771

DO - 10.1145/2745754.2745771

M3 - Conference contribution

SN - 978-1-4503-2757-2

SP - 173

EP - 184

BT - Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

PB - ACM

CY - New York, NY, USA

T2 - 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Y2 - 31 May 2015 through 4 June 2015

ER -

Querying Big Data by Accessing Small Data

Abstract / Description of output

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

VADA: Value Added Data Systems: Principles and Architecture

Querying Graph Structured Data: Principles and Techniques

Profiles

Yang Cao

Cite this