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 proceedingConference 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 languageEnglish (US)
Title of host publicationAbstract State Machines, Alloy, B, TLA, VDM, and Z - 6th International Conference, ABZ 2018, Proceedings
EditorsMichael Butler, Thai Son Hoang, Alexander Raschke, Klaus Reichl
PublisherSpringer-Verlag Berlin Heidelberg
Pages105-120
Number of pages16
ISBN (Print)9783319912707
DOIs
StatePublished - Jan 1 2018
Event6th International Conference on ABZ Conference on ASM, Alloy, B, TLA, VDM, and Z, ABZ 2018 - Southampton, United Kingdom
Duration: Jun 5 2018Jun 8 2018

Publication series

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

Other

Other6th International Conference on ABZ Conference on ASM, Alloy, B, TLA, VDM, and Z, ABZ 2018
CountryUnited Kingdom
CitySouthampton
Period6/5/186/8/18

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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