Property Driven Data Bases

PROPERTY DRIVEN DATA BASES

Jean Paul BARTHES, Michel VAYSSADE, and Monika MIACZYNSKA'~ Department of Applied Mathematics and Computer Science University of Technology of Compiegne 60206 Compiegne Cedex, France

In this paper we suggest how, focusing on the concept of property, one can use a very small number of operators (functions) to organize a factual data base whose information structures are constructed as simple association lists. The approach was used to design and implement a data base management system, operating in a small-core/slow-secondary-storage environnment, as a part of a low cost multimicroprocessor robot system,

I · INTRODUCTION

The A.I. community has developped efficient tech­ niques for in core handling of symbolic know­ ledge representation. On the other hand com­ mercial data bases use extensively secondary storage, but for various reasons suffer from very rigid data structures. Roth sides have proposed abstract representation models with the hope to find an efficient solution [1,2,3,4] However difficulties still subsist when one has to actually implement the models, in parti­ cular when secondary storage is involved. Our recent work aimed at building a low cost multi­ microprocessor robot system led us to address this problem in a small-core/large-but-slow secondary storage environnment. Our objective was to implement a data base using a 16 bit microprocessor. We then reconsidered the simple property value representation which proved to be surprisingly powerful. Indeed it is possible to build easily a data base management system as an. interpretor of a set of properties, each being described in turn as a property - value list (introducing readily a metalevel of description). Then, while processing data, the presence of any given property in the data stream can trigger associated functions, which renders the overall approach somewhat analogous to a production rule system. Hence the name of Property Driven Data Base.

The main characteristics of our approach are

- no distinction between physical and logical

·'·This work was supported in part by CNRS under ATP granted by the Committee for Indus­ trial Robotics and by the University of Techno­ logy of Compiegne.

models, which avoids the so-called "data inde­ pendence" problem plaguing most commercial sys­ tems [6].

• no a priori information (or object) classes ; each entity stands for itself. It is represented as a property list and possesses an internal name. The representation is very similar to the one found in Abrial [1}.
• operators imbedding semantic meaning are at­ tached to properties.
• relational information is implemented at pro­ perty level.
• access to the data base is done through speci­ fic entry points unlike in Me Dermott (4].
• privacy and user classes are dealt with using the notion of model and related access paths.
• access paths are computed dynamically.

2, DATA BASE MODEL

2.1 Static View of the Data Structure

It is built from 3 distinct ensembles, E, the entity ~or set of objects, P, the property !!! or set of attributes, and V, the ~ !!!· It must be noticed that we do not cons1der any "relation set". Relations an implemented via the property set which accordingly is parti­ tioned into 2 subsets, T, the terminal property set, and S, the structural property !!!· with P · T u S. To each entity ei of E is associated a subset Pi · Ti u Si of P. To each property tj of Ti we associated a subset Vij of V. To every property sj of Si we associate a subset Eij of E. Hence tj describes local attributes of ei, whereas sj gives the connections of ei with othet entities (equivalently the relations). Furthermore for each entity ]Pii·ISil + ITil may be different and depends solely 011 what ~s known about e. <lxl denotes the cardinality of X). 1

Elementary Operations: Three basic operators are needed:

- n associating each enti~y to its_correspond­ ing properties: n : E ~ P (where P denotes the power set of P)

- T yielding the values associated to a termi­ nal property t . of e. (a restricted case of the LISP function eET): 1 T : ExT~ V

- y yielding all entities linked ~o ei (a differ­ ent use of GET \: y : Ex S ~ E

Additional Definitions:

A .. . If " f §~~~~!!2!: n ent1ty ek 1s a successor o a given entity e. if ekE y(s,e.). 1 1

~!~~~~~!!2!: A "predecessor" ek of ei is an en­ tity for which e. is a successor. 1

~~~~!!-~~~-~~~!I-~2!!= Every entity having no predecessor is called an access of the data base.

The data base, G, will be said to be normalized if all accesses are made the successor of a sin­ gle entity e which thus becomes the only access of G. --()

However e could be linked to other ent1t1es in G. All s8ccessors of e will be called entry-. d 0 ports, abbrev1ate ports.

. 2.2 Exploring Mechanisms

Information can be obtained incrementally from any given location in the data base without any a priori knowledge of its organization, simply usiag operators n, T, y. In particular from a statical point of view it is possible to obtain full information solely from the elements (e , n, T, y) e being the data base access. This p8ssi­ bility 0 should be reserved to the data base manager, normal users being excluded.

2.3 Modifying the Data Base

veleting Information: Deleting values or links at the entity level is straightforward. However deleting an entity requires updating of all its predecessors.

Adding Information: is a much more interesting operation. Indeed the overall structure of the data base must remain consistent. It is con­ venient to ass.ociate to each terminal property t . of P a screening operator ~. such that for aJy external value W: J

In practice the corresponding function carries on such tasks as validity checks and external/ internal format translation. This permits to associate a specific data type to any given property, and to support easily heterogeneous collections of data.

Retrieving Information : Let us consider a sub­ set E. od E, a property p. of P and an external set o! values W consistent with P., i.e. such that ~.(W) + ~. One can define orte or more se­ lectiort operators w. associated with p., extrac­ ting from E. all elJments satisfying aJgiven criterium;_ 1 w. (E. ,W) · E c E. (w. is a mapping w. : E x w~ EJ) . 1 The invol~edJcriterium can be rJpresented by a Boolean function 8., e.g. J

The selection operator w. is similar to Lind­ green's detection operatJr [~J but is not con­ strained to "HIS" (Homogeneous Information Classes). More will be said concerning its im­ plementation.

2.4 Accessing Structures

Map and Models: A large data base especially in A.I. type of applications may contain many chunks of information stored in a very disorder­ ly fashion. Whenever secondary storage is used it is necessary to minimize the number of acces­ ses. We introduce to this purpose the notion of map and models. In addition to increasing access efficiency they permit to solve neatly some of the problems related to privacy and user's view of the data base. An interesting feature of such models is the possibility to construct them ~ posteriori using pattern recog­ nition techniques. In order to define them we need some additional concepts.

Following Property: Property P will be said to be following a property P. assgciated with en­ tity e., if e is a succes~or of e. and P En(e), 1 1 n

We can define mapping fa such that f : S ~ P and extend it over the set of properties r:: : P ~ P. a

Map: It is the graph Ga m (P,f~) connecting properties.

Model: A model is any subgraph of the map. A model implements a user's view of the data base.

Exploring Using Criteria: Let E. a subset of E be named a position. Let X be ln operator which when applied to E; will yield a subset Eq derived from a given property pk and a given model Mn: n ~ X(E.,pk,M) = E where x:E X p X M ~ E ~ q E is the set of entities that can be reached f~om E. by using some existing path in Mn lead­ ing to~a property pk. Access paths are dynami­ cally computed in a model.

Clearly some entities in the data base having property pk will not be reached, even from e , if ther~ are no existing paths in the given ° model M . Furthermore if, instead of Mn, one considers subgraphs of i", access to entities will be further restricted. For example if E. is a set of entities each one having property p~, one can easily obtain all entities having both properties p. and pk by applying X(E.,pk,{pk}). An analogousJresult can be obtained from any po­ sition E. using X(X(E.,p.,Mn),pk,{pk}). ~ ~ J

Associative Access: It is then possible to com­ bine X with previously defined selection opera­ tors. Using a screening operator (or filter) w. associated with a property p. one can distingulsh 2 ways of filtering information:

• -cumulative filtering E 2 w.(~(E.,Wk),W.) yielding all entities fr3m po~it~on~E. satisfying 2 (or possibly more) criteria associa!ed with one (or more)properties.

-repetitive filtering E · w.(X(E.,p.,Mn),W.) yielding all entities tha~ canJbe r~ac~ed fro~ position E. according to the model Mn and that satisfy cr~teria implemented by w .. Obviously such filtering can be applied recdrsively.

Classes of Users, each having various access privileges, can be defined by means of domains: D' ~ (M ,P ,0 ,Z ) including a set of models M , auset o¥ p¥op~rt¥es P , associated filters 0 u and screening operato¥s Z u u

3. IMPLEMENTATION AND DISCUSSION

An implementation was done at the UTC on a PDP II. The host language is a shallow binding LISP dia­ lect, functions were developed allowing to store and to access directly variable length character strings identified by variable length keys, se­ quential access was added to the LISP I/0 sub­ system for reading bulk data and for producing printed forms. The volume of object code limited us to 5000 list cells and 1250 atom hash cells. This realizes in effect a small processing win­ dow over the data base held in secondary storage. An additional primitive for reclaiming atom s~e had to be developed for dealing with the clogging of the hash table.

Data is structured as association lists. Entities linked by structural properties are reversely chained. Ports are implemented via the hash table. Operators are implemented as LISP functix5

A present restriction in our approach is the lack of possible deduction when the search fails. How­ ever the general structure makes it rather straight-forward to introcuce "advising functions" at the property level. Furthermore screening operators could be implemented as microprograms to be loaded into "stream processors" to take full advantage of the recent developpments in secondary storage architecture [6]. on· the other hand, although path access leads to iterative retrieval of entity subsets, it offers a solution to the erivacy problem and to the implementation of spec~fic user's view of the data base.