As most users do not precisely know the structure and/or the content of databases, their queries do not exactly reflect their information needs. The database management system (DBMS) may interact with users and use their feedback on the returned results to learn the information needs behind their queries. Current query interfaces assume that users do not learn and modify the way they express their information needs in the form of queries during their interaction with the DBMS. Using a real-world interaction workload, we show that users learn and modify how to express their information needs during their interactions with the DBMS and their learning is accurately modeled by a well-known reinforcement learning mechanism. As current data interaction systems assume that users do not modify their strategies, they cannot discover the information needs behind users’ queries effectively. We model the interaction between the user and the DBMS as a game with identical interest between two rational agents whose goal is to establish a common language for representing information needs in the form of queries. We propose a reinforcement learning method that learns and answers the information needs behind queries and adapts to the changes in users’ strategies and proves that it improves the effectiveness of answering queries, stochastically speaking. We propose two efficient implementations of this method over large relational databases. Our extensive empirical studies over real-world query workloads indicate that our algorithms are efficient and effective.

Most users do not know the structure and content of databases or concepts such as schema or formal query languages sufficiently well to express their information needs precisely in form of queries. They may convey their intents via usable but inherently ambiguous query interfaces, such as keyword or natural language queries, which are open to numerous interpretations. Thus, it is very challenging for a database management system (DBMS) to understand and satisfy the intents behind these queries. A useful source of information to decode the intent behind a query is the user feedback on the returned results, which may come in various ways, such as click-through information. To use this information, DBMS has to establish a trade-off between showing strongly reinforced answers, i.e., exploitation, and exploring never-before-shown or rarely shown answers to solicit user feedback on them, i.e. exploration. A DBMS that returns only positively reinforced results may always return a small subset of all relevant answers to a query. On the other hand, if a DBMS shows too many unseen answers to the user, it may discourage and disengage users as many such answers may not be relevant to the query. Moreover, users may learn more about the structure and content of the database and how to express intents as they submit queries and observe the returned results. Thus, they may modify the way they express intents over the course of their interactions with the DBMS.

As many users do not precisely know the structure and/or the content of databases, their queries do not exactly reflect their information needs. The database management systems (DBMS) may interact with users and leverage their feedback on the returned results to learn the information needs behind users' queries. Current query interfaces assume that users follow a fixed strategy of expressing their information needs, that is, the likelihood by which a user submits a query to express an information need remains unchanged during her interaction with the DBMS. Using a real-world interaction workload, we show that users learn and modify how to express their information needs during their interactions with the DBMS. We also show that users' learning is accurately modeled by a well-known reinforcement learning mechanism. As current data interaction systems assume that users do not modify their strategies, they cannot discover the information needs behind users' queries effectively. We model the interaction between users and DBMS as a game with identical interest between two rational agents whose goal is to establish a common language for representing information needs in form of queries. We propose a reinforcement learning method that learns and answers the information needs behind queries and adapts to the changes in users' strategies and prove that it improves the effectiveness of answering queries stochastically speaking. We analyze the challenges of efficient implementation of this method over large-scale relational databases and propose two efficient adaptations of this algorithm over large-scale relational databases. Our extensive empirical studies over real-world query workloads and large-scale relational databases indicate that our algorithms are efficient. Our empirical results also show that our proposed learning mechanism is more effective than the state-of-the-art query answering method.

Indexing is a fundamental mechanism for efficient data access. Recently, we proposed the Variable-Aligned Length (VAL) bitmap index encoding framework, which generalizes the commonly used word-aligned compression techniques. VAL presented a variable-aligned compression framework, which allows columns of a bitmap to be compressed using different encoding lengths. This flexibility creates a tunable compression that balances the trade-off between space and query processing time. The variable format of VAL presents several unique opportunities for query optimization.