Logical spreadsheet

A logical spreadsheet is a spreadsheet in which formulas take the form of logical constraints rather than function definitions.

In traditional spreadsheet systems, such as Excel, cells are partitioned into "directly specified" cells and "computed" cells and the formulas used to specify the values of computed cells are "functional", i.e. for every combination of values of the directly specified cells, the formulas specify unique values for the computed cells. Logical Spreadsheets relax these restrictions by dispensing with the distinction between directly specified cells and computed cells and generalizing from functional definitions to logical constraints.

As an illustration of the difference between traditional spreadsheets and logical spreadsheets, consider a simple numerical spreadsheet with three cells a, b, and c. Each cell accepts a single integer as value; and there is a formula stating that the value of the third cell is the sum of the values of the other two cells.

Implemented as a traditional spreadsheet, this spreadsheet would allow the user to enter values into cells a and b, and it would automatically compute cell c. For example, if the user were to type 1 into a and 2 into b, it would compute the value 3 for c.

Implemented as a logical spreadsheet, the user would be able to enter values into any of the cells. The user could type 1 into a and 2 into b, and the spreadsheet would compute the value 3 for c. Alternatively, the user could type 2 into b and 3 into c, and the spreadsheet would compute the value 1 for a. And so forth.

In this case, the formula is functional, and the function is invertible. In general, the formulas need not be functional and the functions need not be invertible. For example, in this case, we could write formulas involving inequalities and non-invertible functions (such as square root). More generally, we could build spreadsheets with symbolic, rather than numeric data, and write arbitrary logical constraints on this data.

References

* J. Bongard et al.: Reports on the 2006 AAAI Fall Symposia, AI Magazine 28(1), 88-92, 2007.
* I. Cervesato: NEXCEL, A Deductive Spreadsheet, The Knowledge Engineering Review, Vol. 00:0, 1-24, Cambridge University Press, 2004.
* G. Fischer, C. Rathke: Knowledge-Based Spreadsheets, in Proceedings of the 7th National Conference on Artificial Intelligence, St. Paul Minnesota, 21-26 August 1988, AAAI Press, Menl Park, California, 802-807, 1988.
* D. Gunning: Deductive Spreadsheets, Defense Advanced Research Projects Agency Small Business Innovation Research, 2004.3-Topic SB043-040, 2004.
* M. Kassoff, L. Zen, A. Garg, M. Genesereth: Predicalc: A Logical Spreadsheet Management System, in Proceedings of the 31st INternational Conference on Very Large Databases, Trondheim, NOrway, 30 August - 2 September 2005, ACM, New York, New York, 1247-1250, 2005.
* M. Kassoff, M. Genesereth: Predicalc, A Logical Spreadsheet Management System, The Knowledge Engineering Review, Vol. 22:3, 281-295, Cambridge University Press, 2007.
* M. Spenke, C. Beilken: A Spreadsheet Interface for Logic Programming, in K. Bice and C. H. Lewis (eds), Proceedings of ACM CHI 89 Human Factors in Computing Systems, Austin, Texas, 30 April - 4 June 1989, ACM Press, New York, New York, 75-80, 1989.
* M. van Emden, M. Ohki, A. Takeuchi: Spreadsheets with Incremental Qeries as a User INterface for Logic Programming, New Generation Computing 4(3), 287-304, 1986.
* http://blogs.zdnet.com/emergingtech/?p=554
* http://dbgroup.ncsu.edu/musings/genesereth.html