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.
If you cannot see the document below, the PDF document is most likely not freely accessible. In this case, please try to access the document via this link.
% BibTex
@inproceedings{WangSKMK18,
author = {Kaiyuan Wang and
Allison Sullivan and
Manos Koukoutos and
Darko Marinov and
Sarfraz Khurshid},
editor = {Michael J. Butler and
Alexander Raschke and
Thai Son Hoang and
Klaus Reichl},
title = {Systematic Generation of Non-equivalent Expressions for Relational
Algebra},
booktitle = {Abstract State Machines, Alloy, B, TLA, VDM, and {Z} - 6th International
Conference, {ABZ} 2018, Southampton, UK, June 5-8, 2018, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {10817},
pages = {105--120},
publisher = {Springer},
year = {2018},
url = {https://doi.org/10.1007/978-3-319-91271-4\_8},
doi = {10.1007/978-3-319-91271-4\_8},
timestamp = {Thu, 14 Oct 2021 10:31:49 +0200},
biburl = {https://dblp.org/rec/conf/asm/WangSKMK18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}