×

zbMATH — the first resource for mathematics

An algebra of database preferences. (English) Zbl 1329.68094
Summary: Preferences allow more flexible and personalised queries in database systems. Evaluation of such a query means to select the maximal elements from the respective database w.r.t. the preference, which is a partial strict-order. We present a point-free calculus of such preferences and exemplify its use in proving algebraic laws about preferences that can be used in query optimisation. We show that this calculus can be mechanised using off-the-shelf automated first-order theorem provers.

MSC:
68P15 Database theory
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
Software:
Preference SQL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Backhouse, R.; van der Woude, J., Demonic operators and monotype factors, Math. Struct. Comput. Sci., 3, 417-433, (11 1993)
[2] Bird, R.; de Moor, O., Algebra of programming, (Sep. 1996), Prentice Hall PTR
[3] Borzsony, S.; Kossmann, D.; Stocker, K., The skyline operator, (Proceedings 17th International Conference on Data Engineering, 2001, (2001)), 421-430
[4] Chomicki, J., Preference formulas in relational queries, (TODS ’03, ACM Transactions on Database Systems, vol. 28, (2003), ACM Press New York, NY, USA), 427-466
[5] Desharnais, J.; Möller, B.; Struth, G., Kleene algebra with domain, ACM Trans. Comput. Log., 7, 4, 798-833, (Oct. 2006)
[6] Endres, M., Semi-skylines and skyline snippets - theory and applications, (2011), Books on Demand GmbH Norderstedt, Fakultät für Angewandte Informatik, Universität Augsburg, Dissertation
[7] Fishburn, P. C., Utility theory for decision making, (1970), Tech. rep., New York, NY, USA · Zbl 0213.46202
[8] Höfner, P.; Struth, G., On automating the calculus of relations, (Automated Reasoning, (2008), Springer), 50-66 · Zbl 1165.68460
[9] P.C. Kanellakis, Elements of relational database theory, Tech. rep., Providence, RI, USA, 1989. · Zbl 0900.68090
[10] Kießling, W., Foundations of preferences in database systems, (VLDB ’02: Proceedings of the 28th International Conference on Very Large Data Bases, (2002), VLDB Hong Kong, China), 311-322
[11] Kießling, W., Preference queries with SV-semantics, (Haritsa, J. R.; Vijayaraman, T. M., COMAD ’05: Advances in Data Management 2005, Proceedings of the 11th International Conference on Management of Data, (2005), Computer Society of India Goa, India), 15-26
[12] Kießling, W.; Endres, M.; Wenzel, F., The preference SQL system - an overview, Q. Bull. IEEE Comput. Soc., Tech. Comm. Database Eng., 34, 2, 11-18, (2011)
[13] Kozen, D., Typed Kleene algebra, (1998), Computer Science Department, Cornell University, Tech. Rep. TR98-1669
[14] MacCaull, W.; Orłowska, E., A calculus of typed relations, (Berghammer, R.; Möller, B.; Struth, G., Relational and Kleene-Algebraic Methods in Computer Science, Lecture Notes in Computer Science, vol. 3051, (2004), Springer Berlin, Heidelberg), 191-201 · Zbl 1088.68048
[15] Maddux, R. D., Relation algebras. advances in computing, 22-38, (1997), Springer-Verlag Wien, New York, Ch. 2 · Zbl 0885.03047
[16] Manes, E.; Benson, D., The inverse semigroup of a sum-ordered semiring, Semigroup Forum, 31, 1, 129-152, (1985) · Zbl 0549.06014
[17] Marimont, R. B., A new method of checking the consistency of precedence matrices, J. ACM, 6, 2, 164-171, (Apr. 1959)
[18] Möller, B.; Roocks, P., An algebra of layered complex preferences, (Kahl, W.; Griffin, T., Relational and Algebraic Methods in Computer Science, Lecture Notes in Computer Science, vol. 7560, (2012), Springer Berlin, Heidelberg), 294-309 · Zbl 1330.68057
[19] Möller, B.; Roocks, P., Proof of the distributive law for prioritisation and Pareto composition, (2012)
[20] Möller, B.; Roocks, P.; Endres, M., An algebraic calculus of database preferences, (Gibbons, J.; Nogueira, P., Mathematics of Program Construction., Lecture Notes in Computer Science, vol. 7342, (2012), Springer Berlin, Heidelberg), 241-262 · Zbl 1358.68087
[21] Roocks, P.; Endres, M.; Mandl, S.; Kießling, W., Composition and efficient evaluation of context-aware preference queries, (DASFAA ’12: Proceedings of the 17th International Conference on Database Systems for Advanced Applications, (2012))
[22] Schmidt, G.; Hattensperger, C.; Winter, M., Heterogeneous relation algebra, (Brink, C.; Kahl, W.; Schmidt, G., Relational Methods in Computer Science. Advances in Computing Sciences, (1997), Springer Vienna), 39-53 · Zbl 0961.03061
[23] Schmidt, G.; Ströhlein, T., Relations and graphs: discrete mathematics for computer scientists, EATCS Monographs on Theoretical Computer Science, (1993) · Zbl 0900.68328
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.