Abstract
The Reverse Engineering Problem (REP) in database theory involves identifying a query that separates a set of positive examples from a set of negative examples within a given database. This paper provides a comprehensive theoretical framework for REP across various query languages, including First-Order logic, Conjunctive Queries, and Regular Path Queries. By establishing a unified family of tests, the research maps the computational complexity of finding explaining queries and provides optimal bounds for query size and existence.
Introduction
In traditional database management, the workflow is unidirectional: a user formulates a query in a language like SQL or SPARQL to retrieve specific information from a database. However, modern data tasks—such as data exploration, security auditing, and the development of machine learning classifiers—often require the inverse. A user may possess examples of desired data (positive examples) and undesired data (negative examples) but lacks the technical expertise or system knowledge to write the formal query that retrieves exactly that set.
This challenge is formalized as the Reverse Engineering Problem (REP). Given a database $D$, a set of positive examples $P$, and a set of negative examples $N$, the objective is to find a query $q$ within a specific language $L$ such that $q$ perfectly "explains" the data—meaning $q(D)$ includes all elements in $P$ and excludes all elements in $N$.
Theoretical Framework and Methodology
The diversity of query languages—ranging from the First-Order (FO) logic underlying SQL to the Regular Path Queries (RPQs) used in graph databases—presents a significant hurdle for a unified theory. This research addresses this by proposing a unified family of tests designed to solve the REP across multiple paradigms:
- Relational Queries: Including First-Order logic (FO) and the "select-project-join" core represented by Conjunctive Queries (CQ) and Union of Conjunctive Queries (UCQs).
- Graph Queries: Including Regular Path Queries (RPQs) and Conjunctive Regular Path Queries (CRPQs), which are essential for navigating complex networked data.
The methodology treats reverse engineering as a definability problem. If a query exists that separates $P$ from $N$, the set $P$ is considered "definable" relative to $N$ within the constraints of language $L$. By utilizing these tests, the author establishes optimal mathematical bounds, defining the limits of how efficiently an explaining query can be identified.
Key Insights: Complexity and Conciseness
A central theme of the research is the tension between expressivity and computational tractability. The paper identifies several key insights:
The "Smallest Query" Problem
In practical applications, finding any query that separates $P$ and $N$ is often insufficient. Users typically require the most concise or "smallest" query for reasons of readability and execution efficiency. The research provides specific bounds on the size of the smallest possible explaining query, offering a roadmap for optimization.
Computational Complexity Mapping
The paper maps the computational landscape of REP, distinguishing between "tractable" scenarios (where queries can be found in reasonable time) and "intractable" ones (where the problem is NP-hard or worse). By identifying specific language restrictions—such as limiting the number of variables or the depth of the query—the author demonstrates how to reduce computational overhead to make reverse engineering feasible for real-world systems.
Bridging Database Theory and Machine Learning
Perhaps the most significant conceptual contribution is the link between database reverse engineering and relational classifier engineering. In machine learning, the task of building a classifier to categorize relational data is essentially a search for a "separator." This research suggests that database tools and definability tests can be directly applied to assist in training machine learning models, creating a theoretical bridge between these two fields.
Conclusion and Future Directions
While the theoretical foundations for REP are now more robust, significant challenges remain regarding the computational cost of expressive languages. Future research is directed toward:
- Refining Language Restrictions: Identifying the "sweet spot" where a query language remains powerful enough for complex data tasks but simple enough to allow for rapid reverse engineering.
- Heuristic Development: Moving beyond "optimal" theoretical bounds to develop practical, heuristic-based algorithms that can find "good enough" queries when exact solutions are computationally prohibitive.
- Integration with ML: Further exploring the synergy between query definability and the automated construction of relational classifiers.
By providing a unified view of reverse engineering, this work lays the groundwork for more intuitive database interfaces where users can interact with data through examples rather than complex code.
Summary updated