Automated creation of a forms-based database query interface

Magesh Jayapandian, H. V. JagadishPVLDB 2008 · OpenReview

TL;DR

This paper presents an automated method for generating forms-based database query interfaces directly from a database's schema and content. This approach aims to significantly reduce the manual effort required for interface design, making databases more accessible by creating expressive yet simple query forms that can satisfy a high percentage of user queries.

What Problem Does This Paper Address?

Designing effective forms-based query interfaces for databases is a challenging task. While forms are intuitive for users, creating a set of forms that can express a wide range of queries without becoming overly complex or numerous is difficult. Developers often struggle to anticipate all possible user needs, leading to interfaces that fail to support certain queries, even when the data is present in the database. This paper tackles the problem of automatically generating such interfaces, aiming to balance query expressivity with interface simplicity, especially when user query logs are unavailable.

Methods

The authors propose a multi-stage approach to automatically generate forms:

  1. Schema Analysis: They analyze the database schema (entities, attributes, relationships) and its content to estimate the "queriability" of each schema component. This involves calculating metrics like absolute cardinality (number of instances) and relative cardinality (participation in relationships) to gauge importance.
  2. Postulates and Queriability Metrics: Several postulates are introduced to guide the estimation of queriability. For example, an entity's queriability depends on its connectedness to other schema elements and its data cardinality. Related entities' queriability is a function of their individual queriabilities and the strength of their relationships. Attributes' queriability is based on their "necessity" to their parent entity.
  3. Form Composition: Based on the computed queriabilities, the system selects the most "queriable" entities to serve as the focus for forms. It then identifies related entities and attributes to include, using thresholds to control the number of forms and the complexity of each form (number of fields).
  4. Operator-Specific Queriability: To further refine form content, the authors define operator-specific queriability for attributes (e.g., for selection, projection, sorting, aggregation). This considers factors like attribute selectivity and necessity to determine which operations are most likely to be used with an attribute.
  5. Algorithm: A set of algorithms (AnalyzeSchema, AssignSchemaCompntsToForms, CreateFormComponents) orchestrates this process, taking the database and complexity thresholds as input and outputting a set of forms.

Datasets

The system was evaluated using three datasets:

  • MiMI (Michigan Molecular Interactions): A real-world molecular interactions database with a complex XML schema. The evaluation used a log of 3,844 XQuery statements from real users.
  • Geoquery: A database containing geographical information about the United States, originally in Prolog and translated to XML for the study. The evaluation used a set of 880 natural language questions, translated into XQuery.
  • Jobsquery: A dataset of computer-related job postings, also translated from Prolog to XML. The evaluation used a set of 640 queries, with 338 distinct queries.

The paper notes that these datasets differ in schema size, complexity, data size, and organization, allowing for a broad evaluation of the system's performance.

Key Insights and Ideas

  • Automated Interface Generation is Feasible: The core idea is that a database's schema and content alone provide enough information to automatically generate a reasonably effective query interface, reducing reliance on manual design or user query logs.
  • Queriability as a Guiding Metric: The concept of "queriability" is central, providing a quantifiable way to estimate the likelihood of a schema component being used in a user query. This metric effectively prioritizes important entities, attributes, and relationships.
  • Balancing Expressivity and Simplicity: The system explicitly aims to find a trade-off between how many queries a form set can support (expressivity) and how complex or numerous the forms are (simplicity), using configurable thresholds.
  • Operator-Specific Attribute Importance: Recognizing that attributes can be used in different ways (selection, sorting, etc.), the authors introduce operator-specific queriability to better select form fields for specific query operations.
  • Human-Designed Forms Can Be Suboptimal: The comparison with a human-designed form for Monster.com highlights that even expert-designed interfaces can miss significant query opportunities, underscoring the value of an automated, systematic approach.

Key Results

  • The automatically generated forms could express 60-90% of user queries across the evaluated datasets.
  • For the Jobsquery dataset, the system's generated form supported 80% of queries, significantly outperforming a human-designed "Advanced form" from Monster.com, which supported only 31.56%.
  • The system demonstrated that even with a limited number of forms (e.g., 4-6) and attributes per form (e.g., 10-12), a high percentage of user queries could be satisfied.
  • Experiments showed that the ranking mechanism based on postulates was statistically significant, meaning the results were not due to chance.
  • Threshold variations indicated that the system is sensitive to the number of entities and attributes considered, but generally achieves good results with reasonable settings.

Limitations and Future Work

  • Complex Queries: The system currently has limitations in supporting highly complex queries, particularly those involving multiple join conditions or deep nesting, as seen in the Geoquery experiment.
  • Sensitive Data: The system may rank attributes as highly queriable that are actually sensitive or metadata and not intended for user queries. Expert guidance could help address this.
  • Threshold Selection: While the paper provides guidance, selecting optimal thresholds (ke, ka, kr, kf) for a new database without prior knowledge or user logs remains a practical challenge.
  • Future Work: The authors suggest incorporating expert guidance to refine schema annotation and identify useful query types. They also mention extending the system to handle n-ary relationships and more complex query operations. The development of a user-friendly form selection mechanism (e.g., a two-level menu) is also proposed to help users navigate a larger set of generated forms.

Summary updated

BibTeX
@article{jayapandian2008automated,
  author = {Magesh Jayapandian and H. V. Jagadish},
  title = {{Automated creation of a forms-based database query interface}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  url = {https://openreview.net/forum?id=ZA1WZix4_y},
}

Loading related content...

Figure