science

Quantum Reasoners Hold Key to Future Web

Last year, a company called DWave Systems announced their quantum computer (the ‘Orion’) – another milestone on the road to practical quantum computing. Their controversial claims seem worthy in their own right but they are particularly important to the semantic web (SW) community. The significance to the SW community was that their quantum computer solved problems akin to Grover’s Algorithm speeding up queries of disorderly databases.

Semantic web databases are not (completely) disorderly and there are many ways to optimize the search for matching triples to a graph pattern. What strikes me is that the larger the triple store, the more compelling the case for using some kind of quantum search algorithm to find matches. DWave are currently trialing 128qbit processors, and they claim their systems can scale, so I (as a layman) can see no reason why such computers couldn’t be used to help improve the performance of queries in massive triple stores.

 What I wonder is:

  1. what kind of indexing schemes can be used to impose structure on the triples in a store?
  2. how can one adapt a B-tree to index each element of a triple rather than just a single primary key – three indexes seems extravagant.
  3. are there quantum algorithms that can beat the best of these schemes?
  4. is there is a place for quantum superposition in a graph matching algorithm (to simultaneously find matching triples then cancel out any that don’t match all the basic graph patterns?)
  5. if DWave’s machines could solve NP-Complete problems, does that mean that we would then just use OWL-Full?
  6. would the speed-ups then be great enough to consider linking everyday app data to large scale-upper ontologies?
  7. is a contradiction in a ‘quantum reasoner’ (i.e. a reasoner that uses a quantum search engine) something that can never occur because it just cancels out and never appears in the returned triples? Would any returned conclusion be necessarily true (relative to the axioms of the ontology?)

Any thoughts?

UPDATE
DWave are now working with Google to help them improve some of their machine learning algorithms. I wonder whether there will be other research into the practicality of using DWave quantum computing systems in conjunction with inference engines? This could, of course, open up whole new vistas of services that could be provided by Google (or their competitors). Either way, it gives me a warm feeling to know that every time I do a search, I’m getting the results from a quantum computer (no matter how indirectly). Nice.

LinqToRdf v0.7.1 and RdfMetal

I’ve just uploaded version 0.7.1 of LinqToRdf. This bug fix release corrects an issue I introduced in version 0.7. The issue only seemed to affect some machines and stems from the use of the GAC by the WIX installer (to the best of my knowledge). I’ve abandoned GAC installation and gone back to the original approach.

Early indications (Thanks, Hinnerk) indicate that the issue has been successfully resolved. Please let me know if you are still experiencing problems. Thanks to 13sides, Steve Dunlap, Hinnerk Bruegmann, Kevin Richards and Paul Stovell for bringing it to my attention and helping me to overcome the allure of the GAC.

Kevin also reported that he’s hoping to use LinqToRdf on a project involving the Biodiversity Information Standards (TDWG). It’s always great to hear how people are using the framework. Please drop me a line to let me know how you are using LinqToRdf.

Kevin might find feature #13 useful. It will be called RdfMetal in honour of SqlMetal. It will automate the process of working with remotely managed ontologies. RdfMetal will completely lower any barriers to entry in semantic web development. You will (in principle) no longer need to know the formats, protocols and standards of the semantic web in order to consume data in it.

clip_image001[5]

Here’s an example of the output it generated from DBpedia.org for the FOAF ontology:

 ./RdfMetal.exe -e:http://DBpedia.org/sparql -i -n http://xmlns.com/foaf/0.1/ -o foaf.cs

Which produced the following source:

namespace Some.Namespace
{
[assembly: Ontology(
    BaseUri = "http://xmlns.com/foaf/0.1/",
    Name = "MyOntology",
    Prefix = "MyOntology",
    UrlOfOntology = "http://xmlns.com/foaf/0.1/")]


    public partial class MyOntologyDataContext : RdfDataContext
    {
        public MyOntologyDataContext(TripleStore store) : base(store)
        {
        }
        public MyOntologyDataContext(string store) : base(new TripleStore(store))
        {
        }

                public IQueryable<Person> Persons
                {
                    get
                    {
                        return ForType<Person>();
                    }
                }
        
                public IQueryable<Document> Documents
                {
                    get
                    {
                        return ForType<Document>();
                    }
                }
        
                // ...        

    }

[OwlResource(OntologyName="MyOntology", RelativeUriReference="Person")]
public partial class Person
{
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "surname")]
  public string surname {get;set;}
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "family_name")]
  public string family_name {get;set;}
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "geekcode")]
  public string geekcode {get;set;}
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "firstName")]
  public string firstName {get;set;}
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "plan")]
  public string plan {get;set;}
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "knows")]
  public Person knows {get;set;}
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "img")]
  public Image img {get;set;}
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "myersBriggs")]
  // ...
}

[OwlResource(OntologyName="MyOntology", RelativeUriReference="Document")]
public partial class Document
{
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "primaryTopic")]
  public LinqToRdf.OwlInstanceSupertype primaryTopic {get;set;}
  [OwlResource(OntologyName = "MyOntology", RelativeUriReference = "topic")]
  public LinqToRdf.OwlInstanceSupertype topic {get;set;}
}
// ...

As you can see, it’s still pretty rough, but it allows me to write queries like this:

[TestMethod]
public void TestGetPetesFromDbPedia()
{
    var ctx = new MyOntologyDataContext("http://DBpedia.org/sparql");
    var q = from p in ctx.Persons 
            where p.firstName.StartsWith("Pete")
            select p;
    foreach (Person person in q)
    {
        Debug.WriteLine(person.firstName + " " + person.family_name);
    }
}

RdfMetal will be added to the v0.8 release of LinqToRdf in the not too distant future. If you have any feature requests, or want to help out, please reply to this or better-still join the LinqToRdf discussion group and post there.