On Implementing SchemaLog - A Database Programming Language

Alanoly Andrews, Nematollaah Shiri, Laks V. S. Lakshmanan, Iyer N. SubramanianCIKM 1996 · DOI

TL;DR

This paper presents a practical implementation of SchemaLog, a logic programming language designed for advanced database operations. By compiling SchemaLog into an extended relational algebra and exploring efficient storage architectures, the authors demonstrate a viable approach to handling complex data querying and restructuring tasks within a single database context.

What Problem Does This Paper Address?

Traditional database query languages, while powerful for data retrieval, often fall short when it comes to manipulating the database schema itself or performing complex restructuring operations. Logic programming languages, on the other hand, excel at expressing complex rules and transformations but can be inefficient for large-scale data management. SchemaLog aims to bridge this gap by offering a logic-based language with a first-order semantics that can handle both data and meta-data (schema) querying and restructuring. The challenge addressed here is how to efficiently implement such a powerful language within a practical database system, moving beyond theoretical foundations to a working prototype.

Methods

The core of the implementation strategy involves compiling SchemaLog constructs into an extended relational algebra called Schema Algebra (SA). This SA includes standard relational algebra operators and introduces new ones specifically designed to query and manipulate both data and schema information. The authors then develop a top-down algorithm for evaluating SchemaLog programs based on this algebra.

A significant contribution is the exploration of three different physical storage architectures for implementing these SA operators:

  1. Conventional Storage: Standard database storage, efficient for traditional querying but less so for meta-data operations.
  2. Reduced Storage: A "flattened" representation of relations into three core relations, aiming to simplify meta-data querying by reducing it to conventional data querying.
  3. Reduced, Atomized Storage: Further atomization where each attribute of a relation is stored in its own physical relation, potentially offering the best performance for meta-data operations and restructuring.

The paper details algorithms for implementing SA operators under each storage strategy and discusses their trade-offs.

Datasets

The paper uses a running example based on the New York Stock Exchange database, with data available at http://www.ai.mit.edu/stocks.html. This dataset is used to illustrate the concepts and for experimental evaluation. No new benchmarks were introduced; instead, existing data was used to test the performance of the implemented strategies.

Key Insights and Ideas

  • Schema as First-Class Citizen: SchemaLog's strength lies in treating schema information (relation names, attributes) with the same importance as data, enabling powerful meta-data querying and restructuring.
  • Bridging Logic and Databases: The compilation into an extended relational algebra is key to leveraging efficient set-oriented database processing for logic programming constructs.
  • Storage Architecture Matters: The choice of storage significantly impacts performance, especially for the mix of querying and restructuring operations inherent in SchemaLog. Conventional storage excels at pure querying, while reduced storage strategies become more advantageous as restructuring needs increase.
  • Decoupling Querying and Restructuring: The top-down evaluation algorithm effectively separates the querying aspects (handled by SA type 2 operators) from the restructuring aspects (handled by SA type 3 operators), simplifying implementation.

Key Results

Experiments were conducted on a Microsoft Access DBMS. The results indicate:

  • Individual Operations: Conventional storage (S1) is superior for purely querying operations.
  • Mix of Operations: As the proportion of restructuring operations increases, conventional storage becomes significantly slower, while the reduced storage strategy (S2) maintains a more constant cost. For applications dominated by restructuring, the reduced strategy is preferred.
  • Recommendation: A hybrid approach is recommended: conventional storage for base relations and reduced storage for derived relations.

Limitations and Future Work

  • Implementation Scope: The implementation was done on Microsoft Access on Windows 3.1, which might not reflect performance on more modern or powerful database systems.
  • Full SchemaLog: The paper focuses on a fragment of SchemaLog for a single database context, and the full language's capabilities might require further investigation.
  • Future Work: The authors mention a prototype platform for interoperability among multiple INGRES databases based on a fragment of SchemaLog and a standalone implementation of SchemaLog is in progress. They also suggest that the findings are relevant to emerging applications like OLAP, which involve significant restructuring.

Summary updated

BibTeX
@inproceedings{andrews1996implementing,
  author = {Alanoly Andrews and Nematollaah Shiri and Laks V. S. Lakshmanan and Iyer N. Subramanian},
  title = {{On Implementing SchemaLog - A Database Programming Language}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {1996},
  doi = {10.1145/238355.238565},
}

Loading related content...

Figure