FlashRelate: Extracting Relational Data from Semi-Structured Spreadsheets Using Examples - Barowy, Daniel W.; Gulwani, Sumit; Hart, Ted; Zorn, Ben (PLDI '15 Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2014)
Spreadsheets store a tremendous amount of important data. One reason spreadsheets are so successful is that they are both easy to use and allow users great expressiveness in storing and manipulating their data. This flexibility comes at a price, as presentation elements are often combined with the underlying data model. As a result, many spreadsheets contain data in ad-hoc formats. These formats complicate the use of traditional relational tools which require data in a normalized form. Normalizing data from these formats is often tedious or requires programming, and often, a user may prefer the original presentation. We describe an approach that allows users to easily extract structured data from spreadsheets without programming. We make two contributions. First, we describe a novel domain specific language called Flare that extends traditional regular expressions with spatial constraints. Second, we describe an algorithm called FlashRelate that can synthesize Flare programs from user-provided positive and negative examples. Using 43 benchmarks drawn both from a standard spreadsheet corpus and from Excel-user help forums, we demonstrate that correct extraction programs can be synthesized quickly from a small number of examples. Our approach generalizes to many data-cleaning tasks on semi-structured spreadsheets. View the FlashRelate Video Demo
Distinguished Artifact Award