[GRASS5] Multiple attribute support in GRASS 5.1: some considerations (long) [Andrea Aime] During the last days I've spent some time thinking about new vector capabilities in GRASS 5.1, and in particular for what concerns multiple attribute support and DBMS integration. I would like to share my thougths with you. Please forgive my english, I'm not used to write such a long text and I don't have enogh time to consult a dictionary and a grammar :-) [Radim] Have you read grass51/doc/vector/vector.html? Probably not, so I would recomend you to look at it because some related proposals are there and some experimental code is written in grass51 (g51). For example d.vect with where= (SQL where) is already working. [Radim] In general I agree with your ideas, only few comments. In my opinion we should thinks first about what kind of functionality we want to include in GRASS 5.1 before thinking what kind of data structure to adopt. Here is a possible list of interesting features that one can hope to find into a vector GIS: A) ability to store multiple attributes and to have them showed by clicking on a map, ability to choose which attribute to use when performing computations on the map; [David D Gray] A) Multi-att support is largely underway in GRASS5.1. The question of displaying the data and querying through a graphical interface is a separate question. There is an idea to have a geometric representation of the map generated on the fly and stored in memory while a map is being displayed and queried. Also, this could be cached so that an unchanged, recently accessed map can be quickly redrawn without having to re-render the data from the topo data (in dig and dig_plus). This would be optional and the user would determine how much disk space to allocate to the cache. Getting a decent (screen) display in the first case isn't something we've really addressed yet. Development on the GRASS monitor will continue for now, but maybe we should be thinking about a new GUI( GTK+/KDE-based, Java, win32, openstep) or perhaps drivers for existing 3rd-party systems to access, display, query, maybe even edit GRASS databases. This is for beyond 5.1 B) ability to support overlay operations on vector data (which means also to join attribute tables) (overlay: intersection, erase, identity and so on, if you're familiar with ARC/INFO); [David D Gray] B) I think this requires a wholly new approach to get such operations working correctly and efficiently. Segmented processing of vector maps and network capabilities are needed here. This is closely related to the question of improving the build process, so that it can allow updating of maps without having to do monolithic builds each time. It also seems to me to be very dependent on C). . . C) ability to query maps both by spatial criteria, both on the attribute values just like in a SQL query; D) ability to relate attribute tables with some other non spatial information (catastral map with id referring to a table describing the owners of each parcel, and so on); E) ability to make concurrent users to make modifications on the same data. There may be other requests, of course, and I haven't considered 3D vector data such as TIN, but I think they are enogh to explain my proposals. I think that A) and B) are essential requirements if we want to claim that GRASS is a vector GIS. C) is so common among vector GIS that I would look with suspect to a GIS that don't perform such an operation. D) and E) are usually offered by high end systems in conjunction with a DBMS that sports spatial data extensions, and may be offered by GRASS if OSVectDB would turn into a real system (I think that now they are at a specification level). [David D Gray] dig_plus stores topo data, but not spatial locational data, at least not in a form that would allow efficient and spatially confined querying. So the plan is to have a third representation of the map, which would be essentially an R-tree (or similar) whose data is the type and index of the entities in the map, and is keyed spatially. A new element of the GRASS database would be created to store this - dig_spatial or something similar. For this we need to establish some kind of generic spatial tree with an API that allows easy access. Now, let's see what kind of data structure we can use in order to support A), B), and C) functions. To support only A) and B) plain files are a good solution until the number of data involved is not high. There are many possibilities, but I think that DBF files are a good solution. Why? * they are binary files, so access is faster that ASCII files; [Radim] No, dbf files are ascii !!! * they are quite standard, almost any spreadsheet can read them and most DBMS have some way to import them (well, at least for what concerns commercial DBMS); [Radim]That was one of reasons why I wrote simple dbf driver. * because they don't require any growth in our software base, we already have a library to access them: shapelib. Althought shapelib has limited capabilities when it comes to manage dbf files I think that it does what is needed. So we could store only one index toghether with geometric data and have all attributes stored in the DBF file. That'a a simple solutions, but it seems also effective when only A) and B) requirement are considered. [Radim] Yes, my driver is based on shapelib. For future we must either extend shapelib bit or use some other external library. [David D Gray] I agree we should move away from text file representations as they are too slow - except maybe for single-stage operations like import and export. If you consider also C) requirements DBF are not the best choice, since they don't support access thru SQL language. I think that here a DBMS is necessary, since we get the power of SQL queries for free. Berkeley DB is not a solution because it doesn't support SQL. PostgreSLQ is, and thru referential integrity capabilities it would allow us to support also E) requirement. If we want to stick on DBF files we have to choose wheter to build into GRASS a minimal SQL support by hand or not let the user perform queries unless a real DBMS is used. A SQL support based on DBF files would be anyway slow because one have to do a sequential scan on attribute files whereas a DBMS can use indexes and a built in query optimizer. [Radim] dbf driver (g51) is based on simple SQL parser so that it works like SQL database for limited subset of SQL statements. For simple and small projects dbf driver should be enough and for larger projects some other driver may be used (at this time only odbc available but postgres driver should not be problem) A solution that is based on storing topologic information in our classic files and attributes into a database (DBF or Postgres) seems to me a good choice. But it's not enogh. When it comes to give good support to overlay and spatial queries you also have to think at a fast way perform them: spatial indexes are the solutions, and there are some already made libraries that can build R-trees... the spatial index would be stored in a sepate file. So, one file for the topology, one file for attributes and one (optional) file for the spatial index. Since performance is an optional, we could add spatial index support later (say in GRASS 6) and do sequential scans in the meantime. [Radim] David is working on spatial indexes, which should be on level 3 access. [David D Gray] As in my remarks above. . . but it might be possible (through server side programming perhaps) to allow the tables to access the dig_spatial file. This has been mentioned on the list before, at least for PostgreSQL. [David D Gray] An example:- a table could contain a field that has information about the size and offset of a data block in dig_spatial containing the necessary data. Then a query could look up some records by index or querying on another field, extract this information, perform a spatial query on the R-tree (with its internal API), and then return the entity. This may then be part of another map. Or - a direct spatial query could look up the R-tree and return the records which are then queried with SQL, returning a result. And of course it is all behind the scenes', giving the appearance of integrated spatial and data querying. Now, I also would like to perform some criticts on site data: * access is slow, mainly because they are kept in ascii format and because the data structure can vary from record to record (-> site format is now too flexible); * site API is not the best part of the GIS library, in my humble opinion, but that is mainly due to the poor file structure. Why treat line, polygon and point data in a different way? Wouldn't it be possible, and more efficient, to store coordinates and an index into a binary file and put all the attributes into a DBF file? Or in a table inside a DBMS? [David D Gray] Currently (in 5.0) : Point data are stored as lines of two points with the same start and end point. Weird! In 5.1 we have two point types - a SITE and a CENTROID. This is in the vector map, not the site lists. [David D Gray] Lines, really polylines, are the atomic units of most GRASS maps, linear and area. Two types exist in 5.0 and will be the same (essentially) in 5.1: LINE and BOUNDARY. These represent the arc segments of the networks or two-dimensional manifolds that make up GRASS vector maps. LINE maps should conform to the definition of a NETWORK, and area maps (with polygons) to a 2-dimensional manifold (2DM). I think this is how it is just now, but we should make sure it is followed strictly. [David D Gray] Areas or polygons are a kind of composite entity, as are islands, which are composed during the build process from indexed references to their sub-components. I think one of the short-comings of the topological format at the moment is that it allows only these derivative types, while I think many others would be useful eg. - as a minimum - linear aggregates, to allow entities that reference branched structures as a single unit, like tributary systems. This would be _in addition to_ not instead of, providing categories for the individual arcs. Multipoint sets are also required, eg. a set of relevee locations may constitute a vegetation community description, where the individual sites might have their own quite distinct set of attributes. It works the other way round: why can't area boundaries have their own attribute sets separate from those of the area itself? There is occasionally a need for this, though it's rarer than the other examples above. Using binary files would give us a huge performance improvement, and to smaller files. I've seen it a the GRASS Day 2001 in Trento, Italy, somone had an implementation of a site API and format that stores all data in a binary file that also happens to be a quadtree (a fast way to store and index point data -> they performed spatial queries in a really fast way, it was impressive). I think that he's willing to donate that API to GRASS, he seemed only concerned about stability and code quality. Using DBMS tables or DBF files every record would get the same attributes, and we would have attributes names too -> this would also lead to a cleaner site API. You should also consider that this way line, polygon and site management would share some code leading to a smaller gis library (that means also smaller to mantain, a nice feature in the long run). This would also lead toan easier attribute management when it comes to use polygon and site data at the same time (I'm thinking about Voronoi diagrams, but also to overlay between polygon and site data). [Radim] I agree that sites data should be stored in vector files which is possible even in grass5.0. Otherwise we will maintain two similar libraries for vector and sites. New vector library and modules will support points. I was not courageous enough to suggest such thing like replace site_lists by vector files. I remember some mails here that this question was deeply discussed and ascii format was found as good solution but I think that for g51 we could consider site_lists format once more. What are the argumets for points separated from lines and areas if any? [David D Gray] The hierarchy of entities in the dig_plus structure are a good candidate for OOP treatment, and polymorphism through inheritance. That would reduce code, but not necessarily binary size. It would also make a more versatile and manageable data structure: but we don't it seems do that! ------------------------------------------------ [Roger Miller] I think it would be desirable if that data-base support also associates drawing attributes with the vector objects; e.g. area color fill and pattern, line weights, line styles, line color, point symbol, size and color. No doubt there are more. Presentation is one of the most important functions of GIS. GRASS' current state of division between analysis and presentation will make further improvements difficult. [David D. Gray] Though this is broadly to be welcomed, a number of alarm bells are ringing here. One of the problems with entry-level GIS, which echoes a problem across the whole spectrum of desktop philosophy and culture, is the problem of over-integration of logically distinct functions. Presentation is very important, and no-one will deny GRASS has much (everything!) to still do here, but it _is_ something essentially different from analysis, and digitising - which is really a CAD-like function - is something different again, tho' the latter is related to data structure and storage. I include such functions as cut and patch as `digitising'. Analysis needs to deal with attributes and it needs to be spatially aware, but doesn't mostly need to edit - if need be it can call the editing layer. [Roger Miller] My concern is that *if* there is any intent to improve the presentation capabilities available in GRASS then it will ultimately be necessary to provide database capabilities to serve drawing attributes. Those capabilities can be built as an inherent part of the vector attributes database. Alternatively the database capabilties can be added later in a separate, parallel and mostly duplicative effort. The latter alternative makes little sense to me. [Roger Miller] I think there's a substantial need in GRASS for integration of map preparation, map analysis and map presentation. Certainly it would be possible to go too far in that direction, but right now we are so far from that extreme that worrying about it seems a little premature. If my own setting is an indicator then public use of GRASS will be limited until the time that GRASS offers more evenly balanced and integrated capabilities. [David D. Gray] It is good to keep the processes the user doesn't need (or want) to see in the background, but it is also important to make sure the engine processes each stage the best way, logically, it can and not compromise the whole by confounding the parts. It's always _easier_ to cut corners but I think we can achieve what you suggest as long as we keep in mind what we are aiming for is to maintain GRASS as a `high-end' system. [Roger Miller] I appreciate that goal, but as it is now GRASS seems to be intended more as a `back-end' system, than as a `high-end' system. Regarding the separation of vector data and site data... Sites should function as a tie between a map location and a database. The current support for sites is a conceptual start in that direction, but of little practical use. For instance, one of my clients has somewhere over a 100 sites (wells) with a few to 100's of pages of data that is uniquely associated with each site. That is by no means a large example. I would like to be able to use a site list-like feature to organize and access that data. If your concept of data base support for vectors can be extended that far, then by all means merge site lists with vectors. It will make things much simpler. Otherwise, I think it is far better to keep sites for separate development. [David D. Gray] In the version 5.1 dig file, there are now separate entity types for point data. There is a `site' record and a `centroid' record, which are both point types. Actually both are new: the old way of registering a point is as a line of two identical points, and the location of the degenerate nodes is the site location. Area point features are stored currently in dig_att. In GRASS 5.0 however mostly sites use the text-based sites API. [David D. Gray] This suggests moving on to the possibility of linking up to heavy duty RDBMS engines where more than a few small attributes or complex linking is required. So plugins to PostgreSQL/Oracle/etc. or ODBC need to be developed to handle this. But surely this is overkill for the attribute data requirements of most maps, so for day-to-day needs, a simple vanilla DBMS system should do. [David D. Gray] The sites API will probably go the way of many redundant features in GRASS. It will be dropped when the vector engine takes over its functions. [Roger Miller] I think David is right that it would be overkill for day-to-day needs, so long as those needs are limited to the needs for map analysis, and probably for map presentation. The data needs for map construction are much greater than the needs for analysis or presentation and a database system designed to give the capabilites needed for map analysis is likely to be woefully inadequate to serve the demands of map construction. [Roger Miller] GRASS currently offers some Postgres support, and certainly that is helpful for map construction, but it doesn't come close to meeting the needs. -------------- [Eric G. Miller] I think we all can agree GRASS has a ways to go on both attribute data support *and* presentation. Now, if for a vector "map", if each layer/component (SITE, LABEL, LINE, AREA) has a separate attribute table then wouldn't it be a simple matter to *allow* the user to define one column of the table to indicate a "style" for the given thing. Then presentation routines could be told which field to use for looking up the drawing style for the given thing. The styles themselves, could consist of simple text files defining some appropriate variables. GRASS would provide a "DEFAULT" style as well as several "sample" styles. Styles could be indexed by name or number and would reside outside of the database proper (e.g. in etc/styles/ and possibly /home/user/.grass5/styles/). [Roger Miller] If I understand your suggestion, then what this would do is place database support for drawing attributes in some tagged-on external database (which is pretty much the way it works now) rather than in the database inherent in the GIS. It provides yet another unintegrated capability for which a user will need separate training and for which the developers would have to provide separate support. It's exactly what I would like to avoid. [Roger Miller] I know relatively little about database construction, so I can get over my head very quickly here. What I envisioned is that the drawing attribute support would be invisible to the user, included in the same database structure that organizes and provides data on other attributes. We don't currently have anything that uses that capability, so the structure wouldn't actually need to be filled. It just needs to be there for later use. If it's planned for, then it should be a relatively simple procedure to fill it with reasonable defaults. The software to manipulate and use those attributes can come later. [Roger Miller] If it isn't planned in, then it will be relatively difficult to add it later. [Eric G. Miller] Hypothetical polygon style example: [myStyle] AREA { line-color: #000000; line-width: 0.4pt; fill-style: stipple; fill-pattern: hatchure10; fill-foreground: #0000FF; fill-background: transparent; }; The details would have to be fleshed out. If a style could not be rendered or found, the drawing agent should try to render what it can (possibly using the default settings). Being able to define display styles that aren't tied to a particular map makes it easier to apply them to subset maps or related maps and get consistent results while only having to define the style once. Also, I think such a thing doesn't unduly burden any analysis/management aspects of the system. ----------------------------------------------------------- [Frank Warmerdam] I think your email on GRASS 5.1 attribute support is excellent. A few points from my own thoughts: o My thoughts on OSVecDB remain focused on what OGC calls simple features. In particular, this is a non-topological approach, and it seems that the GRASS community does not wish to alter the approach to vectors this dramatically. Thus, I think OSVecDB will not be the core methodology for storing GRASS vector data unless it is extended to support topology. o There are some very liteweight approaches to providing SQL support. If you think it would be desirable for even a "base" GRASS system to have SQL support this might be accomplished by using something like SQLite which provides a high degree of SQL support bug storing data in GDBM files. Folks willing to install a real database could replace SQLite with PostgreSQL or something similar. SQLite is at http://www.hwaci.com/sw/sqlite/ and I have been quite impressed with it from my modest involvement. [Andrea Aime] Wow, is seems really impressive. A good SQL support and index in only 9000 lines of code... Radim, how it compares to g51 dbf driver? Should we take a more closer look at it? It seems that SELECT support is quite complete,and indexing capabilities are interesting for querying large data. Import/export to and from PostgreSQL is another interesting plus... [Radim] SQLite seems to be a good solution. The only problem I see is that there is no GUI front-end which was one of my criteria. Dbf files may be edited in StarOffice and MSAccess (including forms). I thing that we don't have human resources for developing database front-end within grass and we don't want to reinvent wheel. So if such front-end is available is important. [Frank Warmerdam] It seems to me that if we use easily substitutable SQL based RDBMS systems then folks that need forms support and a GUI front end can choose an RDBMS that has them. If we use DBF and depend on external gui front ends it still won't be possible to distribute GRASS database forms applications since different users might choose different target RDBMSes, right? [Radim] At this stage of grass development I think this is the only way, i.e.: grass (with minimal functionality for accessing attributes) + external GUI front-end for RDBMS. [Frank Warmerdam] Is the GUI front end and forms requirement just so that users can see their data interactively, or so that substantial forms based applications can be built? [Radim] Some simple forms for viewing data interactively must be part of grass (such simple tcl/tk form for db sites editing is already db.attr accesible by db.what in g50) but for real applications we must use some third party solution (library is not enough, visual designer is needed) I think. [Frank Warmerdam] Someone mentioned the issue of having different programs for different databases. I completely agree that if we integrate SQL support smoothly into GRASS that the applications should be insulated from the actual database backend by some sort of plugable library. This might be based on an existing standard like ODBC or just a custom simplied database API. I was impressed with the relative simplicity of the abstracted database interface in Python. [Frank Warmerdam] BTW, does Postgres have a nice gui front end? I have always done my work from psql, but I would dearly love to try something a little more visual. :-) [Andrea Aime] Depending on your client you can choose among: * pgAccess, tcl/tk interface for Unix desktop; * pgAdmin, Visual Basic interface for Windows users; * phpPgAdmin (or something like this...), a web interface .. need more? [Radim] BTW: SQLLite files are not portable (The key size thus depends on the size of an integer on the host computer.) but that doesn't matter. [Frank Warmerdam] This is annoying. In the short term I guess it would be necessary to do a database dump and reload to transport to different system types. I would ideally like to see some sort of automatic translation be done at lower performance at some point. [Radim] Yes, but dump (vector export, import) will be needed anyway because of different user RDBMSes. [Andrea Aime] Uhm, I don't see it as a major problem, v.out.ascii can dump the table along with the coordinates, and v.in.ascii do the opposite. Regards [Radim] I think that both dbf and SQLite have some advantages. I don't think we can find the 'best' system and that is the reason why I prefer optional drivers for various databases. I don't see any problem in using new sqlite driver beside odbc, dbf and others. [Andrea Aime] Well, my concern was SQL related: IMHO the command should be the same even if the user adopts different DBMS, I don't like much the idea of a special command for postgres, another for dbf, another for ODBC and so on. Do we pass the query to the driver and let hid decide if it is able to manage it or not? [Radim] That is how d.vect (g51) works now. One command may be used with dbf or odbc. Modules know nothing about driver except its name. Whole comunication is done by DBMI library. o DBase files would be sufficient if you aren't concerned about having SQL support as a core service. However, in this case I would look around for a better DBF library that includes support for attributes. My DBF support in Shapelib is just adequate for it's purposes. Roger also writes that that he feels that presentation information should be stored in close association with vectors, like the attributes. I agree to some extent, but I think caution should be employed. Presentation is something that can grow arbitrarily complicated and this contributes substantially to the complexity and interchange difficulties of CAD formats like DXF and DGN. --------------------------------------------- > PS: I'm interested both in spatial indexes both in overlay operations... > can I join your work :-)? [Radim] Everybody is welcome. David is working on spatial related tasks. I thing that you could start work on spatial operation (overlay) functions. We have only dig_point_in_area() in g50 and we need ALL spatial operations between ALL element types. Have you any ideas? [Eric G. Miller] I've been looking at the spatial operations subject. I've found at least one polygon algorithm that should handle all of the set operations (intersect, union, etc..). I'm working towards fully understanding how to implement it. I've also been looking at some of the others like clipping lines with polygons (possibly resulting in multiple lines). With a little more study I think I'll be ready to start implementing these things. [Andrea Aime] Well, my first task would be to get a v.overlay command working. I already found a GPL'd C library that performs polygon to polygon overlay (PolyBoolean, old version, the new version is C++ based, non GPL and uses only integer coordinates) it shouldbe easy to adapt it to GRASS. But it doesn't work for polygon/line overlays, so it has to be extended. Moreover, there must be a fast way to locate polygon that can intersect (an R-tree or something like this). The sama applies to dig_point_in_area: useful, but slow since you have to compare each point with each polygon. Some kind of indexing is required altogheter... [Radim] OK, I'll leave spatial operations for you. Should be spatial operations part of vector lib ( Vect_*() ) or shall we open new vector spatial lib (VS_*()) - maybe GPL only (not LGPL). [Radim] We could maybe start with definition of functions we want?: int VS_analyse( struct Map_info map1, struct Map_info map2, int element1 , int element2, int operator, double distance)???? [Radim] operator: WITHIN, CONTAIN, OVERLAP, ... and many others (probably take names from some standard - openGis???) -----------------------ISI standard ------------------ [John Reid] -Has anyone had a look at the draft ISO standards? They deal with a lot of these issues. Been talking to our local rep on the TC/211 geomatics committee, and the impression I get is that they are not averse to open source apps implementing the standards ;-) More on this if anyone interested. ISO Geographic Information/Geomatics 19100 series http://www.statkart.no/isotc211/ ------------------- Compiled by Robert Lagacé, professeur Pavillon Comtois Université Laval Ste-Foy, Québec, G1K 7P4 tel : (418)-656-2131#2276 Fax : (418)-656-3723 E-mail: lagace@grr.ulaval.ca