An introduction to data representation synthesis
We consider the problem of specifying combinations of data structures with complex sharing in a manner that is declarative and results in provably correct code. In our approach, abstract data types are specified using relational algebra and functional dependencies. We describe a language of decompos...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/124647 |
| _version_ | 1826211576922767360 |
|---|---|
| author | Hawkins, Peter Rinard, Martin C Aiken, Alex Sagiv, Mooly Fisher, Kathleen |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Hawkins, Peter Rinard, Martin C Aiken, Alex Sagiv, Mooly Fisher, Kathleen |
| author_sort | Hawkins, Peter |
| collection | MIT |
| description | We consider the problem of specifying combinations of data structures with complex sharing in a manner that is declarative and results in provably correct code. In our approach, abstract data types are specified using relational algebra and functional dependencies. We describe a language of decompositions that permits the user to specify different concrete representations for relations, and show that operations on concrete representations soundly implement their relational specification. We also describe an auto-tuner that automatically identifies the best decomposition for a particular workload. It is easy to incorporate data representations synthesized by our compiler into existing systems, leading to code that is simpler, correct by construction, and comparable in performance to the code it replaces. Keywords: Information systems; Information storage systems; Record storage systems; Record storage alternatives |
| first_indexed | 2024-09-23T15:08:11Z |
| format | Article |
| id | mit-1721.1/124647 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:08:11Z |
| publishDate | 2020 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1246472022-10-02T00:49:39Z An introduction to data representation synthesis Hawkins, Peter Rinard, Martin C Aiken, Alex Sagiv, Mooly Fisher, Kathleen Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory General Computer Science We consider the problem of specifying combinations of data structures with complex sharing in a manner that is declarative and results in provably correct code. In our approach, abstract data types are specified using relational algebra and functional dependencies. We describe a language of decompositions that permits the user to specify different concrete representations for relations, and show that operations on concrete representations soundly implement their relational specification. We also describe an auto-tuner that automatically identifies the best decomposition for a particular workload. It is easy to incorporate data representations synthesized by our compiler into existing systems, leading to code that is simpler, correct by construction, and comparable in performance to the code it replaces. Keywords: Information systems; Information storage systems; Record storage systems; Record storage alternatives National Science Foundation (CCF-0702681) National Science Foundation (CNS-050955) 2020-04-15T12:32:13Z 2020-04-15T12:32:13Z 2012-12 2019-07-02T15:46:38Z Article http://purl.org/eprint/type/JournalArticle 0001-0782 1557-7317 https://hdl.handle.net/1721.1/124647 Hawkins, Peter et al. "An introduction to data representation synthesis." Communications of the ACM 55, 12 (December 2012): 91-99. © 2012 ACM en http://dx.doi.org/10.1145/2380656.2380677 Communications of the ACM Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) other univ website |
| spellingShingle | General Computer Science Hawkins, Peter Rinard, Martin C Aiken, Alex Sagiv, Mooly Fisher, Kathleen An introduction to data representation synthesis |
| title | An introduction to data representation synthesis |
| title_full | An introduction to data representation synthesis |
| title_fullStr | An introduction to data representation synthesis |
| title_full_unstemmed | An introduction to data representation synthesis |
| title_short | An introduction to data representation synthesis |
| title_sort | introduction to data representation synthesis |
| topic | General Computer Science |
| url | https://hdl.handle.net/1721.1/124647 |
| work_keys_str_mv | AT hawkinspeter anintroductiontodatarepresentationsynthesis AT rinardmartinc anintroductiontodatarepresentationsynthesis AT aikenalex anintroductiontodatarepresentationsynthesis AT sagivmooly anintroductiontodatarepresentationsynthesis AT fisherkathleen anintroductiontodatarepresentationsynthesis AT hawkinspeter introductiontodatarepresentationsynthesis AT rinardmartinc introductiontodatarepresentationsynthesis AT aikenalex introductiontodatarepresentationsynthesis AT sagivmooly introductiontodatarepresentationsynthesis AT fisherkathleen introductiontodatarepresentationsynthesis |