HR-SQL: extending SQL with hypothetical reasoning and improved recursion for current database systems. (English) Zbl 1435.68077
Summary: In this work we present a formalization, backed with a contrasted implementation, of a relational database language (called HR-SQL) that extends SQL in two aspects. On the one hand, including non-linear and mutual recursion. On the other hand, including hypothetical relations and queries. Regarding expressiveness, HR-SQL allows a novel form of hypothetical reasoning, completely integrated with recursive definitions. In addition, aggregate functions are added. Regarding formalization, the extended language is founded on a stratified fixpoint semantics based on logic programming techniques. We include results of the existence of such fixpoints. An algorithm that transforms a database containing hypothetical definitions into an equivalent one without hypothesis and its correctness proof are presented. Regarding the implementation, we introduce here a system that incorporates the aforementioned benefits and enhances former implementations in several areas. The current HR-SQL system is targeted to several state-of-the-art relational database systems, and could be used with any SQL-based system with minor modifications in the implementation.
MSC:
| 68P15 | Database theory |
References:
| [1] | Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Databases (1995), Addison-Wesley · Zbl 0848.68031 |
| [2] | Alvarez-Picallo, M.; Eyers-Taylor, A.; Peyton Jones, M.; Ong, C.-H. L., Fixing incremental computation, (Caires, L., Programming Languages and Systems (2019), Springer International Publishing), 525-552 · Zbl 1524.68069 |
| [3] | Aranda-López, G.; Nieva, S.; Sáenz-Pérez, F.; Sánchez-Hernández, J., Implementing a fixpoint semantics for a constraint deductive database based on hereditary Harrop formulas, (Proceedings of the 11th International ACM SIGPLAN Symposium of Principles and Practice of Declarative Programing (PPDP’09) (2009), ACM Press), 117-128 |
| [4] | Aranda-López, G.; Nieva, S.; Sáenz-Pérez, F.; Sánchez-Hernández, J., Formalizing a broader recursion coverage in SQL, (Symposium on Practical Aspects of Declarative Languages (PADL’13). Symposium on Practical Aspects of Declarative Languages (PADL’13), LNCS, vol. 7752 (2013)), 93-108 |
| [5] | Aranda-López, G.; Nieva, S.; Sáenz-Pérez, F.; Sánchez-Hernández, J., R-SQL: An SQL Database System with Extended Recursion, Electronic Communications of the EASST, vol. 64 (2013), Programming and Computer Languages |
| [6] | Aranda-López, G.; Nieva, S.; Sáenz-Pérez, F.; Sánchez-Hernández, J., Incorporating hypothetical views and extended recursion into sql database systems, (Mcmillan, K.; Middeldorp, A.; Sutcliffe, G.; Voronkov, A., LPAR-19. LPAR-19, EPiC Series, vol. 26 (2014), EasyChair), 9-22 |
| [7] | Arenas, M.; Bertossi, L., Hypothetical temporal reasoning in databases, J. Intell. Inf. Syst., 19, 2, 231-259 (2002) |
| [8] | Balbin, I.; Ramamohanarao, K., A generalization of the differential approach to recursive query evaluation, J. Log. Program., 4, 3, 259-262 (1987) · Zbl 0636.68125 |
| [9] | Balmin, A.; Papadimitriou, T.; Papakonstantinou, Y., Hypothetical queries in an OLAP environment, (Proceedings of the 26th International Conference on Very Large Data Bases, VLDB ’00 (2000), Morgan Kaufmann Publishers Inc.), 220-231 |
| [10] | Bertino, E.; Catania, B.; Gori, R., Enhancing the expressive power of the U-datalog language, Theory Pract. Log. Program., 1, 1, 105-122 (2001) · Zbl 1066.68521 |
| [11] | Bonner, A.; Kifer, M., A logic for programming database transactions, (Chomicki, J.; Saake, G., Logics for Databases and Information Systems. Logics for Databases and Information Systems, The Springer International Series in Engineering and Computer Science, vol. 436 (1998), Springer US), 117-166 · Zbl 0908.03037 |
| [12] | Bonner, A. J., Hypothetical datalog: negation and linear recursion, (The ACM Symposium on the Principles of Database Systems (PODS) (1989)), 286-300 |
| [13] | Bonner, A. J.; McCarty, L. T., Adding negation-as-failure to intuitionistic logic programming, (Lusk, E. L.; Overbeek, R. A., Logic Programming. Logic Programming, Proceedings of the North American Conference (1989), The MIT Press), 681-703 |
| [14] | Chen, W., Programming with logical queries, bulk updates and hypothetical reasoning, IEEE Trans. Knowl. Data Eng., 9, 587-599 (1995) |
| [15] | Christiansen, H.; Andreasen, T., A practical approach to hypothetical database queries, (Transactions and Change in Logic Databases. Transactions and Change in Logic Databases, LNCS, vol. 1472 (1998), Springer), 340-355 |
| [16] | Cohen, S.; Gil, J. Y.; Zarivach, E., Datalog programs over infinite databases, revisited, (Database Programming Languages: 11th International Symposium, DBPL 2007. Database Programming Languages: 11th International Symposium, DBPL 2007, Vienna, Austria, September 23-24, 2007, Revised Selected Papers (2007), Springer Berlin Heidelber: Springer Berlin Heidelber Berlin, Heidelberg), 32-47 |
| [17] | Dietrich, S., Understanding Relational Database Query Languages (2001), Prentice Hall |
| [18] | Finkelstein, S. J.; Mattos, N.; Mumick, I. S.; Pirahesh, H., Expressing Recursive Queries in SQL (1996), Technical Report, ISO |
| [19] | Garcia-Molina, H.; Ullman, J. D.; Widom, J., Database Systems - The Complete Book (2009), Pearson Education |
| [20] | Golfarelli, M.; Rizzi, S., What-if simulation modeling in business intelligence, Int. J. Data Warehous. Min., 5, 4, 24-43 (2009) |
| [21] | Green, T. J.; Huang, S. S.; Loo, B. T.; Zhou, W., Datalog and recursive query processing, Found. Trends Databases, 5, 2, 105-195 (November 2013) · Zbl 1278.68087 |
| [22] | Griffin, T.; Hull, R., A framework for implementing hypothetical queries, (SIGMOD Conference (1997)), 231-242 |
| [23] | Hilkevich, Z., Oracle SQL Tricks and Workarounds: Expert Guide to Oracle SQL Excellence (2011), AuthorHouse: AuthorHouse Bloomington, IN, USA |
| [24] | Houtsma, M. A.W.; Apers, P. M.G., Algebraic optimization of recursive queries, Data Knowl. Eng., 7, 299-325 (1991) |
| [25] | Inmon, W. H., Building the Data Warehouse (2005), QED Information Sciences, Inc. |
| [26] | ISO/IEC, SQL:2011 ISO/IEC 9075(1-4,9-11,13,14):2011 Standard, 2011. |
| [27] | Kaser, O.; Ramakrishnan, C. R.; Pawagi, S., On the conversion of indirect to direct recursion, ACM Lett. Program. Lang. Syst., 2, 1-4, 151-164 (1993) |
| [28] | Kowalski, R. A., Logic for data description, (Logic and Data Bases (1977)), 77-103 |
| [29] | Mumick, I. S.; Pirahesh, H., Implementation of magic-sets in a relational database system, (Proceedings of the ACM SIGMOD International Conference on Management of Data, vol. 23 (1994)), 103-114 |
| [30] | Nieva, S.; Sáenz-Pérez, F.; Sánchez-Hernández, J., Formalizing a constraint deductive database language based on hereditary Harrop formulas with negation, (FLOPS’08. FLOPS’08, LNCS, vol. 4989 (2008), Springer-Verlag), 289-304 · Zbl 1137.68339 |
| [31] | Oracle, Database Data Warehousing Guide, 11g Release 2 (11.2) Part Number E25554-01, 2011. |
| [32] | Ordonez, C., Optimization of linear recursive queries in SQL, IEEE Trans. Knowl. Data Eng., 22, 2, 264-277 (2010) |
| [33] | Ramamohanarao, K.; Harland, J., An introduction to deductive database languages and systems, VLDB J., 3, 2, 107-122 (1994) |
| [34] | Reiter, R., Towards a logical reconstruction of relational database theory, (On Conceptual Modelling (Intervale) (1982)), 191-233 |
| [35] | Revesz, P. Z., Safe query languages for constraint databases, ACM Trans. Database Syst., 23, 1, 58-99 (March 1998) |
| [36] | Revesz, P. Z., Introduction to Constraint Databases (2002), Springer · Zbl 0995.68035 |
| [37] | Sáenz-Pérez, F., ACIDE: an integrated development environment configurable for LaTeX, PracTeX J., 2007, 3 (August 2007), available at |
| [38] | Sáenz-Pérez, F., Implementing tabled hypothetical datalog, (Proceedings of the 25th IEEE International Conference on Tools with Artificial Intelligence, ICTAI’13 (2013)), 596-601 |
| [39] | Sáenz-Pérez, F., Datalog educational system (2016) |
| [40] | Shepherdson, J., Negation in logic programming, (Minker, J., Foundations of Deductive Databases and Logic Programming (1988), Kaufmann), 19-88 · Zbl 0718.68020 |
| [41] | Stonebraker, M.; Keller, K., Embedding expert knowledge and hypothetical data bases into a data base system, (The 1980 ACM SIGMOD International Conference on Management of Data, SIGMOD ’80 (1980), ACM), 58-66 |
| [42] | Tarski, A., A lattice-theoretical fixpoint theorem and its applications, Pac. J. Math., 5, 285-309 (1955) · Zbl 0064.26004 |
| [43] | Terracina, G.; Leone, N.; Lio, V.; Panetta, C., Experimenting with recursive queries in database and logic programming systems, Theory Pract. Log. Program., 8, 2, 129-165 (2008) · Zbl 1142.68338 |
| [44] | Ullman, J., Database and Knowledge-Base Systems Vols. I (Classical Database Systems) and II (The New Technologies) (1995), Computer Science Press |
| [45] | Watson, H. J.; Wixom, B. H., The current state of business intelligence, Computer, 40, 9, 96-99 (2007) |
| [46] | Zaniolo, C.; Ceri, S.; Faloutsos, C.; Snodgrass, R. T.; Subrahmanian, V. S.; Zicari, R., Advanced Database Systems (1997), Morgan Kaufmann Publishers Inc. · Zbl 0877.68037 |
| [47] | Zhang, Y.; Chen, H.; Sheng, H.; Wu, Z., Applying hypothetical queries to e-commerce systems to support reservation and personal preferences, (Proceedings of the 11th International Database Engineering and Applications Symposium, IDEAS ’07 (2007), IEEE Computer Society), 46-53 |
| [48] | Zhou, G.; Chen, H.; Zhang, Y., Hypothetical queries on multidimensional dataset, (Wang, S.; Yu, L.; Wen, F.; He, S.; Fang, Y.; Lai, K. K., BIFE (2009), IEEE Computer Society), 539-543 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
