Query (complexity)

<h2 id="order-independent-queries">Order-independent queries</h2>
<p>A query is order-independent if the ordering of objects in the structure does not affect the results of the query.  In databases, these queries correspond to generic queries (Immerman 1999, p. 18).  A query is order-independent iff 
  
    
      
        I
        (
        
          
            A
          
        
        )
        ≡
        I
        (
        
          
            B
          
        
        )
      
    
    {\displaystyle I({\mathfrak {A}})\equiv I({\mathfrak {B}})}
  
 for any isomorphic structures 
  
    
      
        
          
            A
          
        
      
    
    {\displaystyle {\mathfrak {A}}}
  
 and 
  
    
      
        
          
            B
          
        
      
    
    {\displaystyle {\mathfrak {B}}}
  
.
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Neil, Immerman (1999). Descriptive Complexity. New York, NY: Springer New York. ISBN 9781461205395. OCLC 853271745. <a href="9781461205395" target="_blank">9781461205395</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Query (complexity) open-in-new

Query (complexity)