טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentRonen Royi
SubjectModels and Methods for Advanced Web Applications
and Social Network Automation
DepartmentDepartment of Computer Science
Supervisor Professor Oded Shmueli
Full Thesis textFull thesis text - English Version


Abstract

This work describes research on novel Web-related data management scenarios. In the first part, we describe the XPathL language and system, which combines XPath and Datalog by introducing an XPath predicate to the Datalog formalism. In the second part, we introduce the Query Network model, a basic model for social network automation using queries, with its evaluation algorithms. In the third part, we discuss social networks automation using Protocols for Social Networks, which coordinate consistency-preserving (and other) decisions in the network.


We begin by defining the XPathL data model and language, which combines both XML and relational data. We define the semantics of XPath predicates and provide examples for the usefulness of the model. The concept of values is introduced and investigated. We show some theoretical results about the language. We design evaluation algorithms for recursive and non-recursive queries, and experiment with them using the XPathL system prototype. In addition, we characterize the complexity of the closely related problem of evaluating conjunctive queries with XPath-inspired predicates on DAGs.


We turn to the Query Network model. We motivate and define the model, which uses queries to abstract the process of proposing and accepting connections in a social network. The model raises the novel database problem of how to evaluate a query whose size is in the order of magnitude of the data being queried. This is in contrast to the traditional database assumption that queries are small and data are large. We design evaluation algorithms for query networks and evaluate them using synthetic graphs as well as real social networks graphs that we derived from the DBLP dataset. We characterize the complexity of several related decision problems.


The third and last chapter is concerned with a future scenario in which social networks participants use protocols in order to efficiently interact in the social network. We introduce a model for a social network in which participants make decisions that are consistent with their friends decisions.

The protocols provide participants a means to coordinate the atomic installment of sets of decision changes, which preserve network consistency. We consider both a Twitter-like one-way communication architecture, and a Facebook-like two-way communication architecture. We develop novel methods

for controlling the concurrency of multiple protocol instances, which enable increased concurrency, by relaxing the traditional concurrency control isolation requirement.