At 11:54 AM 11/11/99 +1100, Robert Leftwich wrote:

I have a requirement to be able to apply a user-definable filter to all the views on the object database. Obviously this would be best applied at a low a level as possible in order to minimise the impact on the application code and to be made as generic as possible for maximum flexibility. To save re-inventing the wheel, has anyone else had this requirement and if so how did you implement it ?

Ty Sarna and I have come up with a concept for this, which we have not yet implemented, as we are still finalizing design details. We believe that it could be made quite general. The basic idea is that you have a "Predicate" interface, for objects which can be combined with "and", "or", and "not" to result in more complex predicates. The Predicate interface would also include functions to return a Generator or a Filter. A Generator is an object which can return a list of objects matching the Predicate, while the Filter is a callable object which may be passed an object and returns true if the object matches the Predicate. Generators and Filters have to also provide a small amount of metadata indicating their cost to filter or generate information. The and, or, and not operations return generic Intersect, Union, and Complement objects which, when asked for their Generator or Filter, create optimized versions based on the cost criteria of their component Predicates. For example, if you ask an Intersect predicate for a generator, it should ask its component predicates for the generator likely to produce the smallest set, then use the remaining predicates to filter that generator. Conversely, if you ask a Union for a filter, it should apply its component Predicate filters in such a way as to maximize the probability of an early hit. Anyway, here's where the fun part comes in. Let's say that you define a set of Predicates that can either verify an object attribute when used as a filter, OR can search a ZCatalog when used as a generator. Let's say you also define another predicate, such as "ContainedWithin", which tells you if one object is reachable from another. Now, to search your site for things with a certain field value, you can do something like this: blue_under_here = Keywords['blue'] & ContainedWithin[somefolder] to get a Predicate which expresses your search. Now, you can do something like: blue_under_here.getResults() to get the actual objects, or, you can say: blue_filter = blue_under_here.getFilter() blue_filter(something) to see if object 'something' matches the criterion. Depending on what the ContainedWithin and Keywords predicates tell their Intersection object, it will pick one of them to return the objects and use the other predicate to filter the list. The interesting thing about the Predicate concept is that predicates can apply to *anything*. For example, suppose you create a PrimeNumber predicate, and a FibonacciSequence predicate. You can intersect them both with a Range predicate, and find all the prime Fibonacci numbers in a certain range. Okay, maybe you don't have any reason to do that. But how about a RandomSelection predicate that selects a random member of the enclosed set? So that: RandomSelection[Keywords['blue'] & ContainedWithin[somefolder]].getResults() Will return a random member of the set of 'blue' keyword-bearing objects within somefolder? Might be fun for returning random taglines keyed to a user's preferences, eh? Or random selection of one they haven't seen in X number of days, or... How about predicates associated with a relational DB? Intersect the two, or join them. By our convention, parameterized predicates (such as Keywords and ContainedWithin) use __getitem__ or __getslice__ to return a predicate which applies to the set of values given, which may itself be a predicate (which is used as a filter for the values of the property the predicate tests). Hm. That might not have been too clear. Let's take Keywords as an example. Keywords[StringContaining['u']] would match keywords like 'blue', 'purple', and 'puce'. If used as a filter, it would do this by applying the inner predicate as a filter against an attribute value of the object being checked. If being used as a generator, it would have to get the unique values for the keywords attribute from the catalog first, then apply the StringContaining filter against them to get the list it would use as a catalog query. (Notice that while all Predicates must support being used as filters, not all can support being generators. PrimeNumber and FibonacciSequence, for example, have to be intersected with some finite number set before you can use them as a generator.) Let's look at more interesting ways to apply predicate projection (if that's the correct term.) How about: ContainedWithin[Keywords['blue']] Used as a filter, this would tell you whether an object had a parent with a keywords attribute of 'blue'. Used as a generator, it would search the catalog for objects with keyword 'blue', then return all objects reachable from those objects. Is your head spinning yet? How about this: you drop in some Predicates that union the predicates from several catalogs plus an LDAP server and a relational database, so that Keywords is now really Catalog1.Keywords || Catalog2.Keywords || SQLDB.Keywords || LDAP1.Keywords. Performing any of the searches above still works, only now you have a (lazy) search set spanning multiple data sources. Most predicates will probably want to check if they have a type or data source in common when doing 'and' and 'or' operations so as to create appropriate union or intersection predicates. For example, a predicate which refers to a field or index in a particular Catalog will want to see if is being intersected with another from the same Catalog, as that will allow it to construct a better query when used as a generator. Okay, this all sounds great in principle, but where's the implementation? We understand the basics of the abstract interface, but there are a few details we need to work out to ensure that the framework will have high interoperability. The base module will probably include: * Constants to be used in optimization metadata (e.g., COST_BUILTIN_FILTER, COST_IN_MEMORY_GENERATOR, COST_DISK_ACCESS) * Some basic predicates like AlwaysTrue, EmptySet, IsObject, EqualsObject, AttributeValue * Utility classes to construct atomic predicates from various standard Python objects like callables and sequences, so that predicates like the Keywords example don't have to care whether you pass them a function, a string, or another predicate. (e.g. KeyOf(dict) would give you a predicate whose getFilter would return dict.has_key, which is ready to be used as a filter. getResults(), on the other hand, would return the results of calling the dictionary's keys() method.) * Basic Union and Intersect objects that can perform crude optimization and re-organization, reshuffling their components to group Predicates together that have common data sources, as well as predicting the best way to go about doing a filtering or generating operation based on the components' cost estimates. We believe such a framework would make a great many interesting things do-able in Zope, as well as serving as a fully general "object query language" for Zope. (Not to mention for Python in general!) Which is why we want to implement it. Our first implementation will probably be a strawman which we'll publish for comments and feedback. We'll probably implement some silly things like Prime, Fibonacci, RandomSelection, IntegerRange, and so on, just to get the feel of using predicates. We might also do some wrappers over the Query objects which are part of the Zope2 library. They'll undoubtedly make great Filters for many purposes, especially since they're implemented in C. We'll probably also reuse some code from Lazy.py so that generators can be kept from fully instantiating huge result sets.

On 22 Nov 1999 19:40:00 -0600, Robert Leftwich wrote:

Robert Leftwich wrote:

...

I have a requirement to be able to apply a user-definable filter to all the views on the object database. Obviously this would be best applied at a low a level as possible in order to minimise the impact on the application code and to be made as generic as possible for maximum flexibility. To save re-inventing the wheel, has anyone else had this requirement and if so how did you implement it ?

I'm off in a little different area which is an extension of the TinyTables concept where I'm wrapping information obtained from several different locations into an object which is then unrolled or 'SubMined' as Ty calls it. :^) The information comes from the filesystem, the Zope database, and hopefully soon, from other database queries, etc. Right now I roll almost all the results into ZRDB.Results objects so I can more consistently filter them and carry the filter results along as the user traverses through the data. This has a chance of allowing me to 'join' my ZRDB.Results with other database results, etc. I've tried to separate functionality to provide for more flexibility with selectable filters that are applied to the SubMine results object via __bobo_traverse__, in addition to DTML-based rendering filters which are not 'carried around' as the user traverses the objects. The SubMine filters are listed in order and can be selectively removed from the 'filter list'. This concept was derived from the 'Datamining' product posted earlier this year, along with some initial work that Ty helped me with. The problem is that the __bobo_traverse__ mechanism I'm using is fraught with many problems but I can't see any way around them right now. This is somewhat applicable to the discussion on schemas because these objects change on a regular basis (SubMines on every request), but storing *some* of those changes as transactions in the Zope database is simply not appropriate. Right now, it appears to me that Zope isn't well suited to dealing with persistent, user-defined volatile filters, schemas, etc. It really wants to pass those things off to database-like queries. For a while I thought that I ought to do just that with my datamining stuff - just write a separate server that handles the things that Zope doesn't deal very well with, but the problem is that Zope is so darned close to what *is* needed that it'd be pretty stupid to go off and write something else. I'd rather see if there is a way to convince Zope to differentiate between objects that need transacted in the Zope database and objects that just need to be cached in the Zope database, otherwise retaining the same behavior.

Phillip J. Eby wrote :

...

Ty Sarna and I have come up with a concept for this, which we have not yet implemented, as we are still finalizing design details. We believe that it could be made quite general. The basic idea is that you have a

(Snip some excellent design/use case discussion [not to mention the odd head spin :-) ]...)

I have been thinking about this on and off for the last week or so and I wanted to bounce around an idea or two.

Given that one of the main criteria (for me, at least) is the ability to apply different filters on a per user basis, I am contemplating adding a filter keyword to the in and tree tags. There already exists a very specialised filter in both of these tags (the skip_unauthorized flag - which is a filter for unauthorised objects), so it should be easy to enhance this to support a more generic filter of the type proposed by Philip and Ty.

The factors pushing me toward this solution are that filtering is generally a UI-driven requirement and I felt very uncomfortable about retrieving user-selected filters from the REQUEST variable at low levels in the code (I was experimenting with filtering in the objectId() method of ObjectManager). Not to mention that this solution only worked for ObjectManager associated data and fails when you have lists or dictionaries or external data access such as SQL.

Anyone have any thoughts or comments ?

The SubMine filters that Ty and I worked on attempted to mimic SQL query commands as it provided a familiar environment. If we are really talking about general-purpose filters that can operate on ZRDB.Results objects (in particular), I'd sure like to see what could be done here. BTW, Phillip kinda lost me. :^) Ty - You know what I'm working on. Are we talking about anything remotely related? :^) I'm ready to ditch what I'm doing if there's a better way out there. ---- FWIW, MS and MIT are offering some funds for developing Open Source educational resources that I think we stand a chance of taking advantage of in this area... (http://swissnet.ai.mit.edu/projects/i-campus/) "I-Campus is a collaborative initiative of MIT and Microsoft Research to conduct research and create new technologies that will set the pace for university education in the next five to ten years. The project aims at fostering excellence in technology-enhanced education, through producing materials that adhere to open standards, with results and source code which can be widely published and disseminated. I-Campus was launched in October 1999 as a five-year research partnership between MIT and Microsoft, but we plan to engage additional academic and industry partners as the project evolves." I am in touch with some people who are considering a proposal that some of these issues might address. A few application-specific things would need to be developed but I think we are headed down similar paths and ought to consider working together. Any interested parties? Paul and the rest of you DC folks, there are a number of issues with the I-Campus research that are darned close to what the AISD proposal that we worked on eventually wanted to address. You might want to take a look and see if there are partnership opportunities available to pick up where we left off. Kent

Phillip J. Eby wrote:

Ty Sarna and I have come up with a concept for this, which we have not yet implemented, as we are still finalizing design details. We believe that it could be made quite general. The basic idea is that you have a "Predicate" interface, for objects which can be combined with "and", "or", and "not" to result in more complex predicates. The Predicate interface would also include functions to return a Generator or a Filter. A Generator is an object which can return a list of objects matching the Predicate, while the Filter is a callable object which may be passed an object and returns true if the object matches the Predicate. Generators and Filters have to also provide a small amount of metadata indicating their cost to filter or generate information.

Phillip... Putting relational operations directly into Python will have substantial repurcussions. The Python community may not appreciate having Guido run over by the Distributed Database Bus, not to mention the 'interesting' vision of relational db people converting to Zen. Pandora, in her wildest dreams... However, since you have opened the box, let us proceed... I have a few problems with the SubMine datamining concept, however I think the basic concept is very encouraging. In our situation, the existing databases are 'alive' (including the schemas). The schemas are defined in each query using a few relatively simple rules. One of the reasons they still use a file-systemed database is that in this environment (population genetics research), simply not enough is known to structure a traditional relational database and almost everything is volatile. The problem is that you have to browse the database in order to formulate a query. Submines allow our scientists and data analysts to browse the databases and determine the relationships they need to impose interactively. They love it because it acts somewhat like a statistical analysis package but acts directly on the database tables (not to mention via the web). The big problem with current SubMines is that the filters are inseparable from their data objects. They are not pythonic and can only exist in the context of a __bobo_traverse__. I've been trying to determine a way to reference them from another object in order to perform joins etc., and I had pretty much decided that their non-pythonic nature is a show-stopper here. What you propose might pythonize Submine filters if there is a way to traverse them without using __bobo_traverse__. Even if they can't be traversed, I think the predicate concept stands to transform how we do things. Me.sitting.bus_stop.waiting.impatiently.beside.self.for(Phillip.explain)