Declarative networking: language, execution and optimization

ABSTRACT

The networking and distributed systems communities have recently explored a variety of new network architectures, both for application-level overlay networks, and as prototypes for a next-generation Internet architecture. In this context, we have investigated declarative networking: the use of a distributed recursive query engine as a powerful vehicle for accelerating innovation in network architectures [23, 24, 33]. Declarative networking represents a significant new application area for database research on recursive query processing. In this paper, we address fundamental database issues in this domain. First, we motivate and formally define the Network Datalog (NDlog) language for declarative network specifications. Second, we introduce and prove correct relaxed versions of the traditional semi-naïve query evaluation technique, to overcome fundamental problems of the traditional technique in an asynchronous distributed setting. Third, we consider the dynamics of network state, and formalize the iheventual consistencyl. of our programs even when bursts of updates can arrive in the midst of query execution. Fourth, we present a number of query optimization opportunities that arise in the declarative networking context, including applications of traditional techniques as well as new optimizations. Last, we present evaluation results of the above ideas implemented in our P2 declarative networking system, running on 100 machines over the Emulab network testbed.

REFERENCES

• 1: GT-ITM. http://www.cc.gatech.edu/projects/gtitm/.
• 2: Serge Abiteboul , Zoë Abrams , Stefan Haar , Tova Milo, Diagnosis of asynchronous discrete event systems: datalog to the rescue!, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065214]
• 3: I. Balbin , K. Ramamohanarao, A generalization of the differential approach to recursive query evaluation, Journal of Logic Programming, v.4 n.3, p.259-262, Sept. 1987 [doi>10.1016/0743-1066(87)90004-5]
• 4: Francois Bancilhon, Naive evaluation of recursively defined relations, On knowledge base management systems: integrating artificial intelligence and d atabase technologies, Springer-Verlag New York, Inc., New York, NY, 1986
• 5: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• 6: Cassandra: Distributed Access Control Policies with Tunable Expressiveness, Proceedings of the Fifth IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY'04), p.159, June 07-09, 2004
• 7: P. A. Bernstein, U. Dayal, D. J. DeWitt, D. Gawlick, J. Gray, M. Jarke, B. G. Lindsay, P. C. Lockemann, D. Maier, E. J. Neuhold, A. Reuter, L. A. Rowe, H.-J. Schek, J. W. Schmidt, M. Schrefl, and M. Stonebraker. Future Directions in DBMS Research. SIGMOD Record, 18(1):17--26, 1989.
• 8: Filippo Cacace , Stephano Ceri , Maurice Houtsma, A survey of parallel execution strategies for transitive closure and logic programs, Distributed and Parallel Databases, v.1 n.4, p.337-382, Oct. 1993 [doi>10.1007/BF01264013]
• 9: Diego Calvanese , Giuseppe De Giacomo , Moshe Y. Vardi, Decidable Containment of Recursive Queries, Proceedings of the 9th International Conference on Database Theory, p.330-345, January 08-10, 2003
• 10: Emulab. http://www.emulab.net.
• 11: N. Feamster and H. Balakrishnan. Correctness properties for Internet routing. In Allerton Conference on Communication, Control, and Computing, Sept. 2005.
• 12: Filippo Furfaro , Sergio Greco , Sumit Ganguly , Carlo Zaniolo, Pushing extrema aggregates to optimize logic queries, Information Systems, v.27 n.5, p.321-343, July 2002 [doi>10.1016/S0306-4379(02)00006-6]
• 13: Overcoming barriers to disruptive innovation in networking. Report of NSF Workshop, Jan. 2005.
• 14: Goetz Graefe, Encapsulation of parallelism in the Volcano query processing system, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.102-111, May 23-26, 1990, Atlantic City, New Jersey, United States
• 15: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 16: Z. J. Haas. A New Routing Protocol for the Reconfigurable Wireless Networks. In IEEE Int. Conf. on Universal Personal Communications, 1997.
• 17: R. Huebsch, B. Chun, J. Hellerstein, B. T. Loo, P. Maniatis, T. Roscoe, S. Shenker, I. Stoica, and A. R. Yumerefendi. The Architecture of PIER: an Internet-Scale Query Processor. In CIDR, 2005.
• 18: Jeffery Ullman. Assigning an Appropriate Meaning to Database Logic with Negation. Computers as Our Better Partners, pages 216--225, 1994.
• 19: Trevor Jim , Dan Suciu, Dynamically distributed query evaluation, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.28-39, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375557]
• 20: D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing, volume 353. 1996.
• 21: Ravi Krishnamurthy , Raghu Ramakrishnan , Oded Shmueli, A framework for testing safety and effective computability, Journal of Computer and System Sciences, v.52 n.1, p.100-124, Feb. 1996 [doi>10.1006/jcss.1996.0009]
• 22: Laurent Vieille. Recursive Axioms in Deductive Database: The Query-Subquery Approach. In 1st International Conference on Expert Database Systems, 1986.
• 23: Boon Thau Loo , Tyson Condie , Joseph M. Hellerstein , Petros Maniatis , Timothy Roscoe , Ion Stoica, Implementing declarative overlays, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 24: Boon Thau Loo , Joseph M. Hellerstein , Ion Stoica , Raghu Ramakrishnan, Declarative routing: extensible routing with declarative queries, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 25: Larry L. Peterson , Bruce S. Davie, Computer Networks: A Systems Approach, 3rd Edition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 26: L. Peterson, S. Shenker, and J. Turner. Overcoming the Internet Impasse Through Virtualization. In HotNets-III, 2004.
• 27: R. Ramakrishnan, K. A. Ross, D. Srivastava, and S. Sudarshan. Efficient Incremental Evaluation of Queries with Aggregation. In SIGMOD, 1992.
• 28: R. Ramakrishnan and J. D. Ullman. A Survey of Research on Deductive Database Systems. Journal of Logic Programming, 23(2):125--149, 1993.
• 29: Venugopalan Ramasubramanian , Zygmunt J. Haas , Emin Gün Sirer, SHARP: a hybrid adaptive routing protocol for mobile ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778450]
• 30: J Rohmer , R Lescoeur , J M Kerisit, The Alexander method-a technique for the processing of recursive axioms in deductive databases, New Generation Computing, v.4 n.3, p.273-285, 1986 [doi>10.1007/BF03037407]
• 31: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 32: J. Shao , D. A. Bell , M. E. C. Hull, An experimental performance study of a pipelined recursive query processing strategy, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.30-43, July 02-04, 1990, Dublin, Ireland [doi>10.1145/319057.319061]
• 33: A. Singh, P. Maniatis, T. Roscoe, and P. Druschel. Distributed Monitoring and Forensics in Overlay Networks. In Eurosys, 2006.
• 34: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 35: M. Stonebraker and J. M. Hellerstein, editors. Readings in Database Systems, Third Edition. Morgan Kaufmann, San Francisco, 1998.
• 36: S. Sudarshan , Raghu Ramakrishnan, Aggregation and Relevance in Deductive Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.501-511, September 03-06, 1991
• 37: John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Algorithms, Design, Languages

Keywords:
declarative networks, recursive queries