Systematic generation of non-equivalent expressions for relational algebra

Kaiyuan Wang; Allison Sullivan; Manos Koukoutos; Darko Marinov; Sarfraz Khurshid

doi:10.1007/978-3-319-91271-4_8

Systematic generation of non-equivalent expressions for relational algebra

Kaiyuan Wang, Allison Sullivan, Manos Koukoutos, Darko Marinov, Sarfraz Khurshid

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

Abstract

Relational algebra forms the semantic foundation in multiple domains, e.g., Alloy models, OCL constraints, UML metamodels, and SQL queries. Synthesis and repair techniques in such domains require an efficient procedure to generate (non-equivalent) expressions subject to relational constraints, e.g., the types of sets and relations, their cardinality, size of expressions, maximum arity of the intermediate expressions, etc. This paper introduces the first generator for relational expressions that are non-equivalent with respect to the semantics of relational algebra. We present the algorithms that define our generator, its embodiment based on the Alloy tool-set, and an experimental evaluation to show the effectiveness of its non-equivalent generation for a variety of problems with relational constraints.

Original language	English (US)
Title of host publication	Abstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings
Editors	Michael Butler, Thai Son Hoang, Alexander Raschke, Klaus Reichl
Publisher	Springer-Verlag Berlin Heidelberg
Pages	105-120
Number of pages	16
ISBN (Print)	9783319912707
DOIs	https://doi.org/10.1007/978-3-319-91271-4_8
State	Published - Jan 1 2018
Event	6th International Conference on ABZ Conference on ASM, Alloy, B, TLA, VDM, and Z, ABZ 2018 - Southampton, United Kingdom Duration: Jun 5 2018 → Jun 8 2018

Publication series

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

Other

Other	6th International Conference on ABZ Conference on ASM, Alloy, B, TLA, VDM, and Z, ABZ 2018
Country	United Kingdom
City	Southampton
Period	6/5/18 → 6/8/18

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-91271-4_8

Fingerprint Dive into the research topics of 'Systematic generation of non-equivalent expressions for relational algebra'. Together they form a unique fingerprint.

Cite this

Wang, K., Sullivan, A., Koukoutos, M., Marinov, D., & Khurshid, S. (2018). Systematic generation of non-equivalent expressions for relational algebra. In M. Butler, T. S. Hoang, A. Raschke, & K. Reichl (Eds.), Abstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings (pp. 105-120). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10817 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-319-91271-4_8

Systematic generation of non-equivalent expressions for relational algebra. / Wang, Kaiyuan; Sullivan, Allison; Koukoutos, Manos; Marinov, Darko; Khurshid, Sarfraz.

Abstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings. ed. / Michael Butler; Thai Son Hoang; Alexander Raschke; Klaus Reichl. Springer-Verlag Berlin Heidelberg, 2018. p. 105-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10817 LNCS).

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

Wang, K, Sullivan, A, Koukoutos, M, Marinov, D & Khurshid, S 2018, Systematic generation of non-equivalent expressions for relational algebra. in M Butler, TS Hoang, A Raschke & K Reichl (eds), Abstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10817 LNCS, Springer-Verlag Berlin Heidelberg, pp. 105-120, 6th International Conference on ABZ Conference on ASM, Alloy, B, TLA, VDM, and Z, ABZ 2018, Southampton, United Kingdom, 6/5/18. https://doi.org/10.1007/978-3-319-91271-4_8

Wang K, Sullivan A, Koukoutos M, Marinov D, Khurshid S. Systematic generation of non-equivalent expressions for relational algebra. In Butler M, Hoang TS, Raschke A, Reichl K, editors, Abstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings. Springer-Verlag Berlin Heidelberg. 2018. p. 105-120. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-91271-4_8

Wang, Kaiyuan ; Sullivan, Allison ; Koukoutos, Manos ; Marinov, Darko ; Khurshid, Sarfraz. / Systematic generation of non-equivalent expressions for relational algebra. Abstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings. editor / Michael Butler ; Thai Son Hoang ; Alexander Raschke ; Klaus Reichl. Springer-Verlag Berlin Heidelberg, 2018. pp. 105-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ba086b705d5c43efa805ebdaab7e284b,

title = "Systematic generation of non-equivalent expressions for relational algebra",

abstract = "Relational algebra forms the semantic foundation in multiple domains, e.g., Alloy models, OCL constraints, UML metamodels, and SQL queries. Synthesis and repair techniques in such domains require an efficient procedure to generate (non-equivalent) expressions subject to relational constraints, e.g., the types of sets and relations, their cardinality, size of expressions, maximum arity of the intermediate expressions, etc. This paper introduces the first generator for relational expressions that are non-equivalent with respect to the semantics of relational algebra. We present the algorithms that define our generator, its embodiment based on the Alloy tool-set, and an experimental evaluation to show the effectiveness of its non-equivalent generation for a variety of problems with relational constraints.",

author = "Kaiyuan Wang and Allison Sullivan and Manos Koukoutos and Darko Marinov and Sarfraz Khurshid",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-91271-4_8",

language = "English (US)",

isbn = "9783319912707",

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

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "105--120",

editor = "Michael Butler and Hoang, {Thai Son} and Alexander Raschke and Klaus Reichl",

booktitle = "Abstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings",

note = "6th International Conference on ABZ Conference on ASM, Alloy, B, TLA, VDM, and Z, ABZ 2018 ; Conference date: 05-06-2018 Through 08-06-2018",

}

TY - GEN

T1 - Systematic generation of non-equivalent expressions for relational algebra

AU - Wang, Kaiyuan

AU - Sullivan, Allison

AU - Koukoutos, Manos

AU - Marinov, Darko

AU - Khurshid, Sarfraz

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Relational algebra forms the semantic foundation in multiple domains, e.g., Alloy models, OCL constraints, UML metamodels, and SQL queries. Synthesis and repair techniques in such domains require an efficient procedure to generate (non-equivalent) expressions subject to relational constraints, e.g., the types of sets and relations, their cardinality, size of expressions, maximum arity of the intermediate expressions, etc. This paper introduces the first generator for relational expressions that are non-equivalent with respect to the semantics of relational algebra. We present the algorithms that define our generator, its embodiment based on the Alloy tool-set, and an experimental evaluation to show the effectiveness of its non-equivalent generation for a variety of problems with relational constraints.

AB - Relational algebra forms the semantic foundation in multiple domains, e.g., Alloy models, OCL constraints, UML metamodels, and SQL queries. Synthesis and repair techniques in such domains require an efficient procedure to generate (non-equivalent) expressions subject to relational constraints, e.g., the types of sets and relations, their cardinality, size of expressions, maximum arity of the intermediate expressions, etc. This paper introduces the first generator for relational expressions that are non-equivalent with respect to the semantics of relational algebra. We present the algorithms that define our generator, its embodiment based on the Alloy tool-set, and an experimental evaluation to show the effectiveness of its non-equivalent generation for a variety of problems with relational constraints.

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

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

U2 - 10.1007/978-3-319-91271-4_8

DO - 10.1007/978-3-319-91271-4_8

M3 - Conference contribution

AN - SCOPUS:85047413867

SN - 9783319912707

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

SP - 105

EP - 120

BT - Abstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings

A2 - Butler, Michael

A2 - Hoang, Thai Son

A2 - Raschke, Alexander

A2 - Reichl, Klaus

PB - Springer-Verlag Berlin Heidelberg

T2 - 6th International Conference on ABZ Conference on ASM, Alloy, B, TLA, VDM, and Z, ABZ 2018

Y2 - 5 June 2018 through 8 June 2018

ER -