Evaluating very large datalog queries on social networks

ABSTRACT

We consider a near future scenario in which users of a Web 2.0 application, such as a social network, contribute to the application not only data, but also rules which automatically query, utilize and create the data. For example, a user of a social network can define rules that automatically manage the user's friends list, the sending of various announcements, filtering of messages and more.

We examine the probable case of automated addition of connections by a participant. The connections to be added are defined using a query, associated to each participant. For this, we introduce and study the Query Network model, a graph-based model in which every node models a network participant and is associated with a Datalog rule. The union of all these individual user rules constitutes a very large, recursive, Datalog program whose size is of the order of magnitude of the size of the data being queried (data whose size in a social network can easily exceed 1TB). This greatly differs from the traditional assumption that queries are small and data are large. In particular, traditional optimizers will be hard pressed to handle such queries. This is the case even if queries are 'translated' to SQL (using views) and their union is transformed to a very large SQL query.

We have designed, built and experimented with evaluation algorithms for such query networks. Experiments with both synthetic and real datasets demonstrate the usefulness and high effectiveness of our methods. Extensions to the model are proposed, their implementation and testing are the subject of on-going work.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 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: R. Agrawal et. al. The Claremont Report on Database Research. Berkeley, California, 2008.
• 4: Sihem Amer-Yahia , Volker Markl , Alon Halevy , AnHai Doan , Gustavo Alonso , Donald Kossmann , Gerhard Weikum, Databases and Web 2.0 panel at VLDB 2007, ACM SIGMOD Record, v.37 n.1, March 2008 [doi>10.1145/1374780.1374794]
• 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: The Britannica Online Encyclopedia. http://www.britannica.com.
• 7: Faiz Arni , Kayliang Ong , Shalom Tsur , Haixun Wang , Carlo Zaniolo, The deductive database system ℒ𝒟ℒ++, Theory and Practice of Logic Programming, v.3 n.1, p.61-94, January 2003 [doi>10.1017/S1471068402001515]
• 8: Robert Baumgartner , Sergio Flesca , Georg Gottlob, The Elog Web Extraction Language, Proceedings of the Artificial Intelligence on Logic for Programming, p.548-560, December 03-07, 2001
• 9: François Bry , Tim Furche , Benedikt Linse , Andreas Schroeder, Efficient evaluation of n-ary conjunctive queries over trees and graphs, Proceedings of the 8th annual ACM international workshop on Web information and data management, November 10-10, 2006, Arlington, Virginia, USA [doi>10.1145/1183550.1183555]
• 10: A. Chandra, P. Merlin, Optimal implementation of conjunctive queries in relational databases. 9th ACM Symposium on the Theory of Computing, 1997.
• 11: Sara Cohen , Yaron Kanza , Yehoshua Sagiv, SQL4X: A Flexible Query Language for XML and Relational Databases, Revised Papers from the 8th International Workshop on Database Programming Languages, p.263-280, September 08-10, 2001
• 12: The DBLP Computer Science Bibliography, 2008. http://www.informatik.uni-trier.de/ley/db/
• 13: R. I. M. Dunbar: Neocortex size as a constraint on group size in primates. In Journal of Human Evolution 22, 1992.
• 14: R. I. M. Dunbar: Coevolution of neocortical size, group size and language in humans. In Behavioral and Brain Sciences 16(4), 1993.
• 15: Facebook Social Utility. http://www.facebook.com, 2008.
• 16: Facebook Query Language. http://developers.facebook.com, 2008.
• 17: Sushant Jain , Ratul Mahajan , Dan Suciu, Translating XSLT programs to Efficient SQL queries, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511526]
• 18: E. M. Jin, M. Girvan, M. E. J. Newman: Structure of growing social networks. Physical Review E, Vol. 64, 2001.
• 19: Wolfgang May, XPath-logic and XPathLog: A logic-programming style XML data manipulation language, Theory and Practice of Logic Programming, v.4 n.3, p.239-287, May 2004 [doi>10.1017/S147106840300187X]
• 20: LinkedIn, Professional Network Management. http://www.linkedin.com, 2008.
• 21: Metis - Family of Multilevel Partitioning Algorithms. Karypis Lab, University of Minnesota. http://glaros.dtc.umn.edu/gkhome/views/metis, 2008.
• 22: Modeling self-organization of communication and topology in social networks. http://cmol.nbi.dk/models/inforew/inforew.html
• 23: MySpace (a place for firends). http://www.myspace.com, 2008.
• 24: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• 25: R. Ronen and O. Shmueli. Conjunctive Queries over DAGs. In NGITS 2006.
• 26: Royi Ronen , Oded Shmueli, Evaluation of datalog extended with an XPath predicate, Proceedings of the 9th annual ACM international workshop on Web information and data management, November 09-09, 2007, Lisbon, Portugal [doi>10.1145/1316902.1316905]
• 27: Royi Ronen , Oded Shmueli, Using a relational processor and an XPath processor to evaluate joint queries, Proceedings of the 2008 EDBT workshop on Database technologies for handling XML information on the web, March 25-25, 2008, Nantes, France [doi>10.1145/1416691.1416695]
• 28: International Organization for Standardization (ISO). I.T. DB Language SQL Part 14: XML-Related Specifications (SQL/XML).
• 29: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 30: Wikipedia - The Free Encyclopedia. http://en.wikipedia.org/.
• 31: Wikipedia entry on Social Networks. http://en.wikipedia.org/wiki/Social_network.
• 32: XPath 1999. http://www.w3.org/TR/xpath.
• 33: XQuery 1.0. http://www.w3.org/TR/xquery.