Abstract
Preference algebra, an extension of the algebra of database relations, is a well-studied field in the area of personalized databases. It allows modelling user wishes by preference terms; they represent strict partial orders telling which database objects the user prefers over other ones. There are a number of constructors that allow combining simple preferences into quite complex, nested ones. A preference term is then used as a database query, and the results are the maximal objects according to the order it denotes. Depending on the size of the database, this can be computationally expensive. For optimisation, preference queries and the corresponding terms are transformed using a number of algebraic laws. So far, the correctness proofs for such laws have been performed by hand and in a point-wise fashion. We enrich the standard theory of relational databases to an algebraic framework that allows completely point-free reasoning about complex preferences. This black-box view is amenable to a treatment in first-order logic and hence to fully automated proofs using off-the-shelf verification tools. We exemplify the use of the calculus with some non-trivial laws, notably concerning so-called preference prefilters which perform a preselection to speed up the computation of the maximal objects proper.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Backhouse, R., van der Woude, J.: Demonic Operators and Monotype Factors. Mathematical Structures in Computer Science 3, 417–433 (1993)
Bird, R., de Moor, O.: Algebra of programming. Prentice Hall (1997)
Börzsönyi, S., Kossmann, D., Stocker, K.: The Skyline Operator. In: Data Engineering (ICDE 2001), pp. 421–430 (2001)
Desharnais, J., Möller, B., Struth, G.: Kleene Algebra With Domain. ACM Transactions on Computational Logic 7, 798–833 (2006)
Endres, M.: Semi-Skylines and Skyline Snippets - Theory and Applications. Fakultät für Angewandte Informatik, Universität Augsburg, Dissertation. Books on Demand GmbH, Norderstedt (2011) ISBN: 978-3-8423-5246-9
Kanellakis, P.: Elements of Relational Database Theory. In: Handbook of Theoretical Computer Science. Formal Models and Semantics (B), vol. B, pp. 1073–1156 (1990)
Kießling, W., Endres, M., Wenzel, F.: The Preference SQL System – An Overview. IEEE Data Eng. Bull. 34(2), 11–18 (2011)
Kießling, W., Hafenrichter, B.: Algebraic Optimization of Relational Preference Queries, Technical Report 2003-1, University of Augsburg (2003)
Hafenrichter, B., Kießling, W.: Optimization of Relational Preference Queries. In: Williams, H., Dobbie, G. (eds.) Proc. Sixteenth Australasian Database Conference, ADC 2005, Database Technologies 2005, Newcastle, Australia, January 31-February 3. CRPIT, vol. 39, pp. 175–184. Australian Computer Society (2005)
Kießling, W.: Foundations of Preferences in Database Systems. In: Very Large Databases (VLDB 2002), pp. 311–322 (2002)
Kozen, D.: Typed Kleene algebra. Technical Report TR98-1669, Computer Science Department, Cornell University (March 1998)
MacCaull, W., Orłowska, E.: A Calculus of Typed Relations. In: Berghammer, R., Möller, B., Struth, G. (eds.) RelMiCS 2003. LNCS, vol. 3051, pp. 191–201. Springer, Heidelberg (2004)
Manes, E., Benson, D.: The Inverse Semigroup of a Sum-Ordered Semiring. Semigroup Forum 31, 129–152 (1985)
Möller, B., Roocks, P.: Proof of the Distributive Law for Prioritisation and Pareto Composition, http://www.informatik.uni-augsburg.de/lehrstuehle/dbis/pmi/staff/roocks/publications/distributivity_proof.pdf
Roocks, P., Endres, M., Mandl, S., Kießling, W.: Composition and Efficient Evaluation of Context-Aware Preference Queries. In: Lee, S.-g., Peng, Z., Zhou, X., Moon, Y.-S., Unland, R., Yoo, J. (eds.) DASFAA 2012, Part II. LNCS, vol. 7239, pp. 81–95. Springer, Heidelberg (2012)
Schmidt, G., Ströhlein, T.: Relations and Graphs: Discrete Mathematics for Computer Scientists. EATCS Monographs on Theoretical Computer Science (1993)
Schmidt, G., Hattensperger, C., Winter, M.: Heterogeneous relation algebra. In: Brink, C., Kahl, W., Schmidt, G. (eds.) Relational Methods in Computer Science. Advances in Computer Science, pp. 39–53. Springer, Vienna (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Möller, B., Roocks, P., Endres, M. (2012). An Algebraic Calculus of Database Preferences. In: Gibbons, J., Nogueira, P. (eds) Mathematics of Program Construction. MPC 2012. Lecture Notes in Computer Science, vol 7342. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31113-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-31113-0_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31112-3
Online ISBN: 978-3-642-31113-0
eBook Packages: Computer ScienceComputer Science (R0)