By definition, recursion is the process of reducing a problem into a smaller version of itself (Malik, 2006).  Recursion can be further classified as either direct recursion that calls itself or indirect recursion that is dependent on another component (Malik, 2006).  Recursion is a powerful programming tool however it can incur a steep cost as it uses considerable amounts of memory and in the worst case can overflow the stack (Malik, 2006; Schalkoff, 1990).  With this basis, recursion requires careful design to ensure it leads to a base case and eventually resolves (Malik, 2006).

Relational recursion is based on recursive joins and predicate logic (Codd, 1990).  In a RDBMS setting, relational recursion can be succinctly described using Datalog notation (Garcia-Molina, Ullman & Widom, 2009. p. 222).  Datalog is a logical query language based on predicate logic and is syntactically and semantically similar to Prolog (Garcia-Molina, Ullman & Widom, 2009; Wilson & Clark, 2001).  Similar to Prolog, Datalog facilitates the representation of relational if-then rules that can query a database’s relations.  In this framework, the database may be viewed as a knowledge base and the relation’s tuples comprise the knowledge base’s asserted facts.

In the Datalog format, relations form the head and body of a Datalog query separated by an arrow (e.g. head ç body).  A rule is defined to be recursive if a predicate symbol appears in the head and also appears in the body as this will require a recursive join (Codd, 1990; Van Le, 1993).  It is common to call the head and body’s relations clauses and the head may be further distinguished as the goal (Van Le, 1993; Wilson & Clark, 2001).  From an interpretation perspective, if the Datalog body’s sub-goals can be met (i.e. tuple-based facts exist), a Boolean value is returned and the Datalog’s head or goal follows.  This type of resolution is particularly relevant to problem spaces that can be represented as directed dependency graphs.  In this instance, the system can determine if a solution is valid or exists by determining if a path of arcs exist from the sub-goals (i.e. body) to the goal (i.e. head).   This framework is consistent with SQL relational and predicate logic principles as the programmer encodes the goal or the desired result rather than how to achieve the result (Wilson & Clark, 2001).

SQL 99 includes the provision to support recursion as presented by Codd through the RECURSION and WITH keywords (Codd, 1990; Garcia-Molina, Ullman & Widom, 2009).  SQL requires recursive statements be preceded by the keyword RECURSIVE.  The WITH statement allows the programmer to define temporary relations and allows these temporary relations to be used in subsequent queries.  This allows the programmer to break up a problem space into smaller components in accord with the recursive definitional basis above.  SQL allows these temporary relations to be mutually recursive where they are defined in terms of other relations in addition to their own relation.  With this basis SQL supports both direct and indirect recursion however if an SQL query is mutually recursive, SQL limits the body to include just a single mutually recursive sub-goal.

An important facet of recursive relational logic programming is its support for anonymous variables (Wilson & Clark, 2001).  An anonymous variable is allowed to range over all possible attribute instance values of a relation’s column.  Functionally this allows an anonymous variable to be iteratively set to all values in a column and tested or compared in additional sub-goals.  If all of the body’s sub-goals are met resulting in a Boolean value of true, the anonymous variable’s value is instantiated and this value becomes part of the solution query or relation (i.e. the head clause).

Summary

SQL’s added support for recursive programming in 1999 represents an important step forward in accord with Codd’s relational theory (Codd, 1990).   The ability to program Datalog equivalent SQL queries demonstrates that SQL is truly a fourth generation language.  Furthermore, support for recursion demonstrates that today’s RDBMS are moving towards knowledge-base functionality.  This is remarkable step forward citing that knowledge-bases are central to Expert System (ES) development and serve as the critical underpinnings of semantic interoperability, knowledge representation and transfer (Graham et al., 2005; Jackson, 1999; Nagarajan, Verma, Sheth & Miller, 2007; Sheth, Gomadam & Lathem, 2007).

References

Bishop, M. (2003). Computer security. Boston, MA: Addison Wesley.

Codd, E. F. (1990). The relational model for database management: version 2.  Boston, MA: Addison-Wesley Longman Publishing Co.  Retrieved June 1, 2010 from, http://portal.acm.org/citation.cfm?id=77708.

Codd, E. F., Codd, S. B., & Salley, C. T. (1993). Providing OLAP (on-line analytical processing) to user-analysis: An IT mandate.  www.aaai.org. Retrieved July 21, 2010 from, http://www.cs.bgu.ac.il/~dbm031/dw042/Papers/olap_to_useranalysts_wp.pdf.

Elmasri, R., & Navathe, S. B. (2000).  Fundamentals of database systems. Reading MA: Addison-Wesley.

Erl, T. (2005) Service-oriented architecture: Concepts, technology, and design. Upper Saddle River, NJ: Pearson Education.

Fayyad, U., Piatetsky-Shapiro, G., & Smyth, P. (1996).  From data mining to knowledge discovery in databases. www.aaai.org. Retrieved July 21, from, http://www.daedalus.es/fileadmin/daedalus/doc/MineriaDeDatos/fayyad96.pdf

Garcia-Molina, H., Ullman, J.D., & Widom, J.   (2009).   Database systems: The complete book, (2^nd ed.).   Upper Saddle River, NJ: Pearson Prentice Hall.

Graham, S. Davis, D. Simeonov, S. Daniels, G. Brittenham, P. Nakamura, Y, Fremantle, P. Konig, D., & Zentner, C. (2005). Building Web services with Java (2^nd ed.). Indianapolis, IN: Sams Publishing

Jackson, P. (1999). Introduction to expert systems. Essex, England: Addison Wesley.

Kotler, P. & Keller, K. L. (2007). Marketing management (12^th ed.). Upper Saddle River, NJ: Pearson Publishing.

Malik, D. S. (2006). Java programming: Program design including data structures. Boston MA: Course Technology.

Nagarajan, M., Verma, K., Sheth, A. P., & Miller, J. A. (2007). Ontology driven data mediation in web services. International Journal of Web Services Research, 4(4), 104-126.  Retrieved February 16, 2009, from ABI/INFORM Global database. (Document ID: 1522690091).

Nutt, G. (2004). Operating systems (3^rd ed.). Boston, MA: Addison Wesley.

Raab, D. (2009). An about face on the database: Markers may shift from analytical two transactional databases as focus on real-time interactions increases. Information Management, 19 (5), 38.

Rivest, S., Bedard, Y., & Marchand, P. (2001). Toward better support for spatial decision making: Defining the characteristics of spatial on-line analytical processing (SOLAP).  Centre for Research in Geomatics, Laval University, Québec.  Retrieved  July 21, 2010 from, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.125.344&rep=rep1&type=pdf.

Robbins, S. P., & Judge, T. A. (2007). Organizational Behavior. Upper Saddle River, NJ: Prentice Hall.

Schalkoff, R. J. (1990). Artificial intelligence: An engineering approach. New York: McGraw-Hill.

Sheth, A. P., Gomadam, K., & Lathem, J. (2007). SA-REST: Semantically interoperable and easier-to-use services and mashups. IEEE Internet Computing, 11(6), 91-94.  Retrieved February 16, 2009, from ProQuest Computing database. (Document ID: 1424144951).

Silberschatz, A., Korth, H. F., & Sudarshan, S. (1999). Database system concepts (3^rd ed.). Boston, MA: McGraw-Hill.

Steiert, H. (2007). Towards a component-based n-Tier C/S architecture. Kaiserslautern, Germany: Department of Computer Science, Database and Information Systems Group,University of Kaiserslautern.  Retrieved January 1, 2009 from http://www.dr-gail.org/upload/p137-steiert.pdf

Van Le, T. (1993). Techniques of Prolog programming. New York: Wiley Publishing.

W3C, (2004). Web services architecture: W3C working group note 11 February 2004. Retrieved February 21, 2009 from, http://www.w3.org/TR/ws-arch/#id2260892

Weisfield, M. (2009). The object-oriented thought process (3^rd ed.). Upper Saddle River, NJ: Addison Wesley.

Wilander, J., & Kamkar, M. (2003). A comparison of publicly available tools for dynamic buffer overflow prevention. Retrieved March 28, 2010 from, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.6288&rep=rep1&type=pdf.

Wilson, L. B., & Clark, R. G. (2001).  Comparative programming languages (3^rd ed.). Essex, England: Addison-Wesley.

Wolfe, A. (2008). Is a smartphone your next computer. Information Week.  Retrieved January 7, 2009 from, http://www.informationweek.com/news/personal_tech/smartphones/showArticle.jhtml?articleID=210605369.