Hydra is a programming language that uses mathematical abstraction to model graphs within the language itself. It’s an open-source project spearheaded by Josh Shinavier, co-creator of Apache TinkerPop. In Josh’s own words: “In Hydra, programs are graphs, and graphs are programs.”
An open source project to search SQL code 'semantically': up to the meaning of parse trees. For example, searching for 'select from A,B' matches 'select from B,A'.
The code in database vs database in code duality has a long history, and one way to formalize it mathematically uses category theory: the notion of LINQ (language integrated query, such as collection comprehensions) is formally related to the notion of "query-integrated languages" (where data integrity constraints are Turing-complete domain specific languages extending the database vocabulary). https://arxiv.org/pdf/1511.06459
There is a partial solution to this problem: use formal methods such as symbolic logic and theorem proving to check the LLM output for correctness. We are launching a semantic validator for LLM-generated SQL code at sql.ai even now. (It checks for things like missing joins.) And others are using logic and math to create LLMs that don't hallucinate or have safety nets for hallucination, such as Symbolica. It is only when the LLM output doesn't have a correct answer that the technical issues become complicated.
Yes; categories extend traditional graphs with systems of equations. Hypergraphs extend traditional graphs by allowing edges to be between multiple nodes. Most operations on categories are formally undecidable because of the systems of equations; most operations on graphs/hypergraphs are decidable. This makes working with categorical databases a lot like doing computer algebra in e.g. Mathematica and provides a huge increase in expressive power (you can e.g. encode Turing machines with equations.)
At https://www.categoricaldata.net we claim that symbolic AI is also generative, when eg used in data warehousing. Instead of eg new images, the generatively gives you new primary and foreign keys, new ontologies, contradiction detection, etc.
Yes, at least with a strong enough arithmetic (such as Peano's), but that is usually more complicated; for example, you might have to create a Godel numbering or some other "deep embedding" to represent each set as a number. There's also so-called "reverse mathematics", which tries to determine the weakest axiom system capable of establishing a particular result.
A foundation for mathematics is any formalism sufficient to prove the results typically taken as axioms in practical mathematics. For example, in ZFC you can define numbers as sets in many different ways and prove that 1+1=2 for each of them - other foundations include higher order logic, topos theory, other set theories, etc.
Yes, although Dijkstra was interested in proving programs correct in general, not just in how lambda calculi correspond to logics correspond to categories (a proof technique for program correctness, among other things).
Yes, in the sense that "math is programming paper instead of computers", being better at one translates to being better at the other. This intuition can even be made precise via the "Curry-Howard isomorphism", upon which "proof assistants" such as Coq are built.
If you have a symmetric system, you can use group theory to make predictions about it. Similarly, if you have a compositional system, you can use category theory to make predictions about it. As for whether those predictions are useful, or non-obvious, or worth it, etc, tends to very a lot depending on the application, and the other techniques available- it's not a matter of being smart enough to get it. FWIW, I think category theory is certainly indispensable in denotational programming language semantics.
Hydra is a transformation toolkit along the lines of Dragon (Uber), but open source, and with a more advanced type system and other new features. Hydra maps data and schemas between languages in a way which maintains type conformance. It will even map functional programs between selected languages, including parts of its own source code.
You might try pages 8-16 of this presentation: https://www.categoricaldata.net/cql/lambdaconf.pdf . The examples are relational to relational and simplistic but they do illustrate running the same transformation both forward and backward, as well as show the "unit" of such a "monad". We implemented everything in public software, so hopefully the software is even better than my word! As for loading SQL to RDF specifically, I'd be happy to share that technique, but it isn't public yet- please ping me at ryan@conexus.com.
Bi-directional data exchange has many uses. For example, given a set of conjunctive queries Q, because coeval_Q is left adjoint to eval_Q, the composition coeval_Q o eval_Q forms a monad, whose unit can be used to quantify the extent to which the original query Q is "information preserving" on a particular source (so query/data quality). As another example, we use the technique to load data into OWL ontologies from SQL sources, by specifying an OWL to SQL projection query (tends to be easy) and then running it in reverse (tends to be hard). But no doubt more applications await!
The way to run conjunctive SQL queries forward and backward is described in this paper, https://www.cambridge.org/core/journals/journal-of-functiona... , (also available on the arxiv), where they are referred to as query 'evaluation' and 'co-evaluation', respectively. We never would have been able to discover co-evaluation if not for category theory! The previous link includes this paper, and many others.
Category theory does provide new algorithms if you unroll all of its definitions. For example, it reveals that SQL conjunctive queries can be run both "forward" and "backward" - an algorithm that is invisible in traditional SQL literature because that literature lacks the vocabulary to even talk about what "running backward" even means - it isn't an 'inverse' relationship but an 'adjoint' one. We also use it to provide a new semantics for data integration. Link: https://www.categoricaldata.net
When I write math papers I often use proof assistants such as Coq to leverage my programming background to avoid some pencil and paper proofs altogether and rule out many sources of human error. If you consider yourself better at programming than proving, definitely take a look at proof assistants to leverage the former to enhance the latter.
The answer is yes. There's even a notion of 'categorical normal form' that extends 3NF that guarantees the direct representability of such relational databases as set-valued functors. Spivak talks about it in e.g. http://math.mit.edu/~dspivak/informatics/FunctorialDataMigra...
The trade-off has to do with computability: because (finitely presented) categories can express so much, reasoning about them (for example, the 'word problem' for them) is undecidable. So to use CT as a modeling language requires automated theorem proving techniques, which are computationally expensive, and fast reasoning is a large part of what we're commercializing.
The categorical databases formalism is also known as 'sketches'. For example, here are some slides from NASA et al that connect to David's work but use this alternative phrasing. It shows how to use category theory to 'align' ontologies, with an example about voting. https://www.nasa.gov/sites/default/files/ivv_wojtowicz_sketc...
Sum types are harder to express as data integrity constraints that product types - for example, Horn clause constraints can be used to express that a table is a product (or limit, more generally) of other tables, but to express that a table is a co-product (or colimit, more generally) requires a stronger logic (handling disjunction, for example). This has implications for data processing algorithms such as the chase that depend on the strength underling logic.
Oh, such as a list of statements unprovable under a specific Godel numbering? Definitely much more difficult - I never saw such a list in grad school, although I wouldn't rule out the existence of one.
You are right that computer generated proofs are often tough to understand, and that understanding is often the intended goal of writing a proof. But proofs can be useful for reasons besides human understanding, especially so in engineering. For example, when a browser establishes a secure session with an encryption protocol, the reason it is secure has to do with the difficulty of finding a proof that eg certain numbers factor, but no human cares about this proof. As another example, a compiler can use a proof that a program is type correct to optimize it, but humans would not find such proofs interesting at all.
It is true that Godel's incompleteness theorem states that there is no complete axiomatization of arithmetic; no first order axioms can characterize the natural numbers up to isomorphism. But Godel's completeness theorem ( https://en.wikipedia.org/wiki/Gödel%27s_completeness_theorem) states that first order logic is in fact complete as a deductive system, and most automated theorem provers have the property that if a proof exists, given enough time they will eventually find it. In higher order logic the situation is reverse: the proof theory is incomplete, but you can eg characterize the natural numbers up to isomorphism. Anyway, I believe that many of your critiques apply to formal logic itself, not so much the attempts to automate formal logic.