Formal Verification of Semistructured Data Models in PVS

Scott Uk-Jin Lee, Gillian Dobbie, Jing Sun, Lindsay GrovesJ. Univers. Comput. sci 2009 · DOI

TL;DR

This paper introduces a formal method for verifying the correctness of semistructured data models, specifically the ORA-SS language, using the PVS theorem prover. By formally defining the semantics of ORA-SS schemas and data instances, the authors enable automated verification, ensuring data consistency and correctness, which is crucial for the growing use of semistructured data on the web.

What Problem Does This Paper Address?

The explosive growth of the World Wide Web has led to a massive increase in the use of semistructured data for information exchange. Ensuring the correctness and consistency of this data is paramount, especially for critical applications like financial transactions or confidential information. Traditional database systems rely on schemas and normalization to maintain data integrity. However, semistructured data, often represented in formats like XML, presents unique challenges. While various data modeling languages exist for semistructured data, a formal and automated way to verify the correctness of their schemas and data instances has been lacking. This paper addresses this gap by providing a formal specification of the ORA-SS data modeling language and demonstrating its verification using the PVS theorem prover.

Methods

The core of this work lies in the formal specification of the ORA-SS data modeling language and its semantics using the Prototype Verification System (PVS). The authors define three key PVS theories:

  1. ORA-SS Schema Theory: This theory formally defines the structure and semantics of ORA-SS schemas, including object classes, relationship types, attributes (object, relationship, composite, disjunctive), and keys (candidate and primary). This is achieved by defining PVS types that capture the components and constraints of an ORA-SS schema diagram.
  2. ORA-SS Data Instance Theory: This theory provides an abstract representation of semistructured data instances (like XML documents) within PVS. It defines types for object relationships, attribute instances, and composite/disjunctive attribute instances, ensuring they conform to the schema's structure.
  3. Relating ORA-SS Schemas and Data Instances Theory: This theory defines the mappings between schema and data instance definitions. It specifies how relationship instances, attribute instances, and candidate key instances in the data should correspond to their schema definitions, enabling validation.

The authors then use PVS's type checker and theorem prover to verify these formal specifications. This process involves proving Type Correctness Conditions (TCCs) for the defined types and then proving conjectures that represent the overall correctness of the schema and the validation of data against the schema.

Datasets

Not discussed in the paper. The paper uses a "Course-Student" example schema and a corresponding XML data instance to illustrate its methodology, but these are not presented as formal datasets for evaluation.

Key Insights and Ideas

  • Formal Semantics are Crucial: The paper strongly advocates for formalizing data modeling language semantics as the foundation for automated verification. This moves beyond informal descriptions or graphical representations.
  • PVS as a Powerful Tool: The choice of PVS is justified by its ability to handle complex type constraints and its integrated theorem prover, making it suitable for verifying intricate data models.
  • ORA-SS's Richness: The authors highlight that ORA-SS, with its support for ternary/n-ary relationships, disjunctive attributes, and relationship attributes, captures richer semantics than simpler models like DTDs or XML Schema, enabling deeper verification.
  • Automated Verification Benefits: The work demonstrates that automated verification can detect semantic errors in schemas and inconsistencies in data instances that might be missed through manual inspection, especially in complex models.
  • Schema-Data Consistency is Verifiable: The paper shows that it's possible to formally define and verify the relationship between a schema and its data instances, ensuring that data conforms to the intended structure and constraints.

Key Results

The paper successfully demonstrates the formal specification of ORA-SS semantics in PVS, covering schemas, data instances, and their mappings. Through the "Course-Student" example, they show how PVS can:

  • Detect Schema Errors: The authors deliberately introduce three semantic errors into the "Course-Student" schema diagram. PVS's type checking and theorem proving successfully identify these errors, such as incorrect relationship degrees and duplicate primary keys.
  • Validate Data Instances: They also demonstrate how the XML data instance for "Course-Student" is validated against the (corrected) schema. PVS identifies inconsistencies like incorrect participation constraints in relationships and non-unique candidate key values in the data.
  • Enable Automated Verification: The work provides a framework where complex ORA-SS schemas and data instances can be automatically verified, reducing the manual effort and potential for human error.

Limitations and Future Work

Limitations:

  • Subset of ORA-SS: The formal semantics presented in the paper are limited to a subset of the ORA-SS data model to manage space constraints. A complete semantics is available online.
  • Interactive Proofs: While PVS automates much of the process, some complex type constraints and conjectures may still require interactive proof steps using predefined theorems and lemmas.

Future Work:

  • Schema Transformation Verification: The authors plan to extend their work to formally specify and verify schema transformation algorithms (like normalization and view creation) and their operators. This would ensure that transformations preserve data consistency.
  • Extended ORA-SS Semantics: They intend to define and verify an extended PVS semantics for ORA-SS to model more complex aspects of semistructured data design, particularly for normalization processes.
  • Comparison of Transformation Algorithms: By formally defining and verifying transformation operators, they aim to compare different algorithms for specific contexts.

Summary updated

BibTeX
@article{lee2009formal,
  author = {Scott Uk-Jin Lee and Gillian Dobbie and Jing Sun and Lindsay Groves},
  title = {{Formal Verification of Semistructured Data Models in PVS}},
  journal = {J. Univers. Comput. sci},
  year = {2009},
  doi = {10.3217/jucs-015-01-0241},
}
Figure