Re: [Haskell-cafe] Expression problem in the database?
On Mon, Jul 22, 2013 at 4:00 PM, Manuel Gómez wrote: > * I could sacrifice relational integrity and store the expression > serialized, perhaps as an AST represented in JSON or somesuch — > although the rest of the data model is a rather traditional, > normalized relational schema, so this is undesirable in my situation > if only for consistency. A hybrid solution could be storing the expression as a string on an entity's field *and* creating a new entity for each foreign reference. In order words, instead of storing the whole AST in the database, store it as a list on the database and the whole thing again in a field. -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Expression problem in the database?
Here is one possible approach. First, convert the propositional formula into the conjunctive normal form (disjunctive will work just as well). Recall, the conjunctive normal form (CNF) is type CNF = [Clause] type Clause = [Literal] data Literal = Pos PropLetter | Neg PropLetter type PropLetter -- String or other representation for atomic propositions We assume that clauses in CNF are ordered and can be identified by natural indices. A CNF can be stored in the following table: CREATE DOMAIN PropLetter ... CREATE TYPE occurrence AS ( clause_number integer, (* index of a clause *) clause_card integer, (* number of literals in that clause *) positive boolean (* whether a positive or negative occ *) ); CREATE TABLE Formula ( prop_letter PropLetter references (table_of_properties), occurrences occurrence[] ); That is, for each prop letter we indicate which clause it occurs in (as a positive or a negative literal) and how many literals in that clause. The latter number (clause cardinality) can be factored out if we are orthodox. Since a letter may occur in many clauses, we use PostgreSQL arrays (which are now found in many DBMS). The formula can be evaluated incrementally: by fetching the rows one by one, keeping track of not yet decided clauses. We can stop as soon as we found a clause that evaluates to FALSE. BTW, `expression problem' typically refers to something else entirely (how to embed a language and be able to add more syntactic forms to the language and more evaluators without breaking previously written code). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Expression problem in the database?
On Tue, Jul 23, 2013 at 7:41 AM, Torsten Grust wrote: > Hi Manuel, > > On 22 Jul 2013, at 21:00, Manuel Gómez wrote (with possible deletions): >> Hi café, >> >> I don’t know whether this is a good forum to ask about this —perhaps >> Stack Overflow is better suited—, but since Haskell and related >> languages are so finely fit for good solutions to the expression >> problem, I figure this list may have a few helpful pointers regarding >> this problem. [...] > > are you merely seeking for a relational encoding of Boolean expressions > or do you plan to also operate on these expression (e.g., evaluate, > simplify, normalize) inside the database? Not inside the database, no. I need to encode conditions for triggering actions in response to events when certain predicates are satisfied over properties of the event and other related objects in the database — but the rules would be manipulated and evaluated outside the database in the code that processes such events (specifically, in my situation, in response to requests to a REST service implemented with Yesod). The key issue is that terms in the expressions would refer to existing database objects, so even though the evaluation would happen outside the database, it’d be convenient to have referential integrity: if an expression states something like «the request is an order for red balloons or for a hot-wheels car, and the user who placed the order is from France», I’d much prefer to get a foreign key constraint violation error if the red balloons are removed from the database (or perhaps just let the database cascade the deletion into the rule, or whatever) than get an error at the time an order is placed and the code outside the database attempts to evaluate a rule that refers to some now nonexistent «red balloon» object. Again, I realize this is all rather vague and only tangentially related to the topic for this list — but I do imagine some here must have run into this sort of issue. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Expression problem in the database?
Hi Manuel, On 22 Jul 2013, at 21:00, Manuel Gómez wrote (with possible deletions): > Hi café, > > I don’t know whether this is a good forum to ask about this —perhaps > Stack Overflow is better suited—, but since Haskell and related > languages are so finely fit for good solutions to the expression > problem, I figure this list may have a few helpful pointers regarding > this problem. [...] are you merely seeking for a relational encoding of Boolean expressions or do you plan to also operate on these expression (e.g., evaluate, simplify, normalize) inside the database? Cheers, --Torsten -- | Prof. Dr. Torsten Grust | Database Systems — Universität Tübingen (Germany) | torsten.gr...@uni-tuebingen.de | db.inf.uni-tuebingen.de ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Expression problem in the database?
Hi café, I don’t know whether this is a good forum to ask about this —perhaps Stack Overflow is better suited—, but since Haskell and related languages are so finely fit for good solutions to the expression problem, I figure this list may have a few helpful pointers regarding this problem. I’m facing a situation that requires saving boolean expressions of more or less arbitrary structure (encoding some business rules) into a SQL database. The expressions can include terms that refer to some other objects in the database. I realize this is somewhat vague, but that’s intentional: I’m really searching for ideas and experience with similar problems, not for a specific solution to my specific situation. Though I’m uncertain of their relative merits, I’ve had a few ideas myself: * I could sacrifice relational integrity and store the expression serialized, perhaps as an AST represented in JSON or somesuch — although the rest of the data model is a rather traditional, normalized relational schema, so this is undesirable in my situation if only for consistency. * I could directly model some form of the expression’s AST in the relational schema, and then endure the usual pain of representing sum types as relations. I imagine this to be quite unpleasant, although I haven’t tried it. * As these are boolean logic predicates, the expressions could be transformed into some normal form that could be more easily represented with relations. I’ll be mostly (but not exclusively) using this database from an application written in Haskell (Yesod using Esqueleto to talk to PostgreSQL), so some native Haskell solution could work almost as well as an SQL solution — but some legacy systems do need to interact with the database, so I’d prefer a solution in the database as long as it’s not horrible to work with in the application. I’ll be grateful for any ideas or pointers — my Googling for the expression problem has not proved fruitful. Thanks! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
