abstract: As the information available to lay users through autonomous data sources continues to increase, mediators become important to ensure that the wealth of information available is tapped effectively. A key challenge that these information mediators need to handle is the varying levels of incompleteness in the underlying databases in terms of missing attribute values. Existing approaches such as Query Processing over Incomplete Autonomous Databases (QPIAD) aim to mine and use Approximate Functional Dependencies (AFDs) to predict and retrieve relevant incomplete tuples. These approaches make independence assumptions about missing values--which critically hobbles their performance when there are tuples containing missing values for multiple correlated attributes. In this thesis, I present a principled probabilis- tic alternative that views an incomplete tuple as defining a distribution over the complete tuples that it stands for. I learn this distribution in terms of Bayes networks. My approach involves min- ing/"learning" Bayes networks from a sample of the database, and using it do both imputation (predict a missing value) and query rewriting (retrieve relevant results with incompleteness on the query-constrained attributes, when the data sources are autonomous). I present empirical studies to demonstrate that (i) at higher levels of incompleteness, when multiple attribute values are missing, Bayes networks do provide a significantly higher classification accuracy and (ii) the relevant possible answers retrieved by the queries reformulated using Bayes networks provide higher precision and recall than AFDs while keeping query processing costs manageable. / Dissertation/Thesis / M.S. Computer Science 2011

O uso de técnicas de replicação de dados em dispositivos móveis permite que uma aplicação móvel compartilhe dados com um servidor e possa atuar sobre tais dados durante períodos de desconexão. Embora essa característica seja fundamental em diversos domínios, a reconciliação das transações que foram aplicadas sobre a réplica móvel dos dados apresenta-se como um desafio a ser superado. O uso de bloqueios apresenta-se impraticável em determinados domínios de aplicação. Por outro lado, ao permitir a execução de operações de escrita em diversas réplicas sem uma sincronização a priori, o sistema se torna suscetível a conflitos de atualização, sendo necessário a implementação de um mecanismo de resolução de conflitos. Resolver conflitos é uma tarefa complexa e propensa a erros, em especial nos casos em que há a necessidade de intervenção humana. Diante desse cenário, foi desenvolvido um modelo para controle de transações em bancos de dados autônomos que faz uso de metadados e multiversão de banco de dados de forma a permitir a auditoria e retificação de resoluções de conflitos. Isso torna a resolução de conflitos uma operação não destrutiva, reduzindo, assim, o impacto de uma resolução de conflito incorreta. Neste trabalho é apresentado também um arcabouço para reconciliação de transações que implementa o modelo proposto. Como estudo de caso, o arcabouço desenvolvido foi utilizado para implementar a integração entre dois sistemas reais que possuem necessidades de replicação de dados e atualizações desconectadas. / The use of data replication techniques on mobile devices allows a mobile application to share data with a server and to work on such data while disconnected. While this feature is crucial in some application domains, the reconciliation of transactions applied to the mobile replica of data proves to be challenging. The use of locking is not feasible in some application domains. However, allowing write operations to be applied on several replicas without \\emph{a priori} synchronization makes the system susceptible to update conflicts, requiring a conflict resolution mechanism. Conflict resolution is a complex and error prone task, specially when human intervention is involved. Given this scenario, we developed a transactions control model for autonomous databases that uses metadata and database versioning to provide auditing and rectification of conflict resolutions. This turns the conflict resolution into a nondestructive operation, thus reducing the impact of an incorrect conflict resolution. This work presents also a framework for transaction reconciliation that implements the proposed model. As a case study, the developed framework was used to integrate two real systems that needed data replication and disconnected updates.

O uso de técnicas de replicação de dados em dispositivos móveis permite que uma aplicação móvel compartilhe dados com um servidor e possa atuar sobre tais dados durante períodos de desconexão. Embora essa característica seja fundamental em diversos domínios, a reconciliação das transações que foram aplicadas sobre a réplica móvel dos dados apresenta-se como um desafio a ser superado. O uso de bloqueios apresenta-se impraticável em determinados domínios de aplicação. Por outro lado, ao permitir a execução de operações de escrita em diversas réplicas sem uma sincronização a priori, o sistema se torna suscetível a conflitos de atualização, sendo necessário a implementação de um mecanismo de resolução de conflitos. Resolver conflitos é uma tarefa complexa e propensa a erros, em especial nos casos em que há a necessidade de intervenção humana. Diante desse cenário, foi desenvolvido um modelo para controle de transações em bancos de dados autônomos que faz uso de metadados e multiversão de banco de dados de forma a permitir a auditoria e retificação de resoluções de conflitos. Isso torna a resolução de conflitos uma operação não destrutiva, reduzindo, assim, o impacto de uma resolução de conflito incorreta. Neste trabalho é apresentado também um arcabouço para reconciliação de transações que implementa o modelo proposto. Como estudo de caso, o arcabouço desenvolvido foi utilizado para implementar a integração entre dois sistemas reais que possuem necessidades de replicação de dados e atualizações desconectadas. / The use of data replication techniques on mobile devices allows a mobile application to share data with a server and to work on such data while disconnected. While this feature is crucial in some application domains, the reconciliation of transactions applied to the mobile replica of data proves to be challenging. The use of locking is not feasible in some application domains. However, allowing write operations to be applied on several replicas without \\emph{a priori} synchronization makes the system susceptible to update conflicts, requiring a conflict resolution mechanism. Conflict resolution is a complex and error prone task, specially when human intervention is involved. Given this scenario, we developed a transactions control model for autonomous databases that uses metadata and database versioning to provide auditing and rectification of conflict resolutions. This turns the conflict resolution into a nondestructive operation, thus reducing the impact of an incorrect conflict resolution. This work presents also a framework for transaction reconciliation that implements the proposed model. As a case study, the developed framework was used to integrate two real systems that needed data replication and disconnected updates.