Count constraints and the inverse OLAP problem: Definition, complexity and a step toward aggregate data exchange

Domenico Saccà; Edoardo Serra; Antonella Guzzo

doi:10.1007/978-3-642-28472-4_20

Count constraints and the inverse OLAP problem: Definition, complexity and a step toward aggregate data exchange

Domenico Saccà, Edoardo Serra, Antonella Guzzo

Computer Science Department

University of Calabria

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

16 Scopus citations

Abstract

A typical problem in database theory is to verify whether there exists a relation (or database) instance satisfying a number of given dependency constraints. This problem has recently received a renewed deal of interest within the context of data exchange, but the issue of handling constraints on aggregate data has not been much investigated so far, notwithstanding the relevance of aggregate operations in exchange systems. This paper introduces count constraints that require the results of given count operations on a relation to be within a certain range. Count constraints are defined by a suitable extension of first order predicate calculus, based on set terms, and they are then used in a new decisional problem, the Inverse OLAP: given a star schema, does there exist a relation instance satisfying a set of given count constraints? The new problem turns out to be NEXP complete under various conditions: program complexity, data complexity and combined complexity. Count constraints can be also used into a data exchange system context, where data from the source database are transferred to the target database using aggregate operations.

Original language	English
Title of host publication	Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Proceedings
Pages	352-369
Number of pages	18
DOIs	https://doi.org/10.1007/978-3-642-28472-4_20
State	Published - 2012
Event	7th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2012 - Kiel, Germany Duration: 5 Mar 2012 → 9 Mar 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7153 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2012
Country/Territory	Germany
City	Kiel
Period	5/03/12 → 9/03/12

Keywords

Count Constraints
Data Exchange
Database Integrity Check
Inverse Data Mining
NEXP
OLAP
Star Schema

Access to Document

10.1007/978-3-642-28472-4_20

Cite this

Saccà, D., Serra, E., & Guzzo, A. (2012). Count constraints and the inverse OLAP problem: Definition, complexity and a step toward aggregate data exchange. In Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Proceedings (pp. 352-369). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7153 LNCS). https://doi.org/10.1007/978-3-642-28472-4_20

Saccà, Domenico ; Serra, Edoardo ; Guzzo, Antonella. / Count constraints and the inverse OLAP problem : Definition, complexity and a step toward aggregate data exchange. Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Proceedings. 2012. pp. 352-369 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6b0ed2d7b6814c61aaea5a0570d8ef0e,

title = "Count constraints and the inverse OLAP problem: Definition, complexity and a step toward aggregate data exchange",

abstract = "A typical problem in database theory is to verify whether there exists a relation (or database) instance satisfying a number of given dependency constraints. This problem has recently received a renewed deal of interest within the context of data exchange, but the issue of handling constraints on aggregate data has not been much investigated so far, notwithstanding the relevance of aggregate operations in exchange systems. This paper introduces count constraints that require the results of given count operations on a relation to be within a certain range. Count constraints are defined by a suitable extension of first order predicate calculus, based on set terms, and they are then used in a new decisional problem, the Inverse OLAP: given a star schema, does there exist a relation instance satisfying a set of given count constraints? The new problem turns out to be NEXP complete under various conditions: program complexity, data complexity and combined complexity. Count constraints can be also used into a data exchange system context, where data from the source database are transferred to the target database using aggregate operations.",

keywords = "Count Constraints, Data Exchange, Database Integrity Check, Inverse Data Mining, NEXP, OLAP, Star Schema",

author = "Domenico Sacc{\`a} and Edoardo Serra and Antonella Guzzo",

year = "2012",

doi = "10.1007/978-3-642-28472-4_20",

language = "English",

isbn = "9783642284717",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "352--369",

booktitle = "Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Proceedings",

note = "7th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2012 ; Conference date: 05-03-2012 Through 09-03-2012",

}

Saccà, D, Serra, E & Guzzo, A 2012, Count constraints and the inverse OLAP problem: Definition, complexity and a step toward aggregate data exchange. in Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7153 LNCS, pp. 352-369, 7th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2012, Kiel, Germany, 5/03/12. https://doi.org/10.1007/978-3-642-28472-4_20

Count constraints and the inverse OLAP problem: Definition, complexity and a step toward aggregate data exchange. / Saccà, Domenico; Serra, Edoardo; Guzzo, Antonella.
Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Proceedings. 2012. p. 352-369 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7153 LNCS).

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

TY - GEN

T1 - Count constraints and the inverse OLAP problem

T2 - 7th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2012

AU - Saccà, Domenico

AU - Serra, Edoardo

AU - Guzzo, Antonella

PY - 2012

Y1 - 2012

N2 - A typical problem in database theory is to verify whether there exists a relation (or database) instance satisfying a number of given dependency constraints. This problem has recently received a renewed deal of interest within the context of data exchange, but the issue of handling constraints on aggregate data has not been much investigated so far, notwithstanding the relevance of aggregate operations in exchange systems. This paper introduces count constraints that require the results of given count operations on a relation to be within a certain range. Count constraints are defined by a suitable extension of first order predicate calculus, based on set terms, and they are then used in a new decisional problem, the Inverse OLAP: given a star schema, does there exist a relation instance satisfying a set of given count constraints? The new problem turns out to be NEXP complete under various conditions: program complexity, data complexity and combined complexity. Count constraints can be also used into a data exchange system context, where data from the source database are transferred to the target database using aggregate operations.

AB - A typical problem in database theory is to verify whether there exists a relation (or database) instance satisfying a number of given dependency constraints. This problem has recently received a renewed deal of interest within the context of data exchange, but the issue of handling constraints on aggregate data has not been much investigated so far, notwithstanding the relevance of aggregate operations in exchange systems. This paper introduces count constraints that require the results of given count operations on a relation to be within a certain range. Count constraints are defined by a suitable extension of first order predicate calculus, based on set terms, and they are then used in a new decisional problem, the Inverse OLAP: given a star schema, does there exist a relation instance satisfying a set of given count constraints? The new problem turns out to be NEXP complete under various conditions: program complexity, data complexity and combined complexity. Count constraints can be also used into a data exchange system context, where data from the source database are transferred to the target database using aggregate operations.

KW - Count Constraints

KW - Data Exchange

KW - Database Integrity Check

KW - Inverse Data Mining

KW - NEXP

KW - OLAP

KW - Star Schema

UR - http://www.scopus.com/inward/record.url?scp=84858017008&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-28472-4_20

DO - 10.1007/978-3-642-28472-4_20

M3 - Conference contribution

AN - SCOPUS:84858017008

SN - 9783642284717

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 352

EP - 369

BT - Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Proceedings

Y2 - 5 March 2012 through 9 March 2012

ER -

Saccà D, Serra E, Guzzo A. Count constraints and the inverse OLAP problem: Definition, complexity and a step toward aggregate data exchange. In Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Proceedings. 2012. p. 352-369. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-28472-4_20

Count constraints and the inverse OLAP problem: Definition, complexity and a step toward aggregate data exchange

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this