Foundations of aggregation constraints

Kenneth A. Ross; Divesh Srivastava; Peter J. Stuckey; S. Sudarshan

Foundations of aggregation constraints

Kenneth A. Ross, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan

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

Abstract

We introduce a new constraint domain, aggregation constraints, which is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We study the fundamental problem of checking if a conjunction of aggregation constraints is solvable, and present undecidability results for many different classes of aggregation constraints. We describe a complete and minimal axiom~tization of the class of aggregation constraints over finite multisets of reals, which permits a natural reduction from the class of aggregation constraints to the class of mixed integer/real, non-linear arithmetic constraints. We then present a polynomial-time algorithm that directly checks for solvability of a useful class of aggregation constraints, where the reduction-based approach does not lead to efficient checks for solvability.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings
Editors	Alan Borning
Publisher	Springer
Pages	193-204
Number of pages	12
ISBN (Print)	9783540586012
Publication status	Published - 1 Jan 1994
Externally published	Yes
Event	International Workshop on the Principles and Practice of Constraint Programming 1994 - Rosario, Orcas Island, United States of America Duration: 2 May 1994 → 4 May 1994 Conference number: 2nd

Publication series

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

Conference

Conference	International Workshop on the Principles and Practice of Constraint Programming 1994
Abbreviated title	PPCP 1994
Country/Territory	United States of America
City	Rosario, Orcas Island
Period	2/05/94 → 4/05/94

Cite this

Ross, K. A., Srivastava, D., Stuckey, P. J., & Sudarshan, S. (1994). Foundations of aggregation constraints. In A. Borning (Ed.), Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings (pp. 193-204). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 874 LNCS). Springer.

Ross, Kenneth A. ; Srivastava, Divesh ; Stuckey, Peter J. et al. / Foundations of aggregation constraints. Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings. editor / Alan Borning. Springer, 1994. pp. 193-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b8bc95a8695244a68be08fc2bc3efc83,

title = "Foundations of aggregation constraints",

abstract = "We introduce a new constraint domain, aggregation constraints, which is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We study the fundamental problem of checking if a conjunction of aggregation constraints is solvable, and present undecidability results for many different classes of aggregation constraints. We describe a complete and minimal axiom~tization of the class of aggregation constraints over finite multisets of reals, which permits a natural reduction from the class of aggregation constraints to the class of mixed integer/real, non-linear arithmetic constraints. We then present a polynomial-time algorithm that directly checks for solvability of a useful class of aggregation constraints, where the reduction-based approach does not lead to efficient checks for solvability.",

author = "Ross, {Kenneth A.} and Divesh Srivastava and Stuckey, {Peter J.} and S. Sudarshan",

year = "1994",

month = jan,

day = "1",

language = "English",

isbn = "9783540586012",

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

publisher = "Springer",

pages = "193--204",

editor = "Alan Borning",

booktitle = "Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings",

note = "International Workshop on the Principles and Practice of Constraint Programming 1994, PPCP 1994 ; Conference date: 02-05-1994 Through 04-05-1994",

}

Ross, KA, Srivastava, D, Stuckey, PJ & Sudarshan, S 1994, Foundations of aggregation constraints. in A Borning (ed.), Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 874 LNCS, Springer, pp. 193-204, International Workshop on the Principles and Practice of Constraint Programming 1994, Rosario, Orcas Island, Washington, United States of America, 2/05/94.

Foundations of aggregation constraints. / Ross, Kenneth A.; Srivastava, Divesh; Stuckey, Peter J. et al.
Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings. ed. / Alan Borning. Springer, 1994. p. 193-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 874 LNCS).

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

TY - GEN

T1 - Foundations of aggregation constraints

AU - Ross, Kenneth A.

AU - Srivastava, Divesh

AU - Stuckey, Peter J.

AU - Sudarshan, S.

N1 - Conference code: 2nd

PY - 1994/1/1

Y1 - 1994/1/1

N2 - We introduce a new constraint domain, aggregation constraints, which is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We study the fundamental problem of checking if a conjunction of aggregation constraints is solvable, and present undecidability results for many different classes of aggregation constraints. We describe a complete and minimal axiom~tization of the class of aggregation constraints over finite multisets of reals, which permits a natural reduction from the class of aggregation constraints to the class of mixed integer/real, non-linear arithmetic constraints. We then present a polynomial-time algorithm that directly checks for solvability of a useful class of aggregation constraints, where the reduction-based approach does not lead to efficient checks for solvability.

AB - We introduce a new constraint domain, aggregation constraints, which is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We study the fundamental problem of checking if a conjunction of aggregation constraints is solvable, and present undecidability results for many different classes of aggregation constraints. We describe a complete and minimal axiom~tization of the class of aggregation constraints over finite multisets of reals, which permits a natural reduction from the class of aggregation constraints to the class of mixed integer/real, non-linear arithmetic constraints. We then present a polynomial-time algorithm that directly checks for solvability of a useful class of aggregation constraints, where the reduction-based approach does not lead to efficient checks for solvability.

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

M3 - Conference Paper

AN - SCOPUS:35048883202

SN - 9783540586012

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

SP - 193

EP - 204

BT - Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings

A2 - Borning, Alan

PB - Springer

T2 - International Workshop on the Principles and Practice of Constraint Programming 1994

Y2 - 2 May 1994 through 4 May 1994

ER -

Ross KA, Srivastava D, Stuckey PJ, Sudarshan S. Foundations of aggregation constraints. In Borning A, editor, Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings. Springer. 1994. p. 193-204. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Foundations of aggregation constraints

Abstract

Publication series

Conference

Other files and links

Cite this