Project title

Implementation of an informational equivalence and typing for unstructured Web-like databases via bisimulation and simulation relations

Supervisor

Vladimir Sazonov, Logic and Computations Group,
http://www.csc.liv.ac.uk/research/logics/

Subject Areas

Logic, set theory and corresponding foundations of database theory.

Brief description

The goal of this Project is to implement simulation and bisimulation relations for unstructured, Web-like databases, WDB [1,6,7,5]. The latter are represented in terms of graphs with labelled edges (called also labelled transition systems; labels currying the database information) considered up to bisimulation. Bisimulation corresponds to ``deep'' informational equivalence of WDBs and simulation allows to determine whether database satisfies a given type (schema).

To implement (bi)simulation and to demonstrate how the implementation works a student should represent WDB in terms of hyper-linked Web-pages (-- files in the format of a simplest fragment of html) where hyper-links are labelled by strings of symbols ``click-able'' by mouse and give several instructive examples of WDB states. A database schemas may be presented in the same way as graphs of simpler form. The bisimulation algorithms should work with URLs of any two pages.

First, a simplest algorithms should be implemented based on the first principles, i.e. based on the fact that bisimulation and simulations relations are largest fixed points of corresponding operators and may be computed iteratively.

Second, as an additional more difficult task¹, (bi)simulation may be implemented on the base of more advanced, faster algorithms developed in [4,2,3]. Then the resulting implementation may be compared -- an instructive enterprise.

Note, that considering graphs (with distinguished, ``title'' vertices) up to bisimulation allows to consider their vertices as denoting so called hyper-sets. Therefore this work will be actually done in the framework of (hyper) set-theoretic approach to (unstructured, Web-like) databases. For a student working on this project this would be a good opportunity to apply his/her programming skills and to learn new ideas on unstructured databases -- a fresh and promising direction of research.

Thus, the concrete goal of implementation consists in automated checking bisimulation and simulation relation for graphs represented in the form of a system of hyper-linked WDB-pages. In particular, an appropriate interface should be designed.

Background requirements

Familiarity with elements of logic, simplest set-theoretic concepts, very general ideas on databases and having sufficiently advanced programming skills and, possibly, theoretical inclinations.

Bibliography

1

S. Abiteboul, P. Buneman and D. Suciu, Data on the Web; From Relations to Semistructured Data and XML, Morgan Kaufmann Publishers, 2000.

2

A. Dovier, C. Piazza and A. Policriti, Fast (Hyper) Set Equivalence, DPS99, Workshop on Declarative Programming with Sets, in conjunction with PLI99, Paris, France, 28 September 1999.

3

A. Dovier, C. Piazza and A. Policriti, A Fast Bisimulation Algorithm (Fast (Hyper) Set Equivalence), Technical Report UDMI/14/00/RR.

4

R. Paige and R. Tarjan, Three partition algorithms, SIAM J. Comput. 16(6), 1987, 973-989

5

Lisitsa, A., and Sazonov, V., Bounded Hyper-set Theory and Web-like Data Bases. Computational Logic and Proof Theory, 5th Kurt Gödel Colloquium, KGC'97, Springer LNCS Vol. 1289, 1997, pp. 172-185.

6

Sazonov, V.Yu.: 1993, `Hereditarily-finite sets, data bases and polynomial-time computability', Theoretical Computer Science Vol. 119, Elsevier, pp. 187-214.

7

Sazonov, V., On Bounded Set Theory. Invited talk on the 10th International Congress on Logic, Methodology and Philosophy of Sciences, in Volume I: Logic and Scientific Method, Kluwer Academic Publishers, 1997, pp. 85-103

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -no_navigation -split 1 -address V.Sazonov@csc.liv.ac.uk bisimul.tex

The translation was initiated by Vladimir Sazonov on 2001-05-01