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
N1 - Funding Information:
Acknowledgements. We thank Viktor Kuncak for his comments on this work. Manos Koukoutos is supported in part by the European Research Council (ERC) project Implicit Programming. This material is based upon work partially supported by the US National Science Foundation under Grant Nos. CCF-1409423, CCF-1421503, CNS-1646305, CCF-1718903, and CNS-1740916.
Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
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
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 -