• CodeInHTML
  • The latest code base (November 30, 2004) is here for viewing as an HTML file.

• devcore_20041101.zip: Prototypes as of November 1, 2004
  • XAYAcoreUsageExample_20041101.doc: Example of using Relation Operations to do simple "Logic Programming" in XAYA

• devcore_20041101.zip: Prototypes as of November 1, 2004
  • XAYAcoreUsageExample_20041101.doc: Example of using Relation Operations to do simple "Logic Programming" in XAYA

• devcore_20041029.zip: Prototypes as of October 29, 2004

• devcore_20041029.zip: Prototypes as of October 29, 2004
  • XAYAcoreUsageExample_20041029.doc: Command Line Usage Example "findRootsLeaves"

XAYA is to be a Pythonic logic-based mini- language for thinking with data, and this site is to document the creation of XAYA as an extended tutorial of “Thinking with Data in Python”. Thinking with Data is a trial-and-error process of exploration of relationships amongst data (in this case “data” can mean everything from numerical observations, to semantic ontologies). One asks questions (queries), one gets answers (query result sets). Is the answer what you expected? No? Revise, and repeat. A great deal of planning, “business intelligence” and analysis work in various industries requires just such “thinking with data”, where questions become iteratively refined based on previous results. One of XAYA’s key goals is to provide a framework that can introduce Python to that business environment, and in particular to planners and analysts who are not primarily programmers, but who are required to reason with complex data and make valid inferences.

Data is everywhere, we try and make sense of it. But we keep getting caught up in the details. Here's a brief overview of the details we end up worrying about when thinking about data (as a prelude to thinking with data)

These three words summarize the spirit behind the vision for XAYA. One day, I was talking to a friend, and trying to explain the technical ideas behind XAYA. Graphs. Analysis Patterns. Declarative Languages. Yada Yada Yada. I watched his eyes begin to glaze over. Desperately, I said, "well it's really about freedom, simplicity, connection". The pupils shifted back into focus a bit. "What do you mean". Well freedom as in freedom to explore. In the limited field of data and information -- how do we give people that freedom to explore. Simplicity -- as in make it as simple as possible and no simpler. Connection as in, connecting pieces of information together -- being able to link the pieces in a chain of thought from instances to ontologies. And then it struck me. Freedom-simplicity-connection, are not technical points, but my hopes for the kind of community spirit that might grow around such a project. Who has information they need to organize? Well, businesses of course, with their enterprise information systems. Scientists with large collaborative research projects. Those are the obvious ones. But what about poets building models of simile. Visual artists organizing scraps of imagery for future transformations. Can we build a system that attracts not only software engineers, data analysts and "domain specialists", but reaches out to poets, painters, singers, dancers, recipe collectors, stamp savers, the persistently forgetful .....

To meet this vision, requires balancing very general concepts about knowledge, information and logic with specific details of query systems, data mini-language design, specific data formats ...... The goal is to balance high level and low level perspectives, and avoid collisions between those perspectives. In the end, we must hide the details from those who don't need them; and make them exposable to those who do. When the software engineering's "How" begins to struggle with the logician's "What" and the humanist's "Why Not!", perhaps it is time for poetry to intervene. Indeed, Richard Gabriel in a recent interview on the Sun site has called for an MFA in The Poetry of Programming.

To meet this vision, requires balancing very general concepts about knowledge, information and logic with specific details of query systems, data mini-language design, specific data formats ...... The goal is to balance high level and low level perspectives, and avoid collisions between those perspectives. In the end, we must hide the details from those who don't need them; and make them exposable to those who do. When the software engineering's "How" begins to struggle with the logician's "What" and the humanist's "Why Not!", perhaps it is time for poetry to intervene:

Algorithm for Collision Avoidance

the specifics and the generals

are like a flock of birds and their shadow

within the flock each bird is particular, isolate

• focussed on avoiding collision with
• its nearest neighbours

Specifics are the wings, getting you there.

Along the way, lets have some fun!

XAYA -- Thinking with Data

XAYAvision: "Freedom Simplicity Connection"

XAYAcore: "A Language for Thinking with Data"

XAYAvision

In A Nutshell. XAYA is to be a Pythonic logic-based mini- language for thinking with data, and this site is to document the creation of XAYA as an extended tutorial of “Thinking with Data in Python”. Thinking with Data is a trial-and-error process of exploration of relationships amongst data (in this case “data” can mean everything from numerical observations, to semantic ontologies). One asks questions (queries), one gets answers (query result sets). Is the answer what you expected? No? Revise, and repeat. A great deal of planning, “business intelligence” and analysis work in various industries requires just such “thinking with data”, where questions become iteratively refined based on previous results. One of XAYA’s key goals is to provide a framework that can introduce Python to that business environment, and in particular to planners and analysts who are not primarily programmers, but who are required to reason with complex data and make valid inferences.

Freedom, Simplicity, Connection. These three words summarize the spirit behind the vision for XAYA. XAYA is centred around the idea of representing information as graphs, and being able to "navigate" through those graphs. This idea originated in the insight that relational systems (such as databases) can be modelled as graphs, and a query in such a system represents a "path through a graph".

• A "miniature language" for representing and reasoning with graphs. There are many excellent graph packages in Python -- and the goal is not to re-invent them, but to focus on having a set of primitives from which we can deal with a wide range of data as graphs. In particular, we want to build up the mini-language so it can support data in many formats in a uniform way. Achieving this, sets us up for the second step. Developing models of data via Analysis Patterns.

• A template for Analysis Patterns. Analysis Patterns are models of a specific area of knowledge. A Template for analysis patterns is a fill-in template that allows you to define a model for your particular area of knowledge. In particular, you want to identify the "objects" of your knowledge, their "relationships" and their "rules". The goal is to develop a template easy enough that non-programmers can use it to model their area of expertise. Given a uniform mini-language for representing data, and a template for modelling data and it's relationships, we are ready to begin to ask questions of data.

• A query engine for "finding paths through graphs". Given a mini-language for dealing with graphs, and a template for developing models in our system, we need a way to ask increasingly sophisticated questions. At the simplest level, this means supporting "finding paths through graphs". At higher levels of sophistication, the act of ffinding paths trhough graphs gradually becomes the basis of querying, and at an even more sophisticated level, a basis for "declarative programming" which focusses on defining "what" the solution is, while allowing an automated system (the query or inference engine) to figure out how to satisfy them. For a capsule summary of declarative programming, and comparison to some other styles, go to Wikipedia

XAYAconcepts

• Representing a Model as a Graph ("thinking with graphs)
• Analysis Patterns (see "Analysis Patterns, Reusable Object Model's" by Martin Fowler, and more recent material on his website at http://www.martinfowler.com/articles.html )
• What does querying, declarative programming style, mini-language mean to programmers?

The idea of "thinking with graphs" is illustrated in:

• ThinkingWithGraphs_20041011.pdf: A visual introduction to thinking with graphs

Over the next week, I'll develop two more visual intro's to the other two topics.

XAYAcore Iteration001 Notes

XAYAPrinciples

XAYAUseCase

A minimal Use Case to begin with, illustrating a command line session:

Rough Procedure to support the Use Case

Necessary Simplifications for first Iteration

Minimal Scope Simplified Use Case

XAYASubjectDataGraphs.

XayaSubjectDataGraphsExample

XAYAFormat

Project Level

Semantics/Ontology Level

Structural level

Mapping Semantics To Structures.

Data Instance Level

XAYAPredicateFunctions.

XayaCoreSpecification

Some More Rough Algorithms

XAYAObjects

XAYALanguage

XAYAcode

Second, we have to worry about "how do we query this data?". Which query mechanism do we use? How do we formulate the query? How do we query, if the relevant data is in several data sets?

Third, it gets even more complicated. All the data we think is relevant might not be in a single database. It might not all be in a single location. How could we connect and consolidate multiple sources of data that are about "the same things".

Point one to three all concern some of the challenges of navigating through information, in search of meaning. Navigating through information is like the early days of the automobile -- where one has to be half-engineer, simply to drive. XAYA's goal is to support the idea of "just driving" and focussing on your understanding of information in a particular field (be it an area of business, science, history, etc). As such XAYA focusses on allowing you to model your knowledge, and link it to existing data, and supports exploratory reasoning about relationships amongst information, in short, "Thinking with Data". More formally, "Logic".

XAYA is to be a Pythonic logic-based mini- language for thinking with data, and to document the creation of that language as an extended tutorial of “Thinking with Data in Python”. Thinking with Data is a trial-and-error process of exploration of relationships amongst data (in this case “data” can mean everything from numerical observations, to semantic ontologies). One asks questions (queries), one gets answers (query result sets). Is the answer what you expected? No? Revise, and repeat. A great deal of planning, “business intelligence” and analysis work in various industries requires just such “thinking with data”, where questions become iteratively refined based on previous results. One of XAYA’s key goals is to provide a framework that can introduce Python to that business environment, and in particular to planners and analysts who are not primarily programmers, but who are required to reason with complex data and make valid inferences.

• A "miniature language" for representing and reasoning with graphs. There are many excellent graph packages in Python -- and the goal is not to re-invent them, but to focus on having a set of primitives from which we can deal with a wide range of data as graphs. In particular, we want to build up the mini-language so it can support data in many formats in a uniform way. Achieving this, sets us up for the second step. Developing models of data via Analysis Patterns.
• A template for Analysis Patterns. Analysis Patterns are models of a specific area of knowledge. A Template for analysis patterns is a fill-in template that allows you to define a model for your particular area of knowledge. In particular, you want to identify the "objects" of your knowledge, their "relationships" and their "rules". The goal is to develop a template easy enough that non-programmers can use it to model their area of expertise. Given a uniform mini-language for representing data, and a template for modelling data and it's relationships, we are ready to begin to ask questions of data.
• A query engine for "finding paths through graphs". Given a mini-language for dealing with graphs, and a template for developing models in our system, we need a way to ask increasingly sophisticated questions. At the simplest level, this means supporting "finding paths through graphs". At higher levels of sophistication, the act of ffinding paths trhough graphs gradually becomes the basis of querying, and at an even more sophisticated level, a basis for "declarative programming" which focusses on defining "what" the solution is, while allowing an automated system (the query or inference engine) to figure out how to satisfy them. For a capsule summary of declarative programming, and comparison to some other styles, go to Wikipedia

• Analysis Patterns (see "Analysis Patterns, Reusable Object Model's" by Martin Fowler, and more recent material on his website at http://www.martinfowler.com/articles.html )

• Based on feedback recieved from some friends after I submitted the original proposal, I did a slight revision to (i) add more discussion on Analysis Patterns and (ii) clarify the payment plan, as a cost/per/module, (ii) corrections to typos, and refining text for reading flow.
• psfgrantXAYA_ThinkingWithData_20041013.pdf: Small Revisions to PSF Proposal for Readability

Some Preliminary Concepts Explained Visually

• Representing a Model as a Graph ("thinking with graphs)
• Analysis Patterns
• What does querying, declarative programming style, mini-language mean to programmers?

The idea of "thinking with graphs" is illustrated in:

• ThinkingWithGraphs_20041011.pdf: A visual introduction to thinking with graphs

Over the next week, I'll develop two more visual intro's to the other two topics.

-- MishtuBanerjee - 13 Oct 2004

• devcore_20041011.zip: Prototypes as of October 11, 2004
  • XAYcoreUsageExample_20041006.doc: Command Line Usage Example "findAllPaths"

XAYAThinkingWithData

All trademarks and copyrights on this page are owned by their respective owners.

Comments are owned by the individual posters.

This work is licensed under the Creative Commons License -- Attribution Share Alike 2.0.

XAYAcore: "A Language for Thinking with Data"

XAYAvision: "Freedom Simplicity Connection"

XAYAvision

XAYAconcepts

Write up on October 1, 2004

GAL -- Boolean, Nested Boolean, Predicate Logic as graphs.

XAYAcore Iteration001 Notes

XAYAPrinciples

XAYAUseCase

XAYASubjectDataGraphs.

• devcore_20040826.zip: Prototypes as of August 26, 2004 -- First Iteration of XAYA Graph Data Model Process

XAYAPredicateFunctions.

XayaCoreSpecification

XAYAObjects

XAYALanguage

XAYAcode

• • XAYcoreUsageExample_20040920.doc: Command Line Usage Example "Bind"

• psfgrantXAYA_ThinkingWithData_20040930.pdf: PSF Grant Proposal: XAYA Thinking With Data

* psfgrantXAYA_ThinkingWithData_20040930.pdf: PSF Grant Proposal: XAYA Thinking With Data

XAYAThinkingWithData

XAYAcore: "A Language for Thinking with Data"

XAYAvision: "Freedom Simplicity Connection"

Return to WebHome

This site has been set up to support a Python Software Foundation grant proposal, and contains a basic description of XAYA's goals, philosophy, concepts, proposed methods, and some early code examples.

XAYAvision

A Language for thinking with data. Data is everywhere, we try and make sense of it. But we keep getting caught up in the details. Is the data in a database? Is it in XML format? Is there a DTD, a Schema? Which query mechanism do we use? Navigating through information is like the early days of the automobile -- where one has to be half-engineer, simply to drive. XAYA's goal is to support the idea of "just driving" and focussing on your understanding of information in a particular field (be it an area of business, science, history, etc). As such it supports allowing you to model your knowledge, and link it to existing data, and supports exploratory reasoning about relationships amongst information, in short, "Thinking with Data". More formally, "Logic".

Freedom, Simplicity, Connection. These three words summarize the spirit behind the vision for Xaya. Xaya is centred around the idea of representing information as graphs, and being able to "navigate" through those graphs. This idea originated in the insight that relational systems (such as databases) can be modelled as graphs, and a query in such a system represents a "path through a graph". An earlier version of this idea was inplemented in LifeLine an application that focussed on representing databases as "tree-like" graphs, and allowing the user to query a database in fairly sophisticated ways without requiring knowledge of the underlying database structure, SQL, etc. At it's centre was a query engine that translates between what the user has selected as a "scenario", a graph representation of the data, and the SQL needed to obtain the "scenario" from a relational database.

XAYA takes that basic idea "a query is a path through a graph" and generalizes it so that the query engine no longer is concerned about a particular storage format (such as relational databases, XML, RDF etc). One should focus on the information, and it's inherent relationships, rather than underlying format. In this context, we want to try and apply a set of design principles that are focussed on Logic, Abstraction, Graphs, Language. See XayaGal^? (l = logic and/or language so Graph Abstraction Logic or Graph Abstraction language).

The basic vision of Xaya is as a modular system that follows the Unix Design Principles, and Coheres to the core Modular Operators

Unix Design principles:

• Build Fns that do One thing only
• Build fns that work with each other
• "Use text streams because it is a universal interface". In our case, the uinversal interface witll be a graph-representation. This is similar to the idea that in an RDB, the uinversal interface is a table. And all operations on tables (Select, joins, constraints) themselves result in tables.

Modularity Design Principles (Modularity Operators)

1. Splitting: Breaking an interdependant module into 2 independant modules.
2. Substitution: Replacing a module with another implementation that is functionally equiavlent.
3. Subtraction : Getting rid of some modulees, without breaking the system
4. Augmentation : Adding new functionality through new modules without breaking the system.
5. Inversion : Taking a low level "hidden" modules and brining it to a higher level and making it visible.
6. Porting : Being able to move a set of modules to a new environment and have them still function

Imagine Xaya as a set of concentric circles (ripples in a pond).

• at the centre is:
  • XayaGal^? -- Graph Abstraction Logic : Design Principles and Meta Data (think Posix design priniples, TCP/IP, .... general protocols or standards)
  • XayaCore^? -- reference implementation of XayaGal^? in a particular language. In our case -- Python. Someone else could implement the equivalent in another language. or even in Python have a version that is Internally different, but equivalent in its operations.

• In the second ring, based on XayaGal^? and XayaCore^? are the specific applications
  • XayaGeo^? -- embedding XayaCore^? in OpenEV^?. Similar embedding could occur in JUMP with a Java port of XayaCore^? via Jython (or in MapServer^?, or in via HTML. Can basically build XayaGeo^? at same time as XayaCore^?, and thereby test that it is embeddable in other applications.
  • XayaApp^? -- Adding back in the GUI of LifeLine, but now in this new core. Since the new core is not restricted to Trees any longer, there will have to be some re-thinking of the GUI/UserInteractions. Target: Go from first iteration of XayaGal^?/XayaCore to XayaApp^? in 6 months (by year end).
  • Xayaflow -- Distributed Information system central to the GridAgent^? / GetSmart^? network Dave Cohen, Tyler Mitchell and I have discussed over the last year. Central concept is a distributed model of information flow. See "Information Flow: The Logic of Distributed Systems" by Barwise and Seligman; available on Amazon at http://www.amazon.ca/exec/obidos/ASIN/0521583861/qid=1090570111/sr=1-2/ref=sr_1_0_2/702-0647905-1780835
  • XayaQuest^? -- Statistical Analysis system, using search algorithms instead of convention statistics. ..... Mb's long term data analysis engine goal.
  • And so on. Other folkds will build other things from XayCore^? ....

• Finally in the third ring, there are frameworks.
  • E.g. LifeLine : combination of XayaApp^? + custom modules for processing inventory data + custom forecasting models and classification systemss + custom data models
  • E.g. The GetSmart^?/ distributed agent system with statistical learning ..... for fault tolerant networks.
  • E.g. : A GIS toolkit based on XAYA embedded in OpenEV^?. The idea Tyler and I have been discussing of the GIS data processing flow of: Storage, Manipulation and Visualization, Publishing of information. (The model applies not just to GIS -- but to other areas of analysis, like statistical visualization systems)

XAYAcore Iteration001 Notes

These notes are transcribed from mb's XAYAjournal, and will be changed as the first implementation comes into being. Right now, I'm just getting the notes down as quickly and roughly as possible, so that both Tyler and I can use them. Based on the specification, we'll both build as many functions as interest us, and compare notes. Others viewing this site are also welcome to play, and post their work here

-- MishtuBanerjee - 16 Aug 2004

Wiki: "The simplest online database that could possibly work" -- Ward Cunningham.

XAYAcore???: "The simplest relational network that could possibly work???"

XayaPrinciples^?

1. Simplest representation that could possibly work.
2. A functional programming style (while we are not Lisping, we are reasoning with data)
3. Focus on logic (and design contracts)
4. Objects if necessary -- but as few and general as possible.
5. Clear, readable, documented code
6. Use generators and iterators idioms for graph traversal (use as few and as consistent constructs as possible)The following article from Dave Mertz' "Charming Python" series provides a nice intro to these new(ish) Python features.
7. Have fun. As the 7th principle, it is of prime importance (ouch)

XAYAUseCase^?

A minimal Use Case to begin with, illustrating a command line session:

1. User provides an unordered list of selected nodes (representing data in db, ascii file, xml doc, etc)
2. User is provided with a choice of paths
3. User selects the path they want
4. Path is translated to a query in the database (initially, "database" is a simple YAML like text-file format. Later, concept of "database" expanded generically -- could be XML, ascii csv text, an OWL Ontology, relational database, etc ).

Rough Procedure to support the Use Case

1. List of unordered nodes are input to a function.
2. Function calculates path to root(s) for each node
3. List of Path is output from Function
4. Paths that are proper subsets of ofther paths are eliminated
5. If one or more of the remaining paths includes all nodes in the original list of selections, these paths are presented to user.
6. If no path incorporates all selected nodes, then user is given a warning that "Multiplication May Occur". User is allowed to select, one or more paths.
7. One user has made selection -- any common nodes from selected paths are removed.
8. The final resulting node set is translated to a query in the data source.

Note1 that we go from an unordered set of initial nodes as our input, to a list of ordered nodes as our final output (the path). I'm glossing what the translater has to do, so I can concentrate on the graph logic part.

Note2 -- in terms of graph operations, this use case is more general than LifeLine, since it is assuming acyclic graphs (forests), rather than trees.

Necessary Simplifications for first Iteration

These simplifications are to restrict the scope of the use case

1. Graphs are stored in a simple text file that imitates the Python dictionary format.
2. Restrict to single rooted forest. (two brances can still join in a leaf node)
3. Instead of an unordered list of selected notes as input, a pair of ordered nodes is submitted, representing the PathStartNode^? and the PathEndNode^?.
4. Both the keys, and the list consist of strings (i.e. don't worry about Types just yet)

These simplifications make input, output of data to/from files fairly unproblematic, and simplify the nature of the graph traversal algorithms needed to find the path. Once we've got system working with these restrictions, can then begin to loosen them, and develop more general case of graph traversal algorithms.

Minimal Scope Simplified Use Case

1. Read in a graph from an Ascii file
2. Generate a NodeIndex^? from the graph. Write it to a file as another graph in the Ascii format.
3. Given a list that is a pair of nodes: [PathStartNode, PathEndNode^?], find all paths. Write the paths as a graph where the key is a tuple (PathStartNode^?, PathEdgeNode^?) and the value is the sorted list of nodes on the path.
4. Write a Python dictionary, corresponding to our Graph model to a file.
5. For two hierarchically related graphs (say one defining measures columns, and one defining data tuples), use the index value of the list for "parent" graph to access all the values at that index for every key of the "child" graph. This approximates a simple relational query.

This is a minimal system to generate paths and "join" two graphs. Note -- there are various patterns possible between "parent" and child graphs.

1. Graphs have same key names, but their lists represent a hierarchical reln. (above example).
2. Every node in the "parent" graph is actually another graph name in the childs. (i.e. for every key in the parent, there is a graph).
3. Various other patterns, which represent all possible combinations of a 2D matrix of the following triple representing our graph interpretation of a python dictionary: GraphName^?, KeyName^?, ValueList^?.

XAYASubjectDataGraphs^?.

What Does the Graph Mean? 8 Interpretations of DictionaryAsGraphs^? to define a Knowledge Management System.

The model here is for a system that at its lowest level is data tables (whether in a db or as text files), and at its highest level is a domain model.

A node is a "Thing"

A directed edge is a non-symmetric relation between "Two Things", represented as pairs of nodes.

A directed graph is a collection "Similar Things" -- a collection of edges identified by the key of the Parent Nodes

A model is a collection of "Related Things", directed graphs -- with specified (in the model) relations between the GraphName^?, KeyName^?, ValueList^? triple in one Graph and another. Essentially, it is a collection of binary relations amongs graphs (call them edges gone meta .....).

An Object is the idea of a Thing, without implementation details (higher level than table, or XML schema structures). It has semantic definitions. And it has relations to other objects (again above the level of table/schema implementation details). The same object could be represented in multiple schema.

XAYA convention will be to name data using the prefix of its interpretation first 4-5 letters. For example: dataTblPolygons, objeStand, measTblPolygons, modelInventory

XayaSubjectDataGraphsExample^?

To make this a little less abstract, a small Forest Inventory based example has been created. The example graphs are stored in the attached file "devcore_20040826.zip" which you can download here:

• devcore_20040826.zip: First Iteration of XAYA Graph Data Model Process

Below follows an explanation of each graph, and the logical process by which we are working down from a high level Ontology to low level data models (or working up in reverse direction for that matter .... or working from the middle up and down, to be most accurate as to how it actually works in practice ... ). For those familiar with the history of data modelling that led to LifeLine ... the modelling process below can be called "Return of the Long Model" (prequel to The Database strikes back).

XAYAFormat

Data is in text files in a format that can easily be converted to Python Dictionary structures where each line of a file has the following form:

Key : Value1, Value2, Value3 .... ValueN^?

This format is similar to that used by YAML a data serialization format geared to be human readable and machine parsable, but focussed more towards dynamic languages and programming constructs than typical markup languages.

The common interpretation across all these data structures are:

• Keys represent parent nodes
• Values represent child nodes (often terminal leaf nodes).
• Thus the key-value combos, define all edges in the graph.
• It's graphs all the way down, and all the way up. (The earth is held up on the backs of turles my son. Who holds up the turtles dad? The turtles are on the backs of other turtles. You mean it's turtles all the way down? Fraid so ..... )

There will have to be fn's to inter-convert from the text format, DB tables, XML docs, Python Dictionaries. Python Dictionaries form the universal translater intermediate form for going between all other forms (ala Safe Software's appraoch to Semantic Translation). The whole thing made language independant via XML-RPC (which can handle dictionaries as structs).

Project Level

Contained in the following files:

DataFiles_X001.txt

• This file lists all files in a project, including itself.

Graphs_X001.txt

• This will be an autogenerated file which uses DataFiles^?_X001.txt to create a graph where the keys are file names, and the values are all keys in a particular file (i.e. the node list).

Semantics/Ontology Level

Contained in the following files:

Objects_X001.txt

• Keys are objects, values are attributes of the object

ObjectOntology_X001.txt

• Keys are objects and represent the "subject"
• Values are in a list of tuples (rather than simply a list)
• Each tuple represents a "predicate" (verb) , "object" pair. As in This Subject is/contains/has/pick-yer-verb Object.
• Format here is more complex: Key : (verbA, Object1), (verbB, Object2) ....

Structural level

This is the part that corresponds to traditional data modelling in databases. These files are fairly close approximations of the LifeLine long model. There are three parrallel files, which have the same key-set, but whose values are different forms of meta-data. The structural level could be said to deal with "collections" and is above the level of individual instances of data. It corresponds to Relational Modelling, as it is usually understood.

Measures_X001.txt

• Keys correspond to a text file that is a "data table".
• Values are list of columns/attributes for such a table.
• This structure would have to be modified somewhat to support XML schemas.

MeasureTypes_X001.txt

• Keys correspond to a text file that is a "data table".
• Values are list of column datatypes -- in terms of Pythons built-in types.

MeasureUnits_X001.txt

• Keys correspond to a text file that is a "data table".
• Value are units of measurement for each attribute -- m, cm, years,etc.....

DataDictionary_X001.txt

• Keys are Measures (columns/attributes)
• Values are the range of data allowed. For numeric data, its a 2 element list of min, max. For coded data, it's the list of allowable codes. For text data it is an empty list (anything goes).

Schema_X001.txt

• Corresponds to an E-R ModellingDiagram^?. Can be used to generate "JTree Tables" ala LifeLine.
• Keys are Parent Entities
• Values are their Child Entities
• I should have used the full file names -- but I used truncated versions (will have to correct).
• The model I've used is a simplification of a Forest Inventory Warehouse.

Models_X001.txt

• Key is the model name
• Values are files in the model.
• In this case, I included mainly the "structural" and data files in the model. I could have added (and probably should have) all the semantic files.

Mapping Semantics To Structures.

The object level, can be considered akin to abstract classes -- devoid of implementation. The Structural level, deals with the implementation as table, table-like structues (or alternatively in XML world, XML-like, or Schema conformant structures).

We have to map Semantics to Structures. Because any Object may have 1 one or more structural equivalents (particularly if we are integrating data from multiple databsases). So for example an object Stand may correspond to different tables with different names and different variable labels in 2 databases, but both of which describe the same "Object" (a stand) and have some common variables (Leading Species). but may otherwise differ. These mappings allow us to integrate ACROSS data sets where there is some common info.

Map_ObjectsToData_X001.txt

• Keys are the Object Names
• Values are the tables that they correspond to, or overlap with.

Map_ObjectAttributesToMeasures_X001.txt

• Keys are Object Attribute Names
• Values are the corresponding Measure names (which may or may not be the same).

Data Instance Level

The 11 graphs above are constant in form, and interpretation -- what changes is their contents -- which depend on the actual data (instances) being modelled at a low level). One could say instance information flows through the Structural and Semantic levels, which do not change in form.

In this case, our low level data a model of the forest inventory, corresponding to the schema in Schema_X001.txt. There can be any number of tables in the low level model. Every table has the same interpretation:

Key : Value1, Value2, .... ValueN^?

• Where the Key represents a primary key for the data
• Where the Values correspond to a tuple of data values (observations) associated with the key.

In our model we have the following tables:

• datStandStructues_X001.txt -- List of Stand Structures from a classification of forest stand types
• datPolygons_X001.txt -- Data about Polygons (roughly correspond to "Stands")
• datPlots_X001.txt -- Data about Plots
• datProtocols_X001.txt -- Data about the protocols used lay out plots.
• datPlotStructures_X001 -- List of Plot structures from a plot-based classification of forest stand types.
• datTrees_X001.txt -- List of Trees that have been measured in Plots.
• __datMeasurements_X001.txt -- Repeated Measurements on the Trees over Time.

And there you have it, a single data graph data structure taking us all the way from high-level ontologies to low level data; and which is sufficiently flexible to map to ascii data files, XML, Relational Database Tables, and which can be passed across programming languages via the XML-RPC protocol.

One Graph to Rule them All.

XAYAPredicateFunctions^?.

Functions that tell you something about a graph, a node, an edge. Currently there are twelve functions. If some of the functions can be defined in terms of others, we can reduce this list to a set of axiomatic functions.

• trans (transforms one data structure to another e.g. an ascii file to a python )dictionary)

• • read (e.g. into a dictionary)

• • write (e.g. into a file or into a db)

• • • print (write to terminal)

• is (a root node, a leaf node, a parent node, a child node, etc)

• get (a root node, a leaf node, a parent node, a child node, etc)

• bind (graph one to graph two based on some relation. Note -- wanted to avoid the word join -- since bind may not correspond to relational join, depending on how its working)
  • What relations are possible between two graphs? Each graph can be represent by 3 sets of information. (1) It's name (scalar). (2) It's key's (collection bound to the name). (3) It's values (collections, each collection bound to a key). So between any two graphs, there is a 3 * 3 matrix of possible bindings (some of which are more common patterns ... other's of which are less common).
    • Pattern 1: BindByValues^?. Values of Graph1 (say Measures) bind to specific balues of Graph2 (say the data) So, measure3 is used to pick up all the data at position 3. This is basically similar to how columns work with data tuples in an RDB.
    • Pattern2: BindKeyToNames^?. The keys A to Z in Graph1 each are bound to the names of a collection of graphs GraphA^? ..... GraphZ^?.
    • Pattern 3: BindValuesToKeys^?: The values for a Key in Graph 1, bind to keys in Graph 2. For example, say graph 1's keys correspond to Relational Data models, with it's values being all the tables in a model. Graph 2, could then be the schema of Tables in a given model, and it's key's corresponding to individual tables. Such a pattern could be used to allow linking data across multiple models, say via a higher order Business Object model.
    • Pattern 4: BindKeysToValues^? : Say Graph 1 and Graph 2 are data tables with a parent-child relationship. The primary key of graph 1, is it's key. The values of this key, are also represented in Graph2's values, at a particular position in the value list. The BindKeysToValues^? is like a Parent-To-Child join between the graph representations of these two tables.
    • Other Patterns. Basically follow from the following Matrix Graph1(Name,Key,Value), Graph2(Name, Key, Value). I.e. 9 possible bindings. For the most part, we are interested in hierarchical relationships, where in some sense one graph is a parent of another. That is, there is a 1-to-1 or 1-to-many reln amongst the graphs.

• split (a path, graph, model into full subsets based on conditions e.g split a graph into subsets using the following criteria to define which subset if falls into)

• filter (a path, graph, model into partial subsets based on conditions -- e.g. filter a graph so only the selected nodes remain; filter may simply be a special case of split, followed by kill)

• make (a node, an edge, a graph ....)

• kill (a node, an edge, a graph ....)

• gen (a function mapping inputs to outputs, e.g. genNodeIndex takes a graph of node names (keys) and node lists (values) and maps it to a set of character separated integer strings (for both keys and values).

• sum (takes a sequence of values and returns a scalar -- e.g. sum([pathlist])

The functions once built, can also be made available in a non-language specific way via XML-RPC. In this context there would be an XML-RPC Xaya Client focussed on read/write functions of local info, and an XML-RPC Xaya Server which handles most other functions including any read/write on the server. If you fully enable both client and server, have beginnings of a peer-to-peer framework.

Subject Data Graphs + Predicate Functions = A Little Domain Specific Language Implemented as Graphs

Using the 8-fold model above, that Domain Specific Language represents a knowledge base (which in turn is defined by the actual data in each of the graphs), spanning low level data, to high level semantics. However, other sets of graphs and operations could be defined. For example Graph structures are used to parse simple languages. See Compiling Little Languages in Python by John Aycock for an example.

So, essentially, any give model of graphs -- represents a general problem domain (the 8-fold GraphInterpretationPattern^? being the path of Knowledge Representation .... if not actually wisdom)

In addition to the general functions defined above, additional domain specific functions may be defined, using the general functions as their components. So, we are building "from the bottom up" several layers of language. For more on this, see the general article by Paul Graham on Programming Bottom Up

XayaCoreSpecification^?

Finally ..... The XAYA001 specification

1. readFromFile(FilePathOrName^?) -- reads from ascii format either a graph or a path (a path is simply a 1 row dictionary with a key and a value list)

2. genNodeIndex(GraphName^?)

3. findAllPaths(GraphName^?, StartNode^?, EndNode^?)

4. filterShortestPaths([PathsList]) -- a list of lists is the PathsList^?

5. filterLongestPaths ([PathsList])

6. sumPathLength([Path])

7. findRoots(GraphName^?,[NodeList])

8. isRoot(GraphName^?, NodeKey^?)

9. writeToFile(GraphOrPathName^?, FilePathOrName^?)

10. filterGraph(GraphName^?, [NodeList])

11. bindGraphs(ParentGraph^?, ChildGraph^?) -- may require either several fns -- or a single fn with a longer list, to define differnet ways of binding two graphs. I always imagine this as the weigh proteins bind.

12. makeNode(GraphName^?, NodeName^?)

13. makeEdge(GraphName^?, ParentNode^?, ChildNode^?)

14. killNode(GraphName^?, NodeName^?)

15. killEdge(graphName, NodeName^?)

Some More Rough Algorithms

.... To be continued, as the implementation is worked out.

General Tree Walking Algorithm For each NodeKey^?, walk through it's edges. Build a list from nodes to edges. Each edge then recursively becomes a node key. Continue until: have hit a leaf node, or encounter a node already in the list (i.e. a cycle). Make sure you follow alternate branches, and don't just end up running down one branch.

Node Index Generation To generate an index such as 1.1, 1.2.1, etc, defining node locations in the graph. Once such an index is generated -- operations on it, can be easier than full graph-walking algorithms (which don't make any assumptions about the graph's structure. In particular, regular expressions on the lists of node indexes can be used to find the paths.

XAYAObjects

Currently in the first iteration there are no "official" objects. Though obviously we are using some object oriented/relational hybrid thinking in our modelling approach. Ultimately, we may create an object such as DiGraph^?(dict), inheriting from the built-in dictionary type. This is a bit different than some other approaches which usually proceed by defining node, edge classes, and several types of graphs: graph, digraph, tree. This leads to a menagery of Graph related objects.

I'm thinking of something much simpler. A single base class (DiGraph^?). Essentially extends the basic capabilities of a dictionary. Their may also need to be a containeer class, for operations "across graphs" rather than operations within a graph.

Focussing on DiGraph^?, we can further sub-class, and actually represent nodes, and edges, as themselves inheriting from the DiGraph^? class:

DiNode^?(DiGraph^?) has a name, that is the node's name. It's keys represent data associated with the node ("cargo") and the values are the values of the data.

DiEdge^?(DiGraph^?) has a name, that is the string-representation of two-nodes (e.g "A-->B), and whose values are the tuple (Parent, Child).

With just these constructs one should be able to build fairly complex models, including ones where a single node in one model, may itself contain a whole other model. Consider this for cases where different models exist at different scales, or where one has nested models.

The current functions then become methods within this class. And subclassing can over-ride what they do, and add further methods.

XAYALanguage

So far, we've defined the mini-language as a library in Python (i.e. we're using Python itself as a little language, in the manner illustrated in the Python Cookbook, pg 449, which also contains yet another graph implementation example). The next step, is to go further and actually extend the Python language. The notes here are some very preliminary ideas as to what such an extended language might look like.

Can we, based on the constructs we've created, define a simple extension to the Python core language, to represent Graph operations -- a type of relationally modelled path language. (call it XayaPath^?). If we could, it would allow Python to add to it's current functional and OO styles of programming, the declarative style of a logic/relational language.

I've got some rough notes in my Xaya journal right now, that I have to try out.

Without referring to the notes (scattered over several pages of journals, and in the backs of several other pieces of paper) here's the general sketch of the idea.

Define a declarative style language that defines a path , using keywords, operators, tokens not currently used by Python (i.e. this language + Python is a superset of Python). As in any declarative language, it states "what is wanted", not "how it is calculated" (done by the underlying system, in this case the query engine functionality)

Say there are 2 graphs, G1 and G2 (represented by perhaps the DiGraph^? class).

Notation Thoughts (very rough)

• | | Indicates beginning and end of a path statement within a graph. (Intra-Path)

• || || Indicates beginning and end of a path statement across graphs. (Inter-Path)

• |{ Names }|

• |( keys )|

• |[ Values ]|

• |{G1} (Key1 : KeyN^?)[Var5,Var6,Var7] | Filters Graph 1 for Keys 1 to N and Projects Values 5,6,7 only. In SQL terms, I just said something like "SELECT Var5, Var6, Var7 FROM G1 WHERE (Keys < (N + 1))" The "path statement" used app 27 characters, where the SQL form used app 40. One could see how, if the source data was stored in an RDB, the path statement could directly translate to an SQL query. Similar could be likely developed if the data storage source was an XML document.

• --> Bind Operator

• || "Some Set of InterGraph^? Operations Placed Here" || Specifies chained graph operations

• || {G1}| --> |{G2}|, ByValues^?) || -- Bind Graph G1 to Graph G2 by Values.

• || {G1} (Key1 : KeyN^?)[Var1 : Var4] --> {G2}( : )[Var5, Var6], ByValues^? || Which says something like "SELECT G1.Var1, G1.Var2, G1.Var3, G1.Var4, G2.Var5, G2.Var6 FROM G1, G2 Where (G1.Keys = G2.Keys) AND (G2.Keys < (N+1)". Note in this case, the number of tokens from the path statement vs the SQL-like equivalent are roughly: 58 vs 100.

• >>> If len(|| {G1} (Key1 : KeyN^?)[Var1 : Var4] --> {G2}( : )[Var5, Var6], ByValues^? ||): "You Have Data"
  • Finally, you should be able to mix "path statements" with regular Python. (More "readable" if the path statement was first bound to a variable name such as >>> myPath = || {G1} (Key1 : KeyN^?)[Var1 : Var4] --> {G2}( : )[Var5, Var6], ByValues^? ||) )
    • which leads to >>> If len(myPath) : "You have data"

Admittedly the paths are a bit cryptic -- but this demonstrates they can be "expanded out" into SQL-like, Xpath-like, X-Query-like statments by path-translator functions. This allows a common internal representation of paths, that can then get executed amongst heterogenous data sources.

Someone with a better eye for readability, should see if there's alternative symbol sets that are both consise, and easy to read. Also, it's important that there be no ambiguity in the interpretation (which currently there might be).

Our thoughts here, are really expressing "paths" in terms of 3 operations. Intersections amongst sets represented by graphs via "-->"; constraints via "(keys list)" and projection via "[variables list]". So, every path is some combination of intersection of sets (including itself), constraints on a set, and projection of set attributes. In short, if you can represent collections of data as sets, this language should be able to operate on those sets in a consistent manner. In terms of the transition from "low level data" to "high level semantics/ontologies", what one is doing is really building a hierarchical model that across sets provides the connecdtions between the high level (say the ontology) and the low level (the actual data, in it's native storage format).

Somewhere behind all this is the idea that Lisp notation reflects the actual parse trees of the language. And I'm imagining something similar in Python for these path statements. Of course, I'm really not sure how Lisp parse trees work so, the analagy might be spurious :-{

XAYAcode

These are some initial code, developed to illustrate ideas for XAYA in its initial iteration. These should not be taken as the final code, for the first iteration, but really a working out of code conventions and initial command line interface via proto-typing. Expect the code to be updated every few days. Top link, is most recent version of code (so one gets a running view of the developing style). Current conventions are to use a test-first development style (define unit tests, write code)via unittest module, a pseudo-literate coding style that provides documentation of any algorithms used, and references to code sources, and finally incorporation of usage examples via docTest module. Code is currently more verbose than it needs to be, and will get stripped down. Try and balance conciseness and clarity. (emphasis on "try").

• devcore_20040921.zip: Prototypes as of September 21, 2004

• devcore_20040914.zip: Prototypes as of September 14, 2004

• devcore_20040826.zip: Prototypes as of August 26, 2004

Original -- MishtuBanerjee - 16 Aug 2004

Revised -- MishtuBanerjee - 30 Sep 2004